| На главную | О проекте | Контакты |
www.Russika.Ru
Статья в Энциклопедическом Фонде

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

Иллюстрация действия алгоритма

Гномья сортировка впервые была предложена Хамидом Сарбази-Азадом в 2000 г. Этот алгоритм сортировки схож с методом вставок, только в этом случае перемещение элементов на их позиции производится путем перестановки двух соседних элементов, аналогично методу "пузырька". Гномья сортировка весьма проста и для нее не требуется вложенных циклов. Среднее время упорядочивания равно O(n^2), но если изначально данные и так практически находятся в нужном порядке, то время становится близким к O(n). На практике данный алгоритм выполняется также быстро как и метод "вставок".

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

Голландский ученый Дик Грун, в одной из своих работ, привел для гномьей сортировки такую аналогию:

Гномья сортировка основана на технике, используемой обыкновенным голландским садовым гномом. Вот как садовый гном сортирует ряд цветочных горшков. По существу, он смотрит на два соседних цветочных горшка, если они находятся в правильном порядке, то он переходит на один горшок вперед, иначе он их меняет местами и возвращается на один горшок назад. Граничные условия: если нет никакого горшка позади, он шагает вперед, а если нет следующего горшка, он закончил.


Приведем простейший пример реализации такой схемы на языке С++.


void Gnome_sort(int n, int ar[]){

int i = 0;

while (i < n) {

if (i == 0 || ar[i-1] <= ar[i]) i++;

else {int tmp = ar[i]; ar[i] = ar[i-1]; ar[--i] = tmp;}

}}


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


void Gnome_sort(int i, int j, int *mas){

while (i< p>

if (mas[i-1]<=mas[i]){

i=j; j++;

}

else{

int t=mas[i];

mas[i]=mas[i-1]; mas[i-1]=t;

i--;

if (i==0){

i=j;

j++;

}}}}


Используемые источники:

1. ru.wikipedia.org/wiki/Гномья_сортировка

2. kvodo.ru/gnome-sorting.html

Энциклопедический Фонд