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

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

Гномья сортировкаГномья сортировка впервые была предложена 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 <n. где n – размер массива. Во-вторых, как было сказано, указатель перемещается как вперед по списку, так и назад, и в том случае если он окажется над первым элементом, его сразу же следует сместить на одну позицию вправо, т. к. в противном случае придется сравнивать два элемента, одного из которых не существует.

Перейдем собственно к коду. На своем сайте Дик Грун выложил следующий листинг:

void gnomesort(int n, int ar[])

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

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

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

Гномья сортировка (англ.   Gnome sort ) — алгоритм сортировки. похожий на сортировку вставками. но в отличие от последней перед вставкой на нужное место происходит серия обменов, как в сортировке пузырьком. Название происходит от предполагаемого поведения садовых гномов при сортировке линии садовых горшков, описанного на странице Дика Груна Гномья сортировка .

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

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

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

Алгоритм концептуально простой, не требует вложенных циклов. Время работы Гномья сортировка. На практике алгоритм может работать так же быстро, как и сортировка вставками.

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

Ниже написан псевдокод сортировки. Это оптимизированная версия с использованием переменной 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 не < 4.

Оптимизация

В результате оптимизации гномья сортировка естественно трансформируется в сортировку вставками. Каждый раз «гном» наталкивается на новый номер, все значения слева от «гнома» уже отсортированы.

Смотреть что такое «Гномья сортировка» в других словарях:

Сортировка Шелла — (англ. Shell sort)  алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга. Иными… … Википедия

Сортировка выбором — (Selection sort)  алгоритм сортировки. Может быть реализован и как устойчивый и как неустойчивый. На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае Θ(n2), предполагая что сравнения делаются за постоянное… … Википедия

Сортировка вставками — Сортировка вставками  простой алгоритм сортировки. Хотя этот алгоритм сортировки уступает в эффективности более сложным (таким как быстрая сортировка), у него есть ряд преимуществ: эффективен на небольших наборах данных, на наборах данных до … Википедия

Сортировка пузырьком — Сортировка простыми обменами, сортировка пузырьком (англ. bubble sort)  простой алгоритм сортировки. Для понимания и реализации этот алгоритм  простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: O(n²).… … Википедия

Сортировка подсчётом — алгоритм сортировки, в котором используется диапазон чисел сортируемого массива (списка) для подсчёта совпадающих элементов. Применение сортировки подсчётом целесообразно лишь тогда, когда сортируемые числа имеют (или их можно отобразить в)… … Википедия

Сортировка перемешиванием — (Шейкерная сортировка) (англ. Cocktail sort) разновидность пузырьковой сортировки. Анализируя метод пузырьковой сортировки можно отметить два обстоятельства. Во первых, если при движении по части массива перестановки не происходят, то эта… … Википедия

Сортировка расчёской — (англ. comb sort)  это довольно упрощённый алгоритм сортировки, изначально спроектированный Влодзимежом Добосиевичем в 1&80 г. Позднее он был переоткрыт и популяризован в статье Стивена Лэйси и Ричарда Бокса в журнале Byte Magazine … Википедия

Сортировка слиянием — Действие алгоритма на примере сортировки случайных точек. Сортировка слиянием (англ. merge sort) алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только п … Википедия

Сортировка с помощью двоичного дерева — Пример двоичного дерева Сортировка с помощью двоичного дерева (сортировка двоичным деревом, сортировка деревом, древесная сортировка, сортировка с помощью бинарного дерева, англ.&#1 … Википедия

Устойчивая сортировка — Устойчивая (стабильная) сортировка  сортировка, которая не меняет относительный порядок сортируемых элементов, имеющих одинаковые ключи. Устойчивость является очень важной характеристикой алгоритма сортировки, но, тем не менее, она… … Википедия

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

Гномья сортировка (англ. Gnome sort ) — алгоритм сортировки. похожий на сортировку вставками. но в отличие от последней перед вставкой на нужное место происходит серия обменов, как в сортировке пузырьком. Название происходит от предполагаемого поведения садовых гномов при сортировке линии садовых горшков.

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

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

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

Алгоритм концептуально простой, не требует вложенных циклов. Время работы O ( n 2 ) <\displaystyle O\left(n^<2>\right)> . На практике алгоритм может работать так же быстро, как и сортировка вставками.

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

Содержание

Гномья сортировка
Гномья сортировка (англ. Gnome sort) — алгоритм сортировки, похожий на сортировку вставками, но в отличие от последней перед вставкой на нужное место происходит серия обменов, как в сортировке пузырьком. Название происходит от предполагаемого поведения садовых гномов при сортировке линии садовых горшков.

Гномья сортировка основана на технике, используемой обычным голландским садовым гномом (нидерл. tuinkabouter). Это метод, которым садовый гном сортирует линию цветочных горшков. По существу он смотрит на следующий и предыдущий садовые горшки: если они в правильном порядке, он шагает на один горшок вперёд, иначе он меняет их местами и шагает на один горшок назад. Граничные условия: если нет предыдущего горшка, он шагает вперёд; если нет следующего горшка, он закончил.
На практике алгоритм может работать также быстро, как и сортировка вставками.
Алгоритм находит первое место, где два соседних элемента стоят в неправильном порядке и меняет их местами. Он пользуется тем фактом, что обмен может породить новую пару, стоящую в неправильном порядке, только до или после переставленных элементов. Он не допускает, что элементы после текущей позиции отсортированы, таким образом, нужно только проверить позицию до переставленных элементов.

type massiv=array[1..100] of integer;

var
k, m, n: integer;
a: massiv;

procedure PGnome_sort(i, j: integer; mas: massiv);
var
t: integer;
begin
while i<=n do
begin
if mas[i-1]<=mas[i] then
begin
i:=j;
j:=j+1;
end
else
begin
t:=mas[i];
mas[i]:=mas[i-1];
mas[i-1]:=t;
i:=i-1;
if i=1 then
begin
i:=j;
j:=j+1;
end;
end;
end;
write(UTF8ToConsole(‘Отсортированный массив: ‘));
for i:=1 to n do
write(mas[i], ‘ ‘); <вывод массива>
end;
begin
clrscr;
write(UTF8ToConsole(‘Размер массива > ‘));
read(n);
for k:=1 to n do <ввод массива>
begin
write(k, UTF8ToConsole(‘ элемент > ‘));
read(a[k]);
end;
k:=2;
m:=3;
PGnome_sort(k, m, a); <вызов процедуры сортировки>
readkey;
end.

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

С этой задачей мы уже сталкивались, когда решали задачи раздела «Цикл For и массивы. Решение тематических задач «.

Итак, что же такое гномья сортировка. Википедия описывает её так: Название происходит от предполагаемого поведения садовых гномов при сортировке линии садовых горшков, описанного на странице Дика Груна Гномья сортировка:

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

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

Для наглядности приведу ещё одну демонстрацию этого алгоритма:

Ниже приведён код сортировки. Это оптимизированная версия с использованием промежуточной переменной ipos для запоминания того места, в котором встретились неотсортированные горшки, чтобы после окончания правильной расстановки всех предыдущих горшков разрешить прыжок вперёд, туда, где гном остановился до движения влево, избегая лишних итераций и сравнений. На рисунке выше показана как раз такая оптимизированная версия.

Задача та же, что и в сортировке методом пузырька. дан массив целых чисел. Необходимо отсортировать этот массив по возрастанию (т.е. расставить цифры по порядку от меньшего к большему). Программа получает на вход размер массива n, а затем сам массив. Необходимо вывести на экран отсортированный по возрастанию массив.

with Ada.Text_IO; use Ada.Text_IO; with Ada.Integer_Text_IO; use Ada.Integer_Text_IO; procedure main is type Matrix is array(Integer range <9gt;) of Integer; n. Integer; tmp. Integer; iprev, inext, ipos. Integer; begin Put("Размер массива: "); Get(n); declare mas. Matrix(1..n); begin --ввод массива Put_Line("Массив: "); for i in 1..mas'Last loop Get(mas(i)); end loop; --сортировка массива iprev := 1; inext := 2; while inext <= mas'Last loop --сравниваются 2 элемента, и если последующий меньше предыдущего, то if mas(inext) < mas(iprev) then ipos := inext; --запоминаем позицию "следующего9quot; --Сравниваем найденный элемент (меньший) со всеми элементами в массиве, --стоящими до него, и производим обмен, если элемент меньше предыдущего while inext - 1 >= 1 and then mas(inext) < mas(inext - 1) loop tmp := mas(inext); mas(inext) := mas(inext - 1); mas(inext - 1) := tmp; inext := inext - 1; end loop; inext := ipos; end if; inext := inext + 1; iprev := inext - 1; end loop; --вывод массива Put_Line("Итоговый массив: "); for i in 1..mas'Last loop Put(Item => mas(i), Width => 1); Put(» «); end loop; end; end main;

Навигация по записям

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *