Code:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>
#define SIZE 50000
#define InsertNum 50
#define TestNum 10
void bubbleSort(int a[], int);
int checkIt(int a[], int);
void insertionSort(int a[], int lo, int hi);
int loadData(int a[], int);
void print(int [], int, int);
void quickSort(int a[], int, int);
void quickSortOpt(int a[], int, int);
void shellSort(int a[], int);
void substitutionSort(int a[], int);
int main(void) {
int *a, hi=0, OK, type=0;
clock_t start, stop;
a = malloc(SIZE * sizeof(int));
printf("Array[SIZE] is %d, and INT_MAX is %d\n", SIZE, INT_MAX);
hi = loadData(a, type);
if(!hi) {
printf("No data was loaded from the file\n");
return 0;
}
OK = checkIt(a, hi);
//getchar();
printf("\n\t\tStart Sorting Test Run\n\t\t======================\n");
printf(" Bubble Sort: ");
start = clock();
bubbleSort(a, hi);
stop = clock();
printf("%7.3lf\n", (double) (stop-start)/CLOCKS_PER_SEC);
if((OK = checkIt(a, hi)) == 0) {
printf(" Sorting Error!\n");
getchar();
return 0;
}
hi = loadData(a, type);
if(!hi)
return 0;
printf(" Insertion Sort: ");
start = clock();
insertionSort(a, 0, hi);
stop = clock();
printf("%7.3lf\n", (double)(stop-start)/CLOCKS_PER_SEC);
if((OK = checkIt(a, hi)) == 0) {
printf(" Sorting Error!\n");
getchar();
return 0;
}
hi = loadData(a, type);
if(!hi)
return 0;
printf(" Quicksort, Unoptimized: ");
start = clock();
quickSort(a, 0, hi);
stop = clock();
printf("%7.3lf\n", (double)(stop-start)/CLOCKS_PER_SEC);
if((OK = checkIt(a, hi)) == 0) {
printf(" Sorting Error!\n");
getchar();
return 0;
}
hi = loadData(a, type);
if(!hi)
return 0;
printf(" Quicksort, Optimized: ");
start = clock();
quickSortOpt(a, 0, hi);
stop = clock();
printf("%7.3lf\n", (double)(stop-start)/CLOCKS_PER_SEC);
if((OK = checkIt(a, hi)) == 0) {
printf(" Sorting Error!\n");
return 0;
}
hi = loadData(a, type);
if(!hi)
return 0;
printf(" Shell Sort, Unoptimized: ");
start = clock();
shellSort(a, hi);
stop = clock();
printf("%7.3lf\n", (double)(stop-start)/CLOCKS_PER_SEC);
if((OK = checkIt(a, hi)) == 0) {
printf(" Sorting Error!\n");
return 0;
}
hi = loadData(a, type);
if(!hi)
return 0;
printf(" Substitution Sort: ");
start = clock();
substitutionSort(a, hi);
stop = clock();
printf("%7.3lf\n", (double)(stop-start)/CLOCKS_PER_SEC);
if((OK = checkIt(a, hi)) == 0) {
printf(" Sorting Error!\n");
return 0;
}
free(a);
putchar('\n');
return 0;
}
void bubbleSort(int a[], int hi) {
int i, n, temp, swapped;
n = hi;
do {
swapped = 0;
for(i =0; i < n-1; i++) {
if(a[i] > a[i + 1 ]) {
temp = a[i];
a[i] = a[i + 1];
a[i + 1] = temp;
swapped = 1;
}
} //end for
--n;
}while(swapped);
}
int checkIt(int a[], int hi) {
int i, count = 0, OK=1;
static int first = 1;
for(i=0;i<hi-1;i++) {
if(a[i] > a[i+1]) {
++count;
OK=0;
}
}
if(first) {
printf(" %d numbers are out of order\n", count);
first = 0;
//getchar();
}
return OK;
}
void insertionSort(int a[], int lo, int hi) {
int i, j, val;
for(i=lo+1;i<hi;i++) {
val = a[i];
j = i-1;
while(a[j] > val) {
a[j + 1] = a[j];
--j;
if(j<0) break;
}
a[j+1] = val;
}
/*
puts("\nAfter Insertion Sort:\n");
for(i=lo;i<lo + 10;i++)
printf(" %5d ", a[i]);
getchar();
exit(0);
*/
}
int loadData(int a[], int type) {
int i, OK;
char buffer[100];
if(type) {
;
}else {
srand(1);
for(i=0;i<SIZE;i++) {
a[i] = rand() % SIZE;
}
}
return i;
}
void print(int a[], int lo, int hi) {
int i;
for(i=0;i<TestNum;i++) {
printf(" %5d ",a[i]);
}
}
//Quicksort w/o a separate compare function :)
void quickSort(int a[], int lo, int hi) {
int i, j, pivot, temp;
if(lo == hi) return;
i=lo;
j=hi;
pivot= a[(lo+hi)/2];
/* Split the array into two parts */
do {
while (a[i] < pivot) i++;
while (a[j] > pivot) j--;
if (i<=j) { //without the = in there, it's an endless loop
temp= a[i];
a[i]= a[j];
a[j]=temp;
i++;
j--;
}
}while (i<=j);
if (lo < j) quickSort(a, lo, j);
if (i < hi) quickSort(a, i, hi);
}
//Optimzed Quicksort
void quickSortOpt(int a[], int lo, int hi) {
int i, j, pivot, temp;
if(lo == hi) return;
if((hi - lo) < InsertNum) {
insertionSort(a, lo, hi+1);
return;
}
i=lo;
j=hi;
pivot= a[(lo+hi)/2];
/* Split the array into two parts */
do {
while (a[i] < pivot) i++;
while (a[j] > pivot) j--;
if (i<=j) {
//swap(A, i, j);
temp= a[i];
a[i]= a[j];
a[j]=temp;
++i;
--j;
}
} while(i<=j);
if (lo < j) quickSortOpt(a, lo, j);
if (i < hi) quickSortOpt(a, i, hi);
}
//Shell sort Brand new, not optimized
void shellSort(int a[], int hi) {
int i, j, gap, temp;
for(gap = hi/2; gap > 0; gap /= 2) { //original Shell divisor
for(i = gap; i < hi; i++) {
temp = a[i];
j = i;
while(j>= gap && a[j-gap] > temp) {
a[j] = a[j - gap];
j = j - gap;
}
a[j] = temp;
}
}
}
//Substitution Sort:
void substitutionSort(int a[], int hi) {
int i, j, temp;
for(i = 0; i < hi-1; i++) {
for(j = i + 1; j < hi; j++) {
if(a[i] > a[j]) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
}