Сорт гномов - Gnome sort
 Визуализация оптимизированной сортировки Gnome.
| |
| Класс | Алгоритм сортировки |
|---|---|
| Структура данных | Множество |
| Наихудшая производительность | |
| Лучшая производительность | |
| Средняя производительность | |
| Сложность пространства в наихудшем случае | вспомогательный |
Gnome рода (дублированный глупы рода ) является алгоритм сортировки , первоначально предложенный иранский ученый Хамид Sarbazi-Азада (профессор компьютерных наук и инженерии в Sharif технологическом университете ) в 2000 году сорт был первым назвал глупым рода (не следует путать с bogosort ), а затем описан Диком Грюном и назван gnome sort .
Сортировка gnome - это алгоритм сортировки, который похож на сортировку вставкой в том, что он работает с одним элементом за раз, но перемещает элемент в нужное место серией перестановок, подобно пузырьковой сортировке . Это концептуально просто, не требует вложенных циклов . Среднее время выполнения составляет O ( n 2 ), но имеет тенденцию к O ( n ), если список изначально почти отсортирован.
Алгоритм находит первое место, где два соседних элемента расположены в неправильном порядке, и меняет их местами. Он использует преимущество того факта, что выполнение обмена может привести к появлению новой неупорядоченной смежной пары рядом с ранее замененными элементами. Он не предполагает, что элементы, расположенные впереди текущей позиции, сортируются, поэтому ему нужно только проверить позицию непосредственно перед заменяемыми элементами.
Описание
Дик Грюн описал метод сортировки следующей историей:
Сортировка Gnome основана на технике, используемой стандартным голландским садовым гномом (Du: tuinkabouter ).
Вот как садовый гном сортирует ряд цветочных горшков .
В основном он смотрит на горшок рядом с ним и предыдущий; если они расположены в правильном порядке, он продвигает один горшок вперед, в противном случае он меняет их местами и отступает на один горшок назад.
Граничные условия: если предыдущего банка нет, он выходит вперед; если рядом с ним нет горшка, он готов.- «Сортировка Gnome - Простейший алгоритм сортировки». Dickgrune.com
Код
Вот псевдокод для сортировки гномов с использованием массива с нулевым отсчетом :
procedure gnomeSort(a[]):
pos := 0
while pos < length(a):
if (pos == 0 or a[pos] >= a[pos-1]):
pos := pos + 1
else:
swap a[pos] and a[pos-1]
pos := pos - 1
Пример
Учитывая несортированный массив, a = [5, 3, 2, 4], сортировка gnome выполняет следующие шаги во время цикла while. Текущая позиция выделена жирным шрифтом и указана как значение переменной pos.
| Текущий массив | позиция | Действующее состояние | Действия, которые необходимо предпринять |
|---|---|---|---|
| [ 5 , 3, 2, 4] | 0 | pos == 0 | инкремент поз |
| [5, 3 , 2, 4] | 1 | a [pos] <a [pos-1] | своп, декремент поз |
| [ 3 , 5, 2, 4] | 0 | pos == 0 | инкремент поз |
| [3, 5 , 2, 4] | 1 | a [pos] ≥ a [pos-1] | инкремент поз |
| [3, 5, 2 , 4] | 2 | a [pos] <a [pos-1] | своп, декремент поз |
| [3, 2 , 5, 4] | 1 | a [pos] <a [pos-1] | своп, декремент поз |
| [ 2 , 3, 5, 4] | 0 | pos == 0 | инкремент поз |
| [2, 3 , 5, 4] | 1 | a [pos] ≥ a [pos-1] | инкремент поз |
| [2, 3, 5 , 4] | 2 | a [pos] ≥ a [pos-1] | приращение позиции: |
| [2, 3, 5, 4 ] | 3 | a [pos] <a [pos-1] | своп, декремент поз |
| [2, 3, 4 , 5] | 2 | a [pos] ≥ a [pos-1] | инкремент поз |
| [2, 3, 4, 5 ] | 3 | a [pos] ≥ a [pos-1] | инкремент поз |
| [2, 3, 4, 5] | 4 | поз == длина (а) | законченный |
Оптимизация
Сортировку gnome можно оптимизировать, введя переменную для хранения позиции перед возвратом к началу списка. С этой оптимизацией сортировка gnome станет вариантом сортировки вставкой .
Вот псевдокод для оптимизированной сортировки гномов с использованием массива с нулевым отсчетом :
procedure optimizedGnomeSort(a[]):
for pos in 1 to length(a):
gnomeSort(a, pos)
procedure gnomeSort(a[], upperBound):
pos := upperBound
while pos > 0 and a[pos-1] > a[pos]:
swap a[pos-1] and a[pos]
pos := pos - 1