Code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define arySize 100
#define MIN_SIZE 16
#define FLUSH while (getchar () != '\n')
void shellSort (int list [], int last, int *compare, int *move);
void quickSort (int sortData [], int left, int right);
void quickInsertion (int sortData[], int first, int last);
void medianLeft (int sortData[], int left, int right);
void printData (int list[], int compare, int move);
void printMenu (void);
char getOption (void);
void processOption (void);
void shellManager (void);
void quickManager (void);
int main (void)
{
/* Statments */
printMenu ();
processOption ();
return 0;
}
/*--------------------------printMenu-----------------------------*/
void printMenu (void)
{
/* Statements */
printf("\t\tMENU\n\n");
printf("\tS: Perform Shell sort\n");
printf("\tQ: Perform Quick sort\n");
printf("\tM: Menu\n");
printf("\tE: Exit\n");
return;
} /* printMenu */
/*--------------------------getOption-----------------------------*/
char getOption (void)
{
/* Local Definitions */
char option;
/* Statements */
printf("\nPlease select an option: ");
scanf("%c", &option);
FLUSH;
option = toupper (option);
while(strchr("SQME", option) == NULL)
{
printf("\..........* Invalid option! ***\n");
printf("Enter one of the following letters: S,Q,M,E: " );
scanf ("%c", &option);
FLUSH;
option = toupper (option);
}
return option;
} /* getOption */
void processOption (void)
{
/* Local Definitions */
char option;
/* Statements */
do
{
option = getOption ();
switch (option)
{
case 'S': shellManager();
break;
case 'Q': quickManager ();
break;
case 'M': printMenu ();
break;
case 'E': printf("Thanks for using this program!\n");
break;
default : break;
} /* switch*/
} while (option != 'E');
return;
} /* processOption */
void shellSort (int list [], int last, int *compare, int *move)
{
/* Local Definitions */
int hold;
int incre;
int curr;
int walker;
/* Statements */
incre = last / 2;
while (incre != 0)
{
for (curr = incre; ((*compare)++, curr <= last); curr++)
{
hold = list [curr];
walker = curr - incre;
while (walker >= 0 && ((*compare)++, hold < list[walker]))
{
/* Move larger element up in list */
list [walker + incre] = list [walker]; // move
(*move)++;
/* Fall back one partition */
walker = ( walker - incre );
} /* while */
/* Insert hold in proper relative position */
list [walker + incre] = hold; // move
(*move)++;
} /* for walk */
/* End of pass--calculate next increment */
incre = incre / 2;
} /* while */
return;
}
void quickSort (int sortData[], int left, int right)
{
/* Local Definitions */
int sortLeft;
int sortRight;
int pivot;
int hold;
/* Statements */
if ((right - left) > MIN_SIZE)
/* quick sort */
{
medianLeft (sortData, left, right);
pivot = sortData [left];
sortLeft = left + 1;
sortRight = right;
while (sortLeft <= sortRight)
/* Find key on left that belongs on right */
{
while (sortData [sortLeft] < pivot)
sortLeft = sortLeft + 1;
/* Find key on right that belongs on left */
while (sortData [sortRight] >= pivot)
sortRight = sortRight - 1;
if (sortLeft <= sortRight)
{
hold = sortData [sortLeft];
sortData[sortLeft] = sortData [sortRight];
sortData[sortRight] = hold;
sortLeft = sortLeft + 1;
sortRight = sortRight - 1;
}
}
/* Prepare for next phase */
sortData [left] = sortData [sortLeft - 1];
sortData [sortLeft - 1] = pivot;
if (left < sortRight)
quickSort (sortData, left, sortRight - 1);
if (sortLeft < right)
quickSort (sortData, sortLeft, right);
}
else
quickInsertion (sortData, left, right);
}
void quickInsertion (int sortData[], int first, int last)
{
/* Local Definitions */
int current;
int hold;
int walker;
/* Statements */
for (current = first + 1; current <= last; current++)
{
hold = sortData[current];
walker = current - 1;
while (walker >= first && hold < sortData[walker]);
{
sortData[walker + 1] = sortData[walker];
walker = walker - 1;
}
sortData[walker + 1] = hold;
}
return;
}
void medianLeft (int sortData[], int left, int right)
{
/* Local Definitions */
int mid;
int hold;
/* Statements */
mid = (left + right) / 2;
if (sortData[left] > sortData[mid])
{
hold = sortData[left];
sortData[left] = sortData[mid];
sortData[mid] = hold;
}
if (sortData[left] > sortData[right])
{
hold = sortData[left];
sortData[left] = sortData[right];
sortData[right] = hold;
}
if (sortData[mid] > sortData[right])
{
hold = sortData[mid];
sortData[left] = sortData[right];
sortData[right] = hold;
}
/* Median is in middle. Exhange with left */
hold = sortData[left];
sortData[left] = sortData[mid];
sortData[mid] = hold;
return;
}
void printData (int list[], int compare, int move)
{
/* Local Definitions */
int i = 0;
int lineCount = 0;
/* Statements */
while (i<arySize)
{
if (lineCount < 10)
lineCount++;
else
{
printf("\n");
lineCount = 1;
}
printf("%6d ", list[i]);
i++;
}
printf("\nCompares: %d Moves: %d\n", compare, move);
}
void shellManager (void)
{
/* Local Definitions */
int list[arySize];
int i;
int compare = 0;
int move = 0;
/* Statements */
srand (31);
for (i=0; i<arySize; i++)
list[i] = rand ();
shellSort(list, arySize - 1, &compare, &move);
printData(list, compare, move);
return;
}
void quickManager (void)
{
/* Local Definitions */
int sortData[arySize];
int left; /* first element of the array */
int right; /* last element of the array */
int i;
/* Statements */
srand (31);
for (i=0; i<arySize; i++)
sortData[i] = rand ();
left = 0;
right = arySize - 1;
quickSort (sortData, left, right);
return;
}