Гномья сортировка (англ. Gnome sort ) — алгоритм сортировки, похожий на сортировку вставками, но в отличие от последней перед вставкой на нужное место происходит серия обменов, как в сортировке пузырьком. Название происходит от предполагаемого поведения садовых гномов при сортировке линии садовых горшков.
 |
Гномья сортировка основана на технике, используемой обычным голландским садовым гномом (нидерл. tuinkabouter ). Это метод, которым садовый гном сортирует линию цветочных горшков. По существу он смотрит на текущий и предыдущий садовые горшки: если они в правильном порядке, он шагает на один горшок вперёд, иначе он меняет их местами и шагает на один горшок назад. Граничные условия: если нет предыдущего горшка, он шагает вперёд; если нет следующего горшка, он закончил. Дик Грун |
 |
Алгоритм концептуально простой, не требует вложенных циклов. Время работы O ( n 2 ) <displaystyle Oleft(n^<2>
ight)> 
Алгоритм находит первое место, где два соседних элемента стоят в неправильном порядке и меняет их местами. Он пользуется тем фактом, что обмен может породить новую пару, стоящую в неправильном порядке, только до или после переставленных элементов. Он не допускает, что элементы после текущей позиции отсортированы, таким образом, нужно только проверить позицию до переставленных элементов.
Содержание
Описание [ править | править код ]
Ниже написан псевдокод сортировки. Это оптимизированная версия с использованием переменной j, чтобы разрешить прыжок вперёд туда, где он остановился до движения влево, избегая лишних итераций и сравнений:
Если мы хотим отсортировать массив с элементами [4] [2] [7] [3] от большего к меньшему, то на итерациях цикла while будет происходить следующее:
- [4] [2] [7] [3] (начальное состояние: i == 1, j == 2);
- [4] [2] [7] [3] (ничего не произошло, но сейчас i == 2, j == 3);
- [4] [7] [2] [3] (обмен a[2] и a[1], сейчас i == 1, а j == 3 по-прежнему);
- [7] [4] [2] [3] (обмен a[1] и a[0], сейчас i == 3, j == 4);
- [7] [4] [3] [2] (обмен a[3] и a[2], сейчас i == 2, j == 4);
- [7] [4] [3] [2] (ничего не произошло, но сейчас i == 4, j == 5);
- цикл закончился, т. к. i не Реализация на С++ [ править | править код ]
Реализация на Java [ править | править код ]
Реализация на Python [ править | править код ]
Оптимизация [ править | править код ]
В результате оптимизации гномья сортировка естественно трансформируется в сортировку вставками. Каждый раз «гном» наталкивается на новый номер, все значения слева от «гнома» уже отсортированы.
Гномья сортировка впервые была предложена 2 октября 2000 года Хамидом Сарбази-Азадом (Hamid Sarbazi-Azad). Он назвал ее «Глупая сортировка, простейший алгоритм сортировки всего с одним циклом…». И действительно, глупый этот метод или нет, но в нем задействован, никак в большинстве сортировок – два или более циклов, а только один. Позже, голландский ученый Дик Грун, на страницах одной из своих книг, привел для гномьей сортировки следующую аналогию.
Gnome Sort is based on the technique used by the standard Dutch Garden Gnome (Du.: tuinkabouter). Here is how a garden gnome sorts a line of flower pots. Basically, he looks at the flower pot next to him and the previous one; if they are in the right order he steps one pot forward, otherwise he swaps them and steps one pot backwards. Boundary conditions: if there is no previous pot, he steps forwards; if there is no pot next to him, he is done.
Перевод:
Гномья сортировка основана на технике, используемой обыкновенным голландским садовым гномом. Вот как садовый гном сортирует ряд цветочных горшков. По существу, он смотрит на два соседних цветочных горшка, если они находятся в правильном порядке, то он переходит на один горшок вперед, иначе он меняет их местами и возвращается на один горшок назад. Граничные условия: если позади нет ни одного горшка – он шагает вперед, а если нет следующего горшка, тогда он закончил.
Так описал основную идею алгоритма гномьей сортировки Дик Грун. Заменим гнома и горшки на более формальные объекты, например на указатель (номер текущего элемента) и элементы массива, и рассмотрим принцип работы алгоритма еще раз. Вначале указатель ставиться на 2-ый элемент массива (в C++ он имеет номер 1, а в Паскале номер 2).
Затем происходит сравнение двух соседних элементов A[i] и A[i-1], т. е. сравниваются первый элемент (i-1) и второй (i). Если те стоят на своих позициях, то сдвигаем указатель на позицию i+1 и продолжаем сравнение с нового положения; иначе меняем элементы местами, и, поскольку в какой-то момент может оказаться, что элементы в левом подмассиве стоят не на своих местах, сдвигаем указатель на одну позицию влево, осуществляя следующее сравнение с новой позиции. Так алгоритм продолжает выполняться до тех пор, пока весь массив не будет упорядочен.
Здесь следует выделить два важных момента.
Во-первых, процесс упорядочивания заканчивается, тогда когда не выполняется условие i #include «stdafx.h»
#include
using namespace std ;
int n ;
void Gnome_sort ( int i, int j, int * mas )
<
while ( i n )
<
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 ++ ; >
> >
cout «Отсортированный массив: « ;
for ( i = 0 ; i n ; i ++ ) //вывод массива
cout mas [ i ] » « ;
>
void main ( )
<
setlocale ( LC_ALL, «Rus» ) ;
int m, k ;
cout «Размер массива > « ; cin >> n ;
int * a = new int [ n ] ;
for ( k = 0 ; k n ; k ++ ) //ввод массива
< cout k + 1 » элемент >« ; cin >> a [ k ] ; >
k = 1 ; m = 2 ;
Gnome_sort ( k, m, a ) ; //вызов функции сортировки
delete [ ] a ;
system ( «pause>>void» ) ;
>
Код программы на Pascal:
Кажется немного необычным, тот факт, что алгоритм сортировки использует всего один цикл. Плюс к этому, на практике гномья сортировка не уступает в скорости сортировки вставками, что видно из таблицы трех случаев этих сортировок.
Гномья сортировка (Gnome sort) – простой в реализации алгоритм сортировки массива, назван в честь садового гнома, который предположительно таким методом сортирует садовые горшки.
Принцип работы алгоритма сортировки Гнома
Алгоритм находит первую пару неотсортированных элементов массива и меняет их местами. При этом учитывается факт, что обмент приводит к неправильному расположению элементов примыкающих с обеих сторон к только что переставленным. Поскольку все элементы массива после переставленных не отсортированны, необходимо перепроверить только элементы до переставленных.