当前位置: 动力学知识库 > 问答 > 编程问答 >

c++ - Strange algorithm performance when sorting an array (edited)

问题描述:

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)

分享给朋友:
您可能感兴趣的文章:
随机阅读: