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ší.
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;
}