Алгоритмы сортировки.

Алгоритм 'пузырька'.

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

Анализ.

Число сравнений:		( n² - n ) / 2
Количество пересылок
	минимальное:	0
	среднее:	( n² - n ) * 3 / 4
	максимальное:	( n² - n ) * 3 / 2

Программа на Паскале.

procedure bubble;
	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 {bubble}

Вверх по странице, к оглавлению и навигации.