Quicksort seltsames Verhalten beim Absteige-aufsteigend Daten

Question

Sortierung Warum diese Implementierung von qs wie unten funktioniert, wenn Array containings Zahlen in absteige-aufsteigend Sortierung (100, 99, .., 0, 99, 100) ?:

time for 50000 elements: 0.123 s 
time for 100000 elements: 0.288 s 
time for 150000 elements: 0.629 s 
time for 200000 elements: 0.695 s 
time for 250000 elements: 1.652 s 
time for 300000 elements: 1.663 s 
time for 350000 elements: 3.404 s 
time for 400000 elements: 4.185 s 
time for 450000 elements: 3.887 s 
time for 500000 elements: 6.73 s 
time for 550000 elements: 8.887 s 
time for 600000 elements: 9.137 s 
time for 650000 elements: 11.094 s 
time for 700000 elements: 8.436 s 
time for 750000 elements: 15.182 s 

Es funktioniert schneller für 700000 Elemente als für 650000 Elemente. Ich wiederholte den Test mehrmals. Hier ist der Code:

#include <iostream> 
    #include <cstdlib> 
    #include <time.h> 
    #include <new> 
    #include <math.h> 

    using namespace std; 
    inline void swap (int *a, int *b) 
    { 
     int tmp; 
     tmp = *a; 
     *a = *b; 
     *b = tmp; 
    } 
    void quick_sort(int tab[], int l, int r); 
    int *allocate (int size); 
    void dec_inc (int tab[], const int length); 
    int main() 
    { 
     int step = 50000; 
     int how_many = 15; 
     int k = 1; 
     int length = step * how_many; 
     int *tab = allocate(length); 
     clock_t t2, t1; 
     long double dif; 
     while (step * k <= length) 
     { 
      dec_inc(tab, step*k); 
      t1 = clock(); 
      quick_sort(tab, 0, step*k - 1); 
      t2 = clock(); 
      dif = (long double)(t2 - t1)/CLOCKS_PER_SEC; 
      cout << "time for " << step * k << " elements: " << dif << " s" << endl; 
      k++; 
     } 
     delete [] tab; 
     system("pause"); 

    } 
    int *allocate (int size) 
    { 
     try 
     { 
      return new int [size]; 
     } 
     catch(bad_alloc) 
     { 
      cerr << "ERROR\n"; 
      exit(EXIT_FAILURE); 
     } 
    } 
    void quick_sort(int tab[], int l, int r) 
    { 
     int v = tab[(l+r)/2]; 
     int i = l; 
     int j = r; 
     do 
     { 
      while(tab[i] < v) i++; 
      while(tab[j] > v) j--; 
      if (i <= j) 
      { 
       swap(&tab[i], &tab[j]); 
       i++, j--; 
      } 
     } 
     while(i <= j); 
     if (l < j) 
      quick_sort(tab, l, j); 
     if(i < r) 
      quick_sort(tab, i, r); 
    } 
    void dec_inc (int tab[], const int length) 
    { 
     int i = length/2; 
     for (int j = 0; j < length/2; j++, i--) 
     { 
      tab[j] = i; 
     } 
     for (int j = length/2; j < length; j++, i++) 
     { 
      tab[j] = i; 
     } 
    } 

Answer 1

Einer der Nachteile von quicksort verwendet, ist seine Stabilität. Bestimmte Datensätze benötigen mehr zu sortierende Schritte als andere. Für pathologische Fälle kann es sogar als O (n^2) skalieren. Ich habe die Anzahl der von Quicksort durchgeführten Vergleiche für Ihre Testdaten gemessen und festgestellt, dass bei 700000 Schritten weniger Vergleiche durchgeführt werden müssen als bei 650000 Elementen. Auch wenn Ihre Datensätze ähnlich aussehen, sind sie es anscheinend nicht für Quicksort. Es gibt Möglichkeiten, QuickSorts Stabilität zu verbessern, siehe zum Beispiel Programming Pearls.

Hier sind die Messungen:

Zeit für 650.000 Elemente: 4,41251 s. Anzahl Vergleiche 5061169826

Zeit für 700000 Elemente: 3,37787 s. Anzahl Vergleiche 3824058435

Zeit für 750000 Elemente: 6,07856 s. Anzahl comparisions 6900645055

Und hier der entsprechende Code: gist