Незначительная производительность алгоритма при сортировке массива (отредактировано)

Question

Привет, Я тестирую производительность нескольких алгоритмов сортировки при сортировке массивов размером от 2500 до 25000. Эти два вида, которые я сравниваю, это Gnome Sort and Quick Sort , из того, что я прочитал об этом, Quick Sort должен быть намного быстрее, но сорт Gnome бьет его в каждом случае.

Код для QuickSort является:

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); 
    } 
} 
} 

и гномья сортировка выглядит следующим образом:

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--; 

      } 
    } 
} 

Может кто-нибудь, пожалуйста, пролить некоторый свет на почему такое резкое увеличение при использовании быстрой сортировки (элементы с 2.5k и почти в 5 раз дольше).

Спасибо за помощь

Edit: код, используемый для испытания

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; 

функция Заселите массив просто заполняет массив случайными числами

Answer 1

На самом деле Быстрая сортировка имеет сложность O (N^2), и это O (N * logN) в среднем, не в худшем случае. Поэтому использование быстрого сортировки не рекомендуется, потому что всегда будут существовать такие данные, на которых он будет работать O (N^2)