Программирование - это просто
Advertisement
Главная arrow Уроки программирования arrow Алгоритмы arrow Алгоритмы. Урок 3. Алгоритм гномьей сортировки (while, var,  циклы в Delphi)
18.07.2024 г.
Главное меню
Главная
Интернет магазин
Программные продукты
Биржевые роботы
Искусственный интеллект
Математика и информатика
1С:Предприятие
Уроки C#
Уроки Delphi
Уроки программирования
Web-программирование
Дизайн и графика
Компьютер для блондинок
Исходники
Статьи
Платный раздел
Рассказы про компьютеры
Хитрости и секреты
Системный подход
Размышления
Наука для чайников
Друзья сайта
Excel-это не сложно
Все о финансах
.
Алгоритмы. Урок 3. Алгоритм гномьей сортировки (while, var,  циклы в Delphi) Печать E-mail
Автор megabax   
20.05.2010 г.
Циклы

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

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

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

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

Вот как такая процедура будет выглядеть на 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. Наш массив отсортирован и это у нас последняя итерация.


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

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

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

 


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


Последнее обновление ( 10.02.2013 г. )
 
« След.   Пред. »
 
© 2024 Программирование - это просто
Joomla! - свободное программное обеспечение, распространяемое по лицензии GNU/GPL.
Русская локализация © 2005-2008 Joom.Ru - Русский Дом Joomla!
Design by Mamboteam.com | Powered by Mambobanner.de
Я принимаю Яндекс.Деньги