N^2 sort comparison
Gnome sort was marginally faster than Bubble sort (so, no reason ever to use Bubble sort), but Insertion sort was twice as fast as gnome sort, IIRC.
Oh yeah, my srand value was stupid. Don't mind that.
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#define NUM_ITEMS 15000
#define RUNS 3
void gnomeSort(int arr[], int n);
void bubbleSort(int arr[], int n);
void insertionSort(int arr[], int n);
typedef void (*Sort)(int arr[], int n);
int numbers[NUM_ITEMS];
int runtimes[RUNS];
int main(){
int i, j, k;
long start, end, avg;
Sort funcs[] = {bubbleSort, gnomeSort, insertionSort};
char* func_names[] = {"bubble", "gnome", "insertion"};
for(k=0; k<3; k++){
printf("Starting %s sort\n", func_names[k]);
for(j=0; j<RUNS; j++){
//printf("Seeding random number generator\n");
srand(clock()+getpid()); //seed random number generator
//printf("Filling random numbers\n");
for (i=0; i<NUM_ITEMS; i++)
numbers[i] = rand(); //fill array with random integers
start = clock();
//printf("Clock ticks before %s sort: %d\n", func_names[k], start);
funcs[k](numbers, NUM_ITEMS); //perform gnome sort on array
end = clock();
//printf("Clock ticks after %s sort: %d\n", func_names[k], end);
//printf("Total ticks: %d\n", end-start);
runtimes[j] = end-start;
}
printf("\nDone with %s sort. Runtimes are:\n", func_names[k]);
for (i=0; i<RUNS; i++)
printf("%i\n", runtimes[i]);
printf("\nAverage time is: ");
avg = 0;
for(i=0; i<RUNS; i++){
avg+=runtimes[i];
}
printf("%d\n\n", avg/RUNS);
}
}
void gnomeSort(int arr[], int n) {
int i=0, temp;
while(i < n) {
if(i == 0 || arr[i-1] <= arr[i]) i++;
else{
temp = arr[i];
arr[i] = arr[i-1];
arr[--i] = temp;
}
}
}
void bubbleSort(int arr[], int n){
int i, j, temp;
for(i=n-1; i>0; i--){
for(j=1; j<=i; j++){
if(arr[j-1] > arr[j]){
temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
}
}
void insertionSort(int arr[], int n){
int i, j, current;
for(i=1; i<n; i++){
current = arr[i];
for(j=i; j>0 && arr[j-1] > current; j--)
arr[j] = arr[j-1];
arr[j] = current;
}
}
Page last edited: November 29, 2005 (utc)
|
