Алгоритм гномьей сортировки (while, var, циклы в Delphi)

Тестовый пример для сравнения пузырьковой и гномьей сортировки можете скачать здесь.

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

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

Вот как такая процедура будет выглядеть на Delphi:

procedure gnomeSort(var item: DataArray; count:integer);
var
    i,j: integer;
    x: DataItem;
begin
   i:= 2;
   j:= 3;
   while i <= count do
   begin
       if item[i - 1] <= item[i] then
       begin
          i:= j;
          j:= j + 1;
       end
       else
       begin
           x:= item[i-1];
           item[i-1] := item[i];
           item[i] := x;
           i:= i - 1;
           if i = 1 then
           begin
               i:= j;
               j:= j + 1;
           end;
      end;
   end;
end;

Работу этого алгоритма мы рассмотрим на примере сортировки последовательности чисел [424] [206] [849] [925] [854].

Итерация 1. [424] [206] [849] [925] [854] (начальное состояние: i = 2, j = 3);
Итерация 2. [206] [424] [849] [925] [854]. Первое и второе числа поменялись местами (i=3, j=4)
Итерация 3. [206] [424] [849] [925] [854]. Ничего не произошло, но теперь у нас i=4, j=5.
Итерация 4. [206] [424] [849] [925] [854]. Снова ничего не произошло, но теперь у нас i=5, j=6.
Итерация 5. [206] [424] [849] [854] [925]. Поменялись местами четвертое и пятое число. (i=4, j=6)
Итерация 6. [206] [424] [849] [854] [925]. Ничего не произошло, но теперь у нас i=6, j=6. Наш массив отсортирован и это у нас последняя итерация.

Что же быстрее, гномья сортировка или пузырьковая? Тесты показали, что последняя*:

Тестовый пример для сравнения пузырьковой и гномьей сортировки можете скачать здесь.

Скриншоты, помеченные знаком *, являются цитатами и иллюстрациями программного продукта "Delphi", авторское право на который принадлежит Borland Delphi..

Последнее обновление ( 10.02.2013 г. )

« След.		Пред. »

Вернуться