Hi I'm testing the performance of a couple of sorting algorithms when sorting arrays between the size of 2500 to 25000. The two sorts I'm comparing is Gnome Sort and Quick Sort, from what I have read about these the Quick Sort should be a lot faster but the Gnome sort is beating it in every case.

The code for the QuickSort is:

``void myQuickSort(Record sRecord[], int firstElement, int lastElement, bool (*funPoint) (int,int)){int i = firstElement;int j = lastElement;int temp;char tmpname[NAMESIZE];int pivot = sRecord[(firstElement + lastElement) / 2].score;bool (*myPoint)(int,int) = funPoint;while (i <= j){while (sRecord[i].score < pivot){i++;}while (sRecord[j].score > pivot){j--;}if(compareResult(sRecord[j].score,sRecord[i].score) == false){temp = sRecord[i].score;strcpy(tmpname,sRecord[i].name);sRecord[i].score = sRecord[j].score;strcpy(sRecord[i].name,sRecord[j].name);sRecord[j].score = temp;strcpy(sRecord[j].name, tmpname);i++;j--;}if(firstElement < j){myQuickSort(sRecord, firstElement, j, compareResult);}if(i < lastElement){myQuickSort(sRecord, i, lastElement , compareResult);}}}``

and the GnomeSort is as follows:

``void myGnomeSort(Record sRecord[], int size, bool (*funPoint)(int,int)){int pos = size, temp;char tmpname[NAMESIZE];bool (*myPoint)(int,int) = funPoint;while(pos > 0){if (pos == size || myPoint(sRecord[pos].score, sRecord[pos-1].score) == false)pos--;else{temp = sRecord[pos].score;strcpy(tmpname,sRecord[pos].name);sRecord[pos].score = sRecord[pos-1].score;strcpy(sRecord[pos].name,sRecord[pos-1].name);sRecord[pos-1].score = temp;strcpy(sRecord[pos-1].name, tmpname);pos--;}}}``

Can anyone please shed some light onto why there is such a drastic increase when using quicksort (elements with 2.5k and almost 5 times longer).

Thanks for help

Edit: Code used to test is

``Record smallRecord[25000];populateArray(smallRecord, 25000);int startTime = GetTickCount();for(int times = 0; times < NUMOFTIMES; times++){populateArray(smallRecord, 25000);myGnomeSort(smallRecord, 25000, compareResult);cout << times << endl;}int endTime = GetTickCount();float timeMS = ((float) (endTime - startTime)) / 1000;cout << "Time taken: " << timeMS << endl;``

the populate array function just fills the array with random numbers

Actually Quick Sort has a complexity of O(N^2), and it is O(N * logN) in average, not in worst case. So using quick sort is not encouraged because there will always exist such data on which it will work O(N^2)

Top