Гномья сортировка (Гномья сортировка.

Алгоритм концептуально простой, не требует вложенных циклов. Время работы . На практике алгоритм может работать так же быстро, как и сортировка вставками.

Алгоритм находит первое место, где два соседних элемента стоят в неправильном порядке и меняет их местами. Он пользуется тем фактом, что обмен может породить новую пару, стоящую в неправильном порядке, только до или после переставленных элементов. Он не допускает, что элементы после текущей позиции отсортированы, таким образом, нужно только проверить позицию до переставленных элементов.

Описание

Ниже написан псевдокод сортировки. Это оптимизированная версия с использованием переменной j, чтобы разрешить прыжок вперёд туда, где он остановился до движения влево, избегая лишних итераций и сравнений:

gnomeSort(a[0..size - 1])
    i = 1;
    j = 2;
    while i < size
        if a[i - 1] <= a[i] //для сортировки по убыванию поменяйте знак сравнения на >=
            i = j;
            j = j + 1;
        else
            swap a[i - 1] and a[i]
            i = i - 1;
            if i == 0
                i = j;
                j = j + 1;

Пример:

Если мы хотим отсортировать массив с элементами [4] [2] [7] [3] от большего к меньшему, то на итерациях цикла while будет происходить следующее:

• [4] [2] [7] [3] (начальное состояние: i == 1, j == 2);
• [4] [2] [7] [3] (ничего не произошло, но сейчас i == 2, j == 3);
• [4] [7] [2] [3] (обмен a[2] и a[1], сейчас i == 1, а j == 3 по-прежнему);
• [7] [4] [2] [3] (обмен a[1] и a[0], сейчас i == 3, j == 4);
• [7] [4] [3] [2] (обмен a[3] и a[2], сейчас i == 2, j == 4);
• [7] [4] [3] [2] (ничего не произошло, но сейчас i == 4, j == 5);
• цикл закончился, т. к. i не < 4.

Оптимизация

Если соптимизировать, то гномья сортировка естественно трансформируется в сортировку вставками. Каждый раз «гном» наталкивается на новый номер, все значения слева от «гнома» уже отсортированы.