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);
}
}

```