Характеристики метода сортировки линейным выбором

Число сравнений:

n (n 1) / 2

( в среднем	n2	/ 2
		)

Максимальное количество перестановок:

(n-1)

1

Метод "пузырька"

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

Сортировка прекращается, если при очередном просмотре не было ни одной перестановки.

2

Пример сортировки методом “пузырька” (предпоследний проход по таблице)

18	12	65	24	78	82	94	98
18>12-обмен
12	18	65	24	78	82	94	98
	18<65- сравнения продолжаются
12	18	65	24	78	82	94	98
		65>24-обмен
12	18	24	65	78	82	94	98

при дальнейших 4-х сравнениях обменов нет

3

Возможные модификации метода:

•Признак наличия/отсутствия перестановки записей при очередном просмотре (если не было ни одной перестановки, значит, таблица упорядочена)

•Запоминание индекса последней перемещенной записи (следующий просмотр выполняют не до конца таблицы, а до этой позиции)

4

Алгоритм сортировки методом «пузырька»

Формальные параметры процедуры сортировки:

T – имя таблицы;

n – ее размер (количество записей).

5

Локальные переменные:

i – индекс текущей записи,

k – позиция, в которой была последняя перестановка записей,

m – номер последней записи, участвующей в сравнениях на текущем шаге,

zap – переменная для обмена записей,

pr – признак наличия перестановок записей при выполненном шаге.

6

Алгоритм сортировки:

k:=n-1;
pr:=true;
while (k>=1) and pr do
begin
pr:=false;
for i:=1 to k do
if T[i].ключ>T[i+1].ключ then
begin
обмен T[i], T[i+1];
m:=i;
pr:=true
end;
k:=m-1	7
end

Характеристики метода «пузырька»

• Максимальное число сравнений:

n (n 1) 2

• Среднее число перестановок

n (n 1) 2

8

Сортировка таблицы методом вставки

(прямое включение)

9

Алгоритм

J – номер шага (j=2, 3, …, n).

На текущем шаге записи с индексами 1, 2, …, j-1 упорядочены;

j – я запись вставляется на свое место путем сравнения ее ключа с ключами записей с номерами j-1, j-2 и т.д. и

сдвига этих записей

10