Delphi World - Сортировка пузырьком и ее улучшения
Delphi World - это проект, являющийся сборником статей и малодокументированных возможностей  по программированию в среде Delphi. Здесь вы найдёте работы по следующим категориям: delphi, delfi, borland, bds, дельфи, делфи, дэльфи, дэлфи, programming, example, программирование, исходные коды, code, исходники, source, sources, сорцы, сорсы, soft, programs, программы, and, how, delphiworld, базы данных, графика, игры, интернет, сети, компоненты, классы, мультимедиа, ос, железо, программа, интерфейс, рабочий стол, синтаксис, технологии, файловая система...
Сортировка пузырьком и ее улучшения

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

{ Сортируются записи типа item по ключу item.key }
{ для вспомогательных переменных используется тип index }
procedure BubbleSort;
    var i,j: index; x:item;
begin for i:=2 to n do
    begin for j:=n downto i do
	    if a[j-1].key > a[j].key then
		begin x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x;
		end;
	end;
end;

  Пример 1. Проходим по массиву снизу вверх. Меньшие/более легкие/
            элементы 'всплывают' наверх, давая название методу.
  
  Hачальные  i      i      i      i      i      i      i
    ключи    2      3      4      5      6      7      8
     44 /-> 06     06     06     06     06     06     06   
     55 |   44 /-> 12     12     12     12     12     12
     12 |   55 |   44 /-> 18     18     18     18     18
     42 |   12-/   55 |   44 /-> 42     42     42     42
     94 |   42 /-> 18-/   55 |   44 --> 44     44     44
     18 |   94 |   42     42-/   55     55 --> 55     55
     06-/   18-/   94 ->  67     67     67     67 --> 67
     67     67     67-/   94     94     94     94     94
	 	 
 Алгоритм пузырька очень медленен и неэффективен. Тем не менее,
у него есть громадный плюс: он прост и его можно по-всякому улучшать.
Чем мы сейчас и займемся.

   Посмотрите на пример 1. Три последних прохода никак не влияют на 
порядок элементов, поскольку те уже отсортированы. Очевидный способ улучшить
алгоритм - запоминать, производился ли на данном проходе какой-либо обмен.
Если нет - это означает, что алгоритм может закончить работу.

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

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

  Hапример, массив 12 18 42 44 55 67 94 06 будет отсортирован за 1 проход,
а сортировка массива 94 06 12 18 42 44 55 67 потребует 7 проходов.

Эта неестественная асимметрия подсказывает третье улучшение:
менять направление следующих один за другим проходов.
Получившийся алгоритм иногда называют 'шейкер-сортировкой'.

  Пример его работы на том же входном массиве.
	
         l  =  2       3       3       4       4
         r  =  8       8       7       7       4
              44  /-> 06      06      06      06
              55  |   44      44  /-> 12      12
              12  |   55 -\   12 -/   44 -\   18
              42  |   12  |   42  /-> 18  |   42
              94  |   42  \-> 55  |   42  \-> 44
              18  |   94 -\   18 -/   55      55
              06 -/   18  |   67      67      67
              67      67  \-> 94      94      94
 Проходы:     /|\      |      /|\      |      /|\
               |      \|/      |      \|/      |
			   
			   
procedure ShakerSort;
    var j,k,l,r: index; x: item;
begin l:=2; r:=n; k:=n;
    repeat
	    for j:=r downto l do
		    if a[j-1].key > a[j].key then
			begin x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x;
                k:=j;
			end;
		l:=k+1;
		for j:=l to r do
		    if a[j-1].key > a[j].key then
			begin x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x;
			    k:=j;
			end;
		r:=k-1;
	until l>r;
end;
			   
Анализ алгоритма простого пузырька:
  Число сравнений   
    C = 1/2 (n^2 - n),
 Числа пересылок:
   Mmin = 0, Mсреднее = 3/4 (n^2 - n), Mmax = 3/2 (n^2 - n).             
			   
Анализ шейкер-сортировки (из книги Д.Кнута):	 
  Минимальное число сравнений Cmin = n-1
  Среднее число проходов пропорционально n - k1*корень(n),
  Cреднее число сравнений пропорционально 1/2 ( n^2 - n(k2+ln(n)) ).
  
Hо, как видно, все предложенные усовершенствования не влияют на число 
обменов. К сожалению, обмен - операция, как правило, гораздо более 
медленная, чем сравнение ключей, поэтому реальный эффект улучшений
гораздо меньше, чем можно было бы ожидать.

  Метод пузырька и описанные улучшения на практике крайне неэффективны,
SelectSort и InsertSort работают быстрее. Шейкер-сортировку выгодно
использовать, когда известно, что элементы уже почти упорядочены.
Hо даже в этом случае обычно применяют все же InsertSort, которая
менее чувствительна к степени упорядоченности.
Проект Delphi World © Выпуск 2002 - 2017
Автор проекта: Эксклюзивные курсы программирования