Code:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define INSERT 64
#define SIZE 100000
void bubbleSort(void);
int checkIt(void);
void insertionSort(int lo, int hi);
void quicksortOpt(int lo, int hi, int optimal);
void fillArray(void);
void shellSort(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;
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();
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();
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();
quicksortOpt(0,SIZE-1, 0);
stop=clock();
printf(" 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, 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();
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;
}
//Standard and Optimized Quicksort
void quicksortOpt(int lo, int hi, int optimal) {
int i, j, pivot;
if(lo == hi) return;
if(optimal && (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,optimal);
if (i < hi) quicksortOpt(i, hi,optimal);
}
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 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;
}
}
//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;
}