Code:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX 10000 //the size of A[] and B[], and the maximum integer value
#define REPEAT 200 //number of times the array is refilled, and resorted
#define SHOW 0 //SHOW = 1 prints the values, in sorted order
#define InsertNum 50 //When the Insertion sort is called for sub array sorting
/* If InsertNum > 60, the times for sorting begin to increase */
void check(int A[], int B[], int choice); //checks accuracy of sort
void countingSort(int A[], int B[]);
void insertion(int A[], int, int);
void quicksortOpt(int A[], int l, int r);
void randomNums(int A[]); //puts random int's into A[] array
void showIt(int A[], int B[], int choice); //shows values
int main(void) {
int i, l, r, choice;
clock_t start, stop;
int A[MAX];
int B[MAX] = { 0 };
l = 0; r = MAX-1;
printf("\n\n\n Name of Algorithm Seconds Sorting %d Integers %d Times", MAX, REPEAT);
printf("\n =========================================================================");
start = clock();
for(i = 0; i < REPEAT; i++) {
randomNums(A);
quicksortOpt(A,l,r); //OK
}
stop = clock();
check(A, B, 0);
printf("\n Quicksort Optimized %7.4f Insertion Threshold is: %d", (stop-start)/CLK_TCK, InsertNum);
if(SHOW) { showIt(A, B, 0); i = getchar(); }
start = clock();
for(i = 0; i < REPEAT; i++) {
randomNums(A);
countingSort(A,B); //OK
}
stop = clock();
check(A, B, 1);
printf("\n Counting Sort %7.4f", (stop-start)/CLK_TCK, InsertNum);
if(SHOW) { showIt(A, B, 1); i = getchar(); }
printf("\n\n\t\t\t press enter when ready");
i = getchar();
return 0;
}
//================ End of Main ============================
/* In this example, 0's are excluded as a valid value */
//Counting Sort
void countingSort(int A[], int B[]) {
int i;
for(i = 0; i < MAX; i++)
if(A[i])
B[A[i]] = A[i];
}
//Insertion sort
void insertion(int A[], int lo, int hi) { //lo and hi are local, not global
int value;
int ohi = hi; //ohi is the original value of hi
for(; lo < ohi; lo++) {
value = A[lo];
hi = lo - 1;
while(A[hi] > value) {
A[hi + 1] = A[hi];
--hi;
if(hi < 0) break;
}
A[hi + 1] = value;
}
}
//Optimzed Quicksort
void quicksortOpt(int A[], int lo, int hi) {
int i, j, pivot, temp;
if(lo == hi) return;
if((hi - lo) < InsertNum) {
insertion(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); //this line works fine.
/* Oddly, on large N, using swap() gives the same time, as
using the swap code below */
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);
}
void randomNums(int A[]) {
int i;
for(i = 0; i < MAX; i++)
A[i] = rand() % MAX;
}
/* checks A[] (0), or B[] (1) , depending on the value of choice */
void check(int A[], int B[], int choice) {
int i;
if(!choice) { //check A's contents directly
for(i = 0; i < MAX - 2; i++) {
if(A[i] > A[i+1]) { //an error
printf("\n\nError!: %d ", A[i]);
return;
}
}
}
else { //check A's contents through the index array
for(i = 0; i < MAX - 2; i++) {
if(B[i] > B[i+1] && B[i+1]) { //an error
printf("\n\nError!: %d ", B[i]);
return;
}
}
}
}
/* shows either A[]'s (0), or B[]'s (1) value, depending on choice */
void showIt(int A[], int B[], int choice) {
int i;
printf("\n\n");
if(!choice) { //regular "direct" display
for(i = 0; i < MAX; i++)
printf("%7d ", A[i]);
}
else {
for(i = 0; i < MAX; i++)
if(B[i] > 0)
printf("%7d ", B[i]);
}
}