Code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define INSERT 64
#define SIZE 100000
void binaryInsertion(void);
void bubbleSort(void);
int checkIt(void);
void insertionSort(int lo, int hi);
void middle1(int lo, int hi);
void quicksortOpt(int lo, int hi);
void quicksortIter(void);
void quicksortRecursive(int lo, int hi);
void fillArray(void);
void shellSort(void);
void selectionSort(void);
void swap(int i, int j);
int A[SIZE]={0};
unsigned long long int SWAPS=0;
int TYPE=0;
int main(void) {
int i,j;
char type[3][11]={{"random"},{"ascending"},{"descending"}};
clock_t start,stop;
srand(time(NULL));
for(j=0;j<3;j++) {
TYPE=j;
fillArray();
printf("\nSorting %d integers, initially in %s order. The first 10 numbers:\n\n",SIZE,type[TYPE]);
for(i=0;i<10;i++) printf("%6d ",A[i]);
printf("\n");
/*
SWAPS=0;
start=clock();
binaryInsertion();
stop=clock();
printf(" Binary Insertion: %15llu swaps in %10.4f seconds\n",SWAPS,(double)(stop-start)/CLOCKS_PER_SEC);
if(checkIt());
*/
/*
SWAPS=0;
start=clock();
bubbleSort();
stop=clock();
printf(" Bubble sort: %15llu swaps in %10.4f seconds\n",SWAPS,(double)(stop-start)/CLOCKS_PER_SEC);
if(checkIt());
SWAPS=0;
fillArray();
start=clock();
middle1(0,SIZE);
stop=clock();
printf(" Middle1 sort: %15llu swaps in %10.4f seconds\n",SWAPS,(double)(stop-start)/CLOCKS_PER_SEC);
if(checkIt());
SWAPS=0;
fillArray();
start=clock();
insertionSort(0,SIZE);
stop=clock();
printf(" Insertion sort: %15llu swaps in %10.4f seconds\n",SWAPS,(double)(stop-start)/CLOCKS_PER_SEC);
if(checkIt());
*/
SWAPS=0;
fillArray();
start=clock();
quicksortIter();
stop=clock();
printf(" Iterative Quicksort: %15llu swaps in %10.4f seconds\n",SWAPS,(double)(stop-start)/CLOCKS_PER_SEC);
if(checkIt());
SWAPS=0;
fillArray();
start=clock();
quicksortOpt(0,SIZE-1);
stop=clock();
printf(" Optimized Quicksort: %15llu swaps in %10.4f seconds\n",SWAPS,(double)(stop-start)/CLOCKS_PER_SEC);
if(checkIt());
SWAPS=0;
fillArray();
start=clock();
quicksortRecursive(0,SIZE-1);
stop=clock();
printf(" Recursive Quicksort: %15llu swaps in %10.4f seconds\n",SWAPS,(double)(stop-start)/CLOCKS_PER_SEC);
if(checkIt());
/*
SWAPS=0;
fillArray();
start=clock();
selectionSort();
stop=clock();
printf(" Selection sort: %15llu swaps in %10.4f seconds\n",SWAPS,(double)(stop-start)/CLOCKS_PER_SEC);
if(checkIt());
*/
SWAPS=0;
fillArray();
start=clock();
shellSort();
stop=clock();
printf(" Shell sort: %15llu swaps in %10.4f seconds\n\n",SWAPS,(double)(stop-start)/CLOCKS_PER_SEC);
if(checkIt());
}
for(i=0;i<10;i++)
printf("%6d ",A[i]);
printf("\n");
return 0;
}
//Binary Insertion Sort Has a subtle error in it - sorts correctly
//but overwrites SWAPS++ for Bubble sort.
void binaryInsertion(void)
{
register int i, m;
int n=SIZE,hi, lo, tmp;
for (i = 1; i < n; i++) {
lo = 0, hi = i;
m = i / 2;
do {
if (A[i] > A[m]) {
lo = m + 1;
} else if (A[i] < A[m]) {
hi = m;
} else
break;
m = lo + ((hi - lo) / 2);
} while (lo < hi);
if (m < i) {
tmp = A[i];
memmove (A + m + 1, A + m, sizeof (int) * (i - m));
A[m] = tmp;
SWAPS++;
}
}
}
void bubbleSort() {
int i, n, swapped;
n = SIZE-1;
do {
swapped = 0;
for(i =0; i < n; i++) {
if(A[i] > A[i + 1 ]) {
swap(i, i + 1);
++SWAPS;
swapped = 1;
}
}
--n;
}while(swapped);
}
void middle1(int lo, int hi) {
int i,j,temp;
for(i=hi-1;i>-1;i--) {
for(j=0;j<i;j++) {
if(A[j] > A[i]) {
temp=A[j];
A[j]=A[i];
A[i]=temp;
++SWAPS;
}
}
}
}
void insertionSort(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];
++SWAPS;
--j;
if(j<0)
break;
}
A[j+1] = val;
}
}
//Quicksort, Iterative
void quicksortIter(void) {
int I, J, left, right, stack, pivot,maxStack=0;
int ST[64] = { 0 }; //uses ~20 with N=25,000 and range of 0-999
left = stack = 0; right = SIZE-1;
while(1) {
while(left >= right) { //better with the >=
if(stack != 0) {
right = ST[stack];
left = ST[stack - 1];
stack -= 2;
}
else { //if T0 == 0, we're done sorting
printf("maxstack: %d \n",maxStack);
return; //not break
}
}
pivot = A[left];
I = left+1; //forward loop counter
J = right+1; //backward loop counter
/* these iterators are touchy */
do {
while(A[--J] > pivot);
while(A[I] < pivot) ++I;
if(J > I) {
swap(I, J);
++SWAPS;
}
}while(J > I);
A[left] = A[J];
A[J] = pivot;
if((J - left) < (right - J)) //take the smallest sub array first
ST[stack + 1] = J + 1;
if(ST[stack + 1] == J + 1) {
ST[stack + 2] = right;
right = J - 1;
}
else {
ST[stack + 1] = left;
ST[stack + 2] = J - 1;
left = J + 1;
}
stack = stack + 2; //push onto ST[]
if(stack > maxStack) maxStack = stack; //debug aid
}
}
//Optimized Quicksort
void quicksortOpt(int lo, int hi) {
int i, j, pivot;
if(lo == hi) return;
if(hi - lo < INSERT) { //The optimizer. Value of
insertionSort(lo, hi+1); //INSERT will vary
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(i, j); //this line works fine.
SWAPS++;
i++;
j--;
}
} while(i<=j);
if (lo < j) quicksortOpt(lo, j);
if (i < hi) quicksortOpt(i, hi);
}
//Good but unoptimized, Quicksort
void quicksortRecursive(int lo, int hi) {
int i, j, pivot;
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) {
swap(i, j); //this line works fine.
SWAPS++;
i++;
j--;
}
} while(i<=j);
if (lo < j) quicksortOpt(lo, j);
if (i < hi) quicksortOpt(i, hi);
}
void selectionSort()
{
int i,j,n=SIZE,min;
for(i = 0; i < n-1; i++) {
min = i; //set min to the firt index
for(j = i+1; j < n; j++) {
if (A[j] < A[min]) {
min = j;
}
}
if( min != i ) {
swap(i, min);
SWAPS++;
}
}
}
//Shell sort
void shellSort(void) {
int i, j, gap, temp;
for(gap = SIZE/2; gap > 0; gap /= 2) {
for(i = gap; i < SIZE; i++) {
for(j = i - gap; j >= 0 && A[j] > A[j + gap]; j -= gap) {
++SWAPS;
temp = A[j];
A[j] = A[j + gap];
A[j + gap] = temp;
}
}
}
}
void swap(int i, int j) {
int temp;
temp = A[i];
A[i] = A[j];
A[j] = temp;
}
void fillArray(void) {
int i,j;
if(TYPE==0) { //random order
for(i = 0; i < SIZE; i++)
A[i] = (rand() % 10000)+1;
}else if(TYPE==1) { //ascending order
for(i=0;i<SIZE;i++)
A[i]=i;
}else if(TYPE==2) { //descending order
for(j=0,i=SIZE-1;i>=0;i--,j++)
A[j]=i;
}
}
int checkIt(void) {
int i;
for(i=0;i<SIZE-1;i++) {
if(A[i]>A[i+1]) {
printf("Error! Not sorted in ascending order.\n");
return 1;
}
}
return 0;
}