Гномья сортировка (Stone Sort)
Очень простой алгоритм с одним циклом. Работает как садовый гном, расставляющий цветочные горшки: если текущий горшок стоит правильно — идёт вперёд, если нет — меняет местами с предыдущим и отступает назад.
Идея алгоритма
- Начинаем с позиции 1
- Если текущий элемент не меньше предыдущего — всё хорошо, идём вперёд
- Если текущий меньше предыдущего — меняем их местами и отступаем на шаг назад
- Если отступили до начала — идём вперёд
- Когда дошли до конца — массив отсортирован
Разбор
Весь алгоритм укладывается в один цикл пока:
алг stonesort(цел n, цел таб A[0:n-1])
нач
цел i, tmp
i := 1
нц пока i < n
если i = 0 то
i := 1
иначе
если A[i] >= A[i - 1] то
i := i + 1
иначе
tmp := A[i]
A[i] := A[i - 1]
A[i - 1] := tmp
i := i - 1
все
все
кц
кон
i = 0— отступили до начала массива, возвращаемся на позицию 1A[i] >= A[i - 1]— текущий элемент на месте, идём вперёд (i + 1)- Иначе — меняем
A[i]иA[i - 1]местами и отступаем назад (i - 1)
Алгоритм похож на сортировку вставками, но проще в реализации — всего один цикл и три ветки.
Сложность: $O(n^2)$ в среднем и худшем случае.
Полная программа
алг main(цел n)
нач
если n <= 0 то
вывод "Размер массива должен быть положительным", нс
выход
все
цел таб A[0:n-1]
заполнить_случайными(n, A)
вывод "Исходный массив:", нс
печать_массива(n, A)
stonesort(n, A)
вывод "Отсортированный массив:", нс
печать_массива(n, A)
кон
| Stone sort (gnome sort)
алг stonesort(цел n, цел таб A[0:n-1])
нач
цел i, tmp
i := 1
нц пока i < n
если i = 0 то
i := 1
иначе
если A[i] >= A[i - 1] то
i := i + 1
иначе
tmp := A[i]
A[i] := A[i - 1]
A[i - 1] := tmp
i := i - 1
все
все
кц
кон
алг заполнить_случайными(цел n, цел таб A[0:n-1])
нач
цел i
нц для i от 0 до n - 1
A[i] := irnd(100)
кц
кон
алг печать_массива(цел n, цел таб A[0:n-1])
нач
цел i
нц для i от 0 до n - 1
вывод A[i], " "
кц
вывод нс
кон