Гном сортирует
 | Эта статья нуждается в дополнительных цитатах для проверки . ( август 2010 г. ) |
 Визуализация сортировки Gnome | |
| Сорт | Алгоритм сортировки |
|---|---|
| Структура данных | Множество |
| Худшая производительность | |
| Лучшая производительность | |
| Средняя производительность | |
| Наихудшая пространственная сложность | вспомогательный |
Сортировка Gnome (по прозвищу « тупая сортировка ») — это вариант вставками алгоритма сортировки , который не использует вложенные циклы. Сортировка гномов была первоначально предложена иранским ученым-компьютерщиком Хамидом Сарбази-Азадом (профессором компьютерных наук и инженерии в Технологическом университете Шарифа ). [1] в 2000 году. Впервые сорт назвали глупым сортом. [2] (не путать с bogosort ), а затем позже описан Диком Груном и назван гномской сортировкой . [3]
Сортировка Gnome выполняет по крайней мере столько же сравнений, сколько и сортировка вставками , и имеет те же времени выполнения асимптотические характеристики . Сортировка Gnome работает путем построения отсортированного списка по одному элементу за раз, помещая каждый элемент в нужное место в серии перестановок. Среднее время работы составляет O ( n 2 ), но стремится к O ( n ), если список изначально почти отсортирован. [4] [примечание 1]
Дик Грюн описал метод сортировки следующей историей: [3]
Сортировка гномов основана на технике, используемой стандартным голландским садовым гномом (Du.: tuinkabouter ).
Вот как садовый гном сортирует ряд цветочных горшков .
В основном он смотрит на цветочный горшок рядом с ним и на предыдущий; если они расположены в правильном порядке, он делает шаг на один горшок вперед, в противном случае он меняет их местами и делает шаг назад на один горшок.
Граничные условия: если предыдущего горшка нет, он делает шаг вперед; если рядом с ним нет горшка, он готов.— «Сортировка Gnome — простейший алгоритм сортировки». Dickgrune.com
Псевдокод
[ редактировать ]Вот псевдокод для сортировки gnome с использованием массива с отсчетом от нуля :
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.
| Текущий массив | pos
|
Действующее условие | Действия, которые необходимо предпринять |
|---|---|---|---|
| [ 5 , 3, 2, 4] | 0 | позиция == 0 | увеличить позицию |
| [5, 3 , 2, 4] | 1 | а[поз.] < а[поз.-1] | поменять местами, уменьшить позицию |
| [ 3 , 5, 2, 4] | 0 | позиция == 0 | увеличить позицию |
| [3, 5 , 2, 4] | 1 | а[поз.] ≥ а[поз.-1] | увеличить позицию |
| [3, 5, 2 , 4] | 2 | а[поз.] < а[поз.-1] | поменять местами, уменьшить позицию |
| [3, 2 , 5, 4] | 1 | а[поз.] < а[поз.-1] | поменять местами, уменьшить позицию |
| [ 2 , 3, 5, 4] | 0 | позиция == 0 | увеличить позицию |
| [2, 3 , 5, 4] | 1 | а[поз.] ≥ а[поз.-1] | увеличить позицию |
| [2, 3, 5 , 4] | 2 | а[поз.] ≥ а[поз.-1] | увеличение позиции: |
| [2, 3, 5, 4 ] | 3 | а[поз.] < а[поз.-1] | поменять местами, уменьшить позицию |
| [2, 3, 4 , 5] | 2 | а[поз.] ≥ а[поз.-1] | увеличить позицию |
| [2, 3, 4, 5 ] | 3 | а[поз.] ≥ а[поз.-1] | увеличить позицию |
| [2, 3, 4, 5] | 4 | поз == длина(а) | законченный |
Примечания
[ редактировать ]- ^ Почти отсортировано означает, что каждый элемент в списке находится недалеко от своего правильного положения (не дальше некоторого небольшого постоянного расстояния).
Ссылки
[ редактировать ]- ^ Хамид, Сарбази-Азад. «Профильная страница Хамида Сарбази-Азада» . Архивировано из оригинала 16 октября 2018 г. Проверено 16 октября 2018 г.
- ^ Сарбази-Азад, Хамид (2 октября 2000 г.). «Глупая сортировка: новый алгоритм сортировки» (PDF) . Информационный бюллетень (599). Кафедра компьютерных наук, Univ. Глазго: 4. Архивировано (PDF) из оригинала 7 марта 2012 года . Проверено 25 ноября 2014 г.
- ↑ Перейти обратно: Перейти обратно: а б «Сортировка Gnome — простейший алгоритм сортировки» . Дикгрюн.com . 2000-10-02. Архивировано из оригинала 31 августа 2017 г. Проверено 20 июля 2017 г.
- ^ Пол Э. Блэк. «гномий сорт» . Словарь алгоритмов и структур данных . Национальный институт стандартов и технологий США. Архивировано из оригинала 11 августа 2011 г. Проверено 20 августа 2011 г.
Внешние ссылки
[ редактировать ]