Shell sort

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie

Shell sort je kvadratický triediaci algoritmus podobný insertion sortu. Aj keď má tiež zložitosť O(n^2), tak je z algoritmov tohoto typu nevýkonnejší.

Algoritmus[upraviť | upraviť zdroj]

Tento kód je napísaný v programovacom jazyku C++.

int * shellSort(int * array, int size) {
   int gap = size / 2;
   while (gap > 0) { //dokud mame co porovnavat
       for (int i = 0; i < size - gap; i++) { //upraveny insertion sort
           int j = i + gap;
           int tmp = array[j];
           while (j >= gap && tmp > array[j - gap]) {
               array[j] = array[j - gap];
               j -= gap;
           }
           array[j] = tmp;
       }
       if (gap == 2) { //zmena velikosti mezery
           gap = 1;
       } else {
           gap /= 2.2;
       }
   }
   return array;
}