Лекция
Привет, сегодня поговорим про гномья сортировка, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое гномья сортировка , настоятельно рекомендую прочитать все из категории Алгоритмы и теория алгоритмов.
гномья сортировка впервые была предложена 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
Перейдем собственно к коду. На своем сайте Дик Грун выложил следующий листинг:
|
1
2 3 4 5 6 7 8 |
void gnomesort(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;} } } |
Приведенный Груном код позволяет упорядочить массив, но все же он может быть немного улучшен. Об этом говорит сайт https://intellect.icu . Оптимизация потребует небольшого редактирования, в частности, добавления одной вспомогательной переменной, что позволит избавиться от излишних сравнений. Далее показаны листинги программ, сортирующих элементы массива по возрастанию.
|
1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
#include "stdafx.h"
#include using namespace std; int n; void Gnome_sort(int i, int j, int *mas) { while (i{ 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; icout< "; cin>>a[k]; } k=1; m=2; Gnome_sort(k, m, a); //вызов функции сортировки delete []a; system("pause>>void"); } |
|
1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
program Gnome_sort;
uses crt; 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('Отсортированный массив: '); for i:=1 to n do write(mas[i], ' '); {вывод массива} end; begin clrscr; write('Размер массива > '); read(n); for k:=1 to n do {ввод массива} begin write(k, ' элемент > '); read(a[k]); end; k:=2; m:=3; PGnome_sort(k, m, a); {вызов процедуры сортировки} readkey; end. |
Кажется немного необычным, тот факт, что алгоритм сортировки использует всего один цикл. Плюс к этому, на практике гномья сортировка не уступает в скорости сортировки вставками, что видно из таблицы трех случаев этих сортировок.
|
Гномья сортировка |
Сортировка вставками |
|
|
Худший случай |
O(n2) |
O(n2) |
|
Лучший случай |
O(n) |
O(n) |
|
Средний случай |
O(n2) |
O(n2) |
На этом все! Теперь вы знаете все про гномья сортировка, Помните, что это теперь будет проще использовать на практике. Надеюсь, что теперь ты понял что такое гномья сортировка и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Алгоритмы и теория алгоритмов
Из статьи мы узнали кратко, но содержательно про гномья сортировка
Комментарии
Оставить комментарий
Алгоритмы и теория алгоритмов
Термины: Алгоритмы и теория алгоритмов