ssort.c

常用数据结构算法代码库

/****************************************************************************
*
*					Copyright (C) 1991 Kendall Bennett.
*							All rights reserved.
*
* Filename:		$RCSfile: ssort.c $
* Version:		$Revision: 1.3 $
*
* Language:		ANSI C
* Environment:	any
*
* Description:	Shell sort for array's and array's of pointers.
*
* $Id: ssort.c 1.3 91/12/31 19:40:39 kjb Exp $
*
* Revision History:
* -----------------
*
* $Log:	ssort.c $
* Revision 1.3  91/12/31  19:40:39  kjb
* Modified include file directories
* 
* Revision 1.2  91/09/02  11:21:52  ROOT_DOS
* Minor cosmetic change.
* 
* Revision 1.1  91/08/16  13:16:25  ROOT_DOS
* Initial revision
* 
****************************************************************************/

#include "debug.h"
#include "ssort.h"

PUBLIC void ssort(char *base, int nel, int elsize, int (*cmp)(void *, void*) )
/****************************************************************************
*
* Function:		ssort
* Parameters:	base	- Pointer to base of array to sort
*				nel		- Number of elements to sort
*				elsize	- Size of elements in bytes
*				cmp		- Comparision routine for elements
*
* Description:	Sorts the array using the standard "Shell Sort". The shell
*				sort is simple and very efficient if we are sorting only
*				small numbers of elements (say < 5000 elements).
*
****************************************************************************/
{
	int		i,j;
	int		gap,k,tmp;
	char	*p1,*p2;

	for (gap = 1; gap <= nel; gap = 3*gap + 1);

	for(gap /= 3; gap > 0; gap /= 3)
		for(i = gap; i < nel; i++)
			for(j = i-gap; j >= 0; j -= gap) {
				p1 = base + (j * elsize);
				p2 = base + ((j+gap) * elsize);

				if ((*cmp)(p1,p2) <= 0)		/* Compare the two elements	*/
					break;

				for (k = elsize; --k >= 0;) { /* Swap two elements, one	*/
					tmp = *p1;
					*p1++ = *p2;
					*p2++ = tmp;
					}
				}
}

PUBLIC void assort(void **base,int nel,int elsize,int (*cmp)(void*,void*) )
/****************************************************************************
*
* Function:		assort
* Parameters:	base	- Pointer to base of array to sort
*				nel		- Number of elements to sort
*				cmp		- Comparision routine for elements
*
* Description:	Same as ssort(), except that it sorts an array of pointer
*				size objects.
*
****************************************************************************/
{
	int		i,j,gap;
	void	*tmp, **p1, **p2;

	for (gap = 1; gap <= nel; gap = 3*gap + 1);

	for(gap /= 3; gap > 0; gap /= 3)
		for(i = gap; i < nel; i++)
			for(j = i-gap; j >= 0; j -= gap) {
				p1 = base + j;
				p2 = base + j + gap;

				if ((*cmp)(p1,p2) <= 0)		/* Compare the two elements	*/
					break;

				tmp = *p1;
				*p1 = *p2;
				*p2 = tmp;
				}
}