Heapsort - Komplexität der Implementierung

Question

Ich schrieb Heapsort (Cormen). Der Algorithmus sortiert korrekt, aber die Komplexität ist größer als erwartet.

void heap_sort(int tab[], int length) 
{ 
    build_max_heap(tab, length); 
    int heap_size = length; 
    for (int i = length-1; i > 1; i--) 
    { 
     int tmp = tab[1]; 
     tab[1] = tab[i]; 
     tab[i] = tmp; 
     heap_size--; 
     max_heapify(tab, 1, heap_size); 
    } 
} 

void max_heapify (int tab[], int i, int length) 
{ 
    int largest; 
    int l = i * 2; 
    int r = i * 2 + 1; 
    if (l < length and tab[l] > tab[i]) 
     largest = l; 
    else 
     largest = i; 
    if (r < length and tab[r] > tab[largest]) 
     largest = r; 
    if (largest != i) 
    { 
     int tmp = tab[i]; 
     tab[i] = tab[largest]; 
     tab[largest] = tmp; 
     max_heapify(tab, largest, length); 
    } 
} 

void build_max_heap(int tab[], int length) 
{ 
    for (int i = length/2; i >= 1; i--) 
     max_heapify(tab, i, length); 
} 

Für 15000000 Zahlen von rand() erzeugt es dauerte länger als in dieser Implementierung mit Shell sortieren Sortierung:

void shell_sort (int tab[], int length) 
{ 
    int x = 2; 
    int q; 
    do 
    { 
     x*=2; 
     q=2*(length/x) + 1; 
     for(int i = q, val, j; i < length; i++) 
     { 
      val = tab[i]; 
      for(j = i - q ; j >= 0 and tab[j] > val; j-=q) 
      { 
       tab[j + q] = tab[j]; 
      } 
      tab[j + q] = val; 
     } 
    }while (q > 1); 
} 

Test:

HEAPSORT 
Time for 1000000 elements: 0.336 s 
Time for 2000000 elements: 0.732 s 
Time for 3000000 elements: 1.142 s 
Time for 4000000 elements: 1.595 s 
Time for 5000000 elements: 2.034 s 
Time for 6000000 elements: 2.513 s 
Time for 7000000 elements: 3.023 s 
Time for 8000000 elements: 3.51 s 
Time for 9000000 elements: 4.02 s 
Time for 10000000 elements: 4.558 s 
Time for 11000000 elements: 5.095 s 
Time for 12000000 elements: 5.595 s 
Time for 13000000 elements: 6.183 s 
Time for 14000000 elements: 6.7 s 
Time for 15000000 elements: 7.367 s 

SHELLSORT 
Time for 1000000 elements: 0.343 s 
Time for 2000000 elements: 0.779 s 
Time for 3000000 elements: 1.182 s 
Time for 4000000 elements: 1.654 s 
Time for 5000000 elements: 2.218 s 
Time for 6000000 elements: 2.672 s 
Time for 7000000 elements: 3.34 s 
Time for 8000000 elements: 3.778 s 
Time for 9000000 elements: 4.297 s 
Time for 10000000 elements: 4.903 s 
Time for 11000000 elements: 4.872 s 
Time for 12000000 elements: 5.514 s 
Time for 13000000 elements: 6.29 s 
Time for 14000000 elements: 6.994 s 
Time for 15000000 elements: 7.121 s 

ich die Test viele Male wiederholt. Was stimmt nicht mit dem Algorithmus?

Answer 1

Erste Note, große O und rohe Leistung haben eine komplizierte Beziehung. Im Fall von Heapsort führt eine schlechte Speicherlokalität dazu, dass es auf Computern schlechter skaliert, als es Big-O vermuten lässt. Im Gegensatz dazu ist die Shell-Sortierung nur sehr geringfügig schlechter als O(n log(n)) und die meisten ihrer Pässe haben eine ordentliche Speicherstelle.

Ich bin daher nicht überrascht, dass sie vergleichbar sind.

Das heißt, Sie könnten versuchen, max_heapify aus einer rekursiven Funktion in eine Schleife zu verwandeln. Das kann eine gewisse Stapelmanipulation vermeiden.