Сортировка гномов - Gnome sort


Сортировка гномов
Сортировка gnomesort anim.gif
Визуализация сортировки Gnome.
Учебный классАлгоритм сортировки
Структура данныхМножество
Худший случай спектакль
Лучший случай спектакль
Средний спектакль
Худший случай космическая сложность вспомогательный

Сортировка гномов (дублированный глупый вид) это алгоритм сортировки первоначально предложенный Иранский специалист в области информатики Хамид Сарбази-Азад (профессор компьютерных наук и инженерии в Технологический университет Шарифа )[1] в 2000 году. Впервые сорт был назван глупый вид[2] (не путать с Богосорт ), а затем описан позже Дик Грюн и назвал гномья сортировка.[3]

Сортировка gnome - это алгоритм сортировки, который похож на вставка сортировки в том, что он работает с одним элементом за раз, но перемещает элемент в нужное место серией обменов, аналогично пузырьковая сортировка. Это концептуально просто, не требует вложенные циклы. Среднее время работы составляет О (п2) но стремится к О(п), если список изначально почти отсортирован.[4][примечание 1]

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

Описание

Дик Грюн описал метод сортировки следующей историей:[3]

Gnome Sort основан на методе, используемом в стандартной голландской Садовый гном (Du .: Tuinkabouter ).
Вот как садовый гном сортирует линию цветочные горшки.
В основном он смотрит на горшок рядом с ним и предыдущий; если они расположены в правильном порядке, он продвигает один горшок вперед, в противном случае он меняет их местами и шагает один горшок назад.
Граничные условия: если предыдущего банка нет, он выходит вперед; если рядом с ним нет горшка, он готов.

— "Сортировка Gnome - Простейший алгоритм сортировки". Dickgrune.com

Код

Вот это псевдокод для сортировки гномов с использованием массив с отсчетом от нуля:

процедура gnomeSort (a []): pos: = 0 while pos  = a [pos-1]): pos: = pos + 1 else: swap a [pos] и a [pos-1] pos: = pos - 1

Пример

Учитывая несортированный массив, a = [5, 3, 2, 4], сортировка gnome выполняет следующие шаги во время цикла while. Текущая позиция выделена жирным шрифтом и указана как значение переменной позиция.

Текущий массивпозицияДействующее состояниеДействия, которые необходимо предпринять
[5, 3, 2, 4]0pos == 0инкремент поз
[5, 3, 2, 4]1a [pos] своп, декремент поз
[3, 5, 2, 4]0pos == 0инкремент поз
[3, 5, 2, 4]1a [pos] ≥ a [pos-1]инкремент поз
[3, 5, 2, 4]2a [pos] своп, декремент поз
[3, 2, 5, 4]1a [pos] своп, декремент поз
[2, 3, 5, 4]0pos == 0инкремент поз
[2, 3, 5, 4]1a [pos] ≥ a [pos-1]инкремент поз
[2, 3, 5, 4]2a [pos] ≥ a [pos-1]приращение позиции:
[2, 3, 5, 4]3a [pos] своп, декремент поз
[2, 3, 4, 5]2a [pos] ≥ a [pos-1]инкремент поз
[2, 3, 4, 5]3a [pos] ≥ a [pos-1]инкремент поз
[2, 3, 4, 5]4поз == длина (а)законченный

Оптимизация

Сортировку gnome можно оптимизировать, введя переменную для хранения позиции перед возвратом к началу списка. С этой оптимизацией сортировка gnome станет вариантом вставка сортировки.

Вот это псевдокод для оптимизированной сортировки гномов с использованием массив с отсчетом от нуля:

1 процедура optimizedGnomeSort (a []):2     для pos в 1 к длине (a):3         gnomeSort (a, pos)4 5 процедура gnomeSort (a [], upperBound):6     pos: = upperBound7     в то время как pos> 0 и a [pos-1]> a [pos]:8         поменять местами [pos-1] и [pos]9         pos: = pos - 1

Примечания

  1. ^ Почти отсортировано означает, что каждый элемент в списке находится недалеко от своего надлежащего положения (не дальше некоторого небольшого постоянного расстояния).

Рекомендации

  1. ^ Хамид, Сарбази-Азад. "Профильная страница Хамида Сарбази-Азада". В архиве из оригинала на 2018-10-16. Получено 16 октября, 2018.
  2. ^ Сарбази-Азад, Хамид (2 октября 2000 г.). «Глупая сортировка: новый алгоритм сортировки» (PDF). Новостная рассылка. Отдел вычислительной науки, Univ. Глазго (599): 4. Архивировано из оригинал (PDF) 7 марта 2012 г.. Получено 25 ноября 2014.
  3. ^ а б "Сортировка Gnome - простейший алгоритм сортировки". Dickgrune.com. 2000-10-02. В архиве из оригинала 31.08.2017. Получено 2017-07-20.
  4. ^ Пол Э. Блэк. "гномья сортировка". Словарь алгоритмов и структур данных. Национальный институт стандартов и технологий США. В архиве из оригинала 2011-08-11. Получено 2011-08-20.

внешняя ссылка