Qsort.c

/*************************************************************************
***  QSORT.C - Sample of qsort() algorithm
***  MG - 9/16/97
***
***  Comment: You will note that this program will demonstrate the fact that
***  the Quick Sort algorithm works worst on already-sorted data.
*************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int Compares, Swaps;

/* Compare function, called by the QSort routine to determine if 2 elements
** should be swapped
*/
int Compare( char *Str1, char *Str2 )
{
	Compares++;
	return( stricmp(Str1,Str2) );
}

/* Swaps 2 elements, called by QSort */
void Swap( char **One, char **Two )
{
	char *Tmp;
	Swaps++;
	Tmp=*One;
	*One=*Two;
	*Two=Tmp;
}

int Depth; /* Global variable, used to demonstrate the depth of recursion*/

/***********************************************************************
** Name:	QSort
** Descr:	Implements the Quick Sort algorithm to sort an array of strings
** Params:	Lines = Lines to sort
**          Left = Left index of current partition
**          Right = Right index of current partition
** Author:  MG 9/16/97
** Comment: The quick sort algorithm works by recursively dividing the
**          array into partitions, then sub-partitions, and sub-sub partitions,
**          and so on.  A basic organization is performed on each partition.
***********************************************************************/
void QSort( char *Lines[], int Left, int Right )
{
	int Part, j;

	Depth++; /* Just for demo, keep track of depth of recursion */

	if( Right > Left )  /* Watch our bounds */
	{
		Part=Left;
		j=Right-1;

		/* Loop to determine partition */
		for( ;; )
		{
			/* Part (partition) towards the right while it's < rightmost */
			while( Compare( Lines[Part], Lines[Right] ) < 0 )
				Part++;
			/* Move j from right-1 to Part */
			while( j>Part && Compare( Lines[j], Lines[Right] ) >= 0 )
				j--;
			/* If Part and j crossed paths, or j is out of bounds, we got the Part */
			if( Part >= j || j<0)
				break;

			/* Otherwise, swap these lines (here's where data is moved far) */
			Swap( Lines+Part, Lines+j);
		}
		if( Part != Right )
			Swap( Lines+Part, Lines+Right);

		QSort( Lines, Left, Part-1 ); /* Sort the left of the partition */
		QSort( Lines, Part+1, Right ); /* sort the right of the partition */
	}
}

/***********************************************************************
** Name:	QuickSort
** Descr:	A simply 'front-end' function to call the QSort function
** Params:	Lines = Lines to sort
** Author:  MG 9/16/97
** Comment: See QSort for more details
***********************************************************************/
void QuickSort( char *Lines[] )
{
	int Count;
	Depth=0;
	for( Count=0; Lines[Count]; Count++ )
		;
	if( Count )
		QSort( Lines, 0, Count-1 );
	printf("Depth: %u\n", Depth);
	
}

/* Inititializes Lines with sample data.  Mode indicates what type of data:
**   Mode = 0 then sequntial data is set
**   Mode = 1 then random data is set
**   Mode = 2 then reverse-sequential data is set
*/
void InitLines( char *Lines[], int Count, int Mode )
{
	int i;
	char Tmp[32];

	for( i=0; i<Count; i++)
	{
		sprintf( Tmp, "%05d", Mode==0?i: Mode==1? rand() : Mode==2?Count - i: (i==3?0:i) );
		Lines[i] = strdup( Tmp );
	}
}

#define LCOUNT 24

void Print(char **Lines) 
{ 
	while( *Lines ) 
		printf("%s ", *Lines++);
	printf("\n");
}

char *Lines[ LCOUNT+1 ];

char *MStr[]={"Sorted", "Random", "Reverse", "Mostly Sorted"};

void main( void )
{
	int DataOrder;
	
	for( DataOrder=0; DataOrder < 4; DataOrder++ )
	{
		Swaps=Compares=0;
		InitLines(Lines, LCOUNT, DataOrder );
		QuickSort( Lines);
		printf("%s: Compares: %u   Swaps: %u\n", MStr[DataOrder], Compares, Swaps );
		Print(Lines);
	}
}