Gnome sort je řadící algoritmus, který si zakládá na své jednoduchosti. Základní princip algoritmu je podobný insertion sort, ale gnome sort je navrž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 dopředu. Pokud ne, květináče prohodí, a vrátí se o jednu pozici zpět. Poté se celý postup opakuje od začátku.

Pokud se trpaslík dostane před první květináč, musí se logicky posunout o jednu pozici dopředu, 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 🤠 43špatné pořadí - prohodit, posun vzad
2 3 🤠 4 52správné pořadí, posun vpřed
2 3 4 🤠 53správné pořadí, posun vpřed
2 3 4 5 🤠4konec pole - řazení dokončeno