Shell sort

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

Kategória:Triediacie algoritmy