Shell sort

Shell sort (Shellovo řazení, řazení se snižujícím se přírůstkem) je kvadratický řadící algoritmus podobný insertion sortu. Ačkoliv má asymptotickou složitost $Ο(n^{2})$ , tak je z algoritmů této třídy nejvýkonnější.

Princip

Běžný insertion sort si uchovává seznam již seřazených prvků. V každém svém kroku zařadí do seznamu prvek, který s tímto seznamem přímo sousedí. Opakováním tohoto postupu od triviálního případu (seznam čítající pouze první prvek) algoritmus seřadí pole za iterací.

Shell sort funguje obdobně. Základním rozdílem však je, že Shell sort využívá tzv. snižující se přírůstek. To znamená, že algoritmus neřadí prvky, které jsou přímo vedle sebe, ale prvky, mezi nimiž je určitá mezera (tj. první a pátý, pátý a devátý, druhý a šestý...). V každém kroku je pak mezera mezi prvky zmenšena. V okamžiku, kdy se velikost mezery sníží na 1, dojde k řazení sousedních prvků – algoritmus degeneruje na běžný insertion sort. Výhodou tohoto poněkud komplikovaného přístupu je, že jsou prvky vysokých a nízkých hodnot velmi rychle přemístěny na odpovídající stranu pole. Poslední iterace algoritmu (insertion sort) pak již přesouvá naprosté minimum prvků.

Ideální mezera

Základním problémem je ovšem volba ideální vzdálenosti pro porovnávání jednotlivých prvků. Donald Shell (autor algoritmu) původně navrhoval, aby se začínalo na n/2 (n je velikost pole) a vzdálenost se vždy půlila. Tento přístup má ovšem tu nevýhodu, že se prvky na sudých a lichých místech porovnávají až v posledním kroku algoritmu. Dalšími pokusy byly například posloupnosti 2^k - 1 (Hibbard) se složitostí $Ο(n^{3/2})$ nebo $9 \\cdot 4^{i} \\, - \\, 9 \\cdot 2^{i}$ (Sedgewick) se složitostí $Ο(n^{4/3})$ , případně Fibonacciho posloupnost umocněná na dvojnásobek zlatého řezu.

Nejlepší výsledky ovšem podává posloupnost 1, 4, 10, 23, 57, 132, 301, 701, 1750, dále $mezera \\cdot 2.2$ , jejímž autorem je Marcin Ciura.

Vizualizace

Kód

/**
 * Shell sort - Shellovo razeni - razeni se snizujicim se prirustkem (od nejvyssiho)
 * @param array pole k serazeni
 * @return serazene pole
 */
public static int[] shellSort(int[] array) {
    int gap = array.length / 2;
    while (gap > 0) { //dokud mame co porovnavat
        for (int i = 0; i < array.length - 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;
}

/**
 * Shell sort - Shellovo razeni - razeni se snizujicim se prirustkem (od nejvyssiho)
 * @param array pole k serazeni
 * @param size velikost pole
 * @return serazene pole
 */
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;
}

/**
 * Shell sort - Shellovo razeni - razeni se snizujicim se prirustkem (od nejvyssiho)
 * @param array pole k serazeni
 * @return serazene pole
 */
public static int[] ShellSort(int[] array)
{
    int gap = array.Length / 2;
    while (gap > 0) //dokud mame co porovnavat
    { 
        for (int i = 0; i < array.Length - 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 = (int)(gap / 2.2);
        }
    }
    return array;
}

Princip

Ideální mezera

Vizualizace

Kód

Doporučujeme