Gnome sort je řadící algoritmus podobný insertion sort, ale určený spíše pro pobavení.

Algoritmus je přirozený, stabilní a jeho asymptotická složitost je € O(n^2) €.

Nyní si zkusme představit, jak zahradní trpaslíci řadí květináče podle velikosti.

Trpaslík stojí mezi dvěma květináči a kontroluje, zda jsou správně seřazeny. Pokud ano, posune se o jednu pozici vpřed. Pokud ne, květináče prohodí, a vrátí se o jednu pozici nazpět. Poté trpaslík celý postup opakuje, dokud není řazení dokončeno.

Jaké jsou krajní podmínky? Pokud se trpaslík dostane před první květináč, musí se ihned posunout o jednu pozici vpřed, aby vůbec měl co porovnávat. A jestliže dorazí za květináč poslední, řazení je dokončeno.

Gnome Sort is based on the technique used by the standard Dutch Garden Gnome (tuinkabouter). Here is how a garden gnome sorts a line of flower pots. Basically, he looks at the flower pot next to him and the previous one; if they are in the right order he steps one pot forward, otherwise, he swaps them and steps one pot backward. Boundary conditions: if there is no previous pot, he steps forwards; if there is no pot next to him, he is done. Dick Grune

Implementace (Java)

package sort;

public class GnomeSort {
    /**
     * Implementace algoritmu gnome sort.
     * @param input vstupní pole
     * @author Vojtěch Hordějčuk
     */
    public static <T extends Comparable<? super T>> void gnomeSort(final T[] input) {
        int gnomePosition = 1;

        while (gnomePosition < input.length) {
            if (input[gnomePosition - 1].compareTo(input[gnomePosition]) <= 0) {
                // správné pořadí, posun dopředu
                gnomePosition++;
            } else {
                // špatné pořadí, prohodit prvky, posun dozadu
                final T tmp = input[gnomePosition - 1];
                input[gnomePosition - 1] = input[gnomePosition];
                input[gnomePosition] = tmp;

                if (--gnomePosition == 0) {
                    // odrazit se od konce
                    gnomePosition = 1;
                }
            }
        }
    }
}

Zdrojový kód Pokrytí testy

Ukázkový běh

PolePozice trpaslíkaOperace
(🤠 5) 3 2 40počátek pole - posun vpřed
(5 🤠 3), 2, 41špatné pořadí - prohodit, posun vzad
(🤠 3) 5 2 40počátek pole - posun vpřed
(3 🤠 5) 2 41správné pořadí, posun vpřed
3 (5 🤠 2) 42špatné pořadí - prohodit, posun vzad
(3 🤠 2) 5 41špatné pořadí - prohodit, posun vzad
(🤠 2) 3 5 40počátek pole - posun vpřed
(2 🤠 3) 5 41správné pořadí, posun vpřed
2 (3 🤠 5) 42správné pořadí, posun vpřed
2 3 (5 🤠 4)3špatné pořadí - prohodit, posun vzad
2 (3 🤠 4) 52správné pořadí, posun vpřed
2 3 (4 🤠 5)3správné pořadí, posun vpřed
2 3 4 (5 🤠)4konec pole - řazení dokončeno