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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Иллюстрация действия алгоритма гномьей сортировки

Гномья сортировка (англ. 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.

Оптимизация[править | править исходный текст]

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

Ссылки[править | править исходный текст]