Shell sort

Tomuto článku alebo sekcii chýbajú odkazy na spoľahlivé zdroje, môže preto obsahovať informácie, ktoré je potrebné ešte overiť. Pomôžte Wikipédii a doplňte do článku citácie, odkazy na spoľahlivé zdroje.

Tento článok si vyžaduje rozšírenie, aby zodpovedal základnému štandardu kvality. Pozrite si stránky z kategórie návody a štýl, prípadne diskusiu k článku a článok, prosím, doplňte.

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

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