Пузырьковая сортировка

Сущность пузырьковой сортировки состоит в следующем. Пусть

необходимо исходный массив чисел

a [ ], a [2],, a [ n ]

расположить в неубывающем порядке, т.е. так, чтобы выполнялось условие a [ i ]£ a [ j ],если i < j.

Будем рассматривать элементы массива как вектор-столбец, в первой строкекоторогорасположенэлемент a [ ],авпоследнейстроке—элемент a [ n ]

исходного массива.

Метод состоит в том, чтобы на каждой итерации метода наиболее

«легкий» (с меньшим значением) элемент оказался «выше» всех более

«тяжелых» элементов массива. Из такого представления и проистекает

название метода.

Каждая k -я итерация начинается с рассмотрения последнего, n -го

элемента массива. В общем случае, при рассмотрении i -го элемента массива, происходит его сравнение с i -1-м элементом. Если a [ ]> a [ i ], то

элементы массива меняются местами. В противном случае расположение

элементов не меняется. Далее происходит переход к рассмотрению i -1-го элемента массива. Итерация заканчивается при сравнении a [ k +1 -то элементасэлементом a [ k ].Врезультатевыполнениякаждойитерацииодин,

i -1

]

самый «легкий» элемент, оказывается «наверху» рассматриваемой части

вектора-столбца.

Сортировка заканчивается, когда в процессе ее выполнения не будет ни

одной замены местами элементов массива.

Пример4.2.1. Пузырьковым методомотсортируем массивцелыхчисел

А = {8,4,6,3,7,2,1,5}.

Изменения исходного массива в процессе сортировки представлены в виде

последовательности вектор-строк, каждый из которых содержит результат

соответствующей итерации

{8,4,6,3,7,2,1,5} - исходный массив;

{1,8,4,6,3,7,2,5} - 1-я итерация;

{1,2,8,4,6,3,7,5} - 2-я итерация;

{1,2,3,8,4,6,5,7} - 3-я итерация;

{1,2,3,4,8,5,6,7} - 4-я итерация;

{1,2,3,4,5,8,6,7} - 5-я итерация;

{1,2,3,4,5,6,8,7} - 6-я итерация;

{1,2,3,4,5,6,7,8} - 7-я итерация.

Определим число операций, которые необходимо выполнить (в худшем

случае) для получения отсортированного массива.

На первой итерации требуется, очевидно, выполнить п - 1 сравнений и, возможно, столько же перемен местами сравниваемых элементов. На второй итерации уже потребуется выполнить п - 2 сравнений и столько же перемен местами элементов. Легко заметить, что на k -той итерации потребуется выполнить п - k сравнений и столько же перемен местами

элементов. Значит, всего нужно выполнить n 2- n операций.

Программа пузырьковой сортировки на Паскале имеет следующий вид

program Bubble;

(* пузырьковая сортировка *) Uses СRT;

Const n=8;

Var i,k,t:integer; flag:boolean;

A:array[1..n] of integer;

begin clrscr;

for i:=l to n do A[i]:=0;

writeln (‘Введите элементы массива’);

for i:=l to n do read(A[i]);

Writeln;

k:=l; (* номер итерации *) repeat

flag:=true;

Writeln(k,'-тая итерация:'); for i:=n downto k+1 do

if A[i] < A[i-l] then begin

flag:=false; t:=A[i];

A[i-1]:=t; end;

for i:=l to n do

Write(A[i],’ ‘); Writeln;

k:=k+l; until((k=n)or flag); end.

Дата добавления: 2015-11-16