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

Иллюстрация действия алгоритма гномьей сортировки

Гномья сортировка (англ. Gnome sort) — алгоритм сортировки, похожий на сортировку вставками, но в отличие от последней перед вставкой на нужное место происходит серия обменов, как в сортировке пузырьком. Название происходит от предполагаемого поведения садовых гномов при сортировке линии садовых горшков, описанного на странице Дика Груна Гномья сортировка.

Гномья сортировка основана на технике, используемой обычным голландским садовым гномом (нидерл. tuinkabouter). Это метод, которым садовый гном сортирует линию цветочных горшков. По существу он смотрит на следующий и предыдущий садовые горшки: если они в правильном порядке, он шагает на один горшок вперёд, иначе он меняет их местами и шагает на один горшок назад. Граничные условия: если нет предыдущего горшка, он шагает вперёд; если нет следующего горшка, он закончил. Дик Грун

Алгоритм концептуально простой, не требует вложенных циклов. Время работы $O\left(n^2\right)$. На практике алгоритм может работать так же быстро, как и сортировка вставками.

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

Описание

Ниже написан псевдокод сортировки. Это оптимизированная версия с использованием переменной 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.

Реализация на С++

template<class T> void GnomeSort(T *A, int N) {
    int i = 0;
    while(i < N) {
        if(i == 0 || A[i - 1] <= A[i]) ++ i;
        else {
            T Temp = A[i];
            A[i] = A[i - 1];
            A[i - 1] = Temp;
            -- i;
        }
    }
}

Оптимизация

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

Ссылки

• Описание метода и листинг программ гномьей сортировки.