Используются два индекса для обращения к записям, ключи которых сравниваются с разделяющим элементом. Если упорядоченность нарушена-записи меняются местами, индексы смещаются к середине таблицы.

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

Далее- разделение для правой и левой подтаблиц

Среднее число сравнений = n log2(n).

11

Параметры сортировки

T – сортируемая таблица;

l – левая граница разделения (при первом вызове =1);

R – правая граница разделения(при первом вызове =n).

12

Рекурсивная процедура "быстрой" сортировки

procedure SORT (var T: table; l, r: integer); var i,j:integer;

. . . . . . . . . . . . . . . . .

begin

{процесс разделения}

. . . . . . . . . . . . . . . . . . . .

if (i-1)>l then

SORT (T, l, i-1); if (i+1)<r then

SORT (T, i+1, r);

end;	13

«Быстрая» сортировка с первым разделяющим элементом

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

i, j – индексы сравниваемых записей

pr – признак того, что разделяющий элемент находится слева (в позиции i),

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

14

Алгоритм разделения:

i:=l; j:=r; pr:=true;

While i<j

Begin

If (t[i].ключ>t[j].ключ) then

Begin zap:=t[i]; t[i]:=t[j]; t[j]:=zap;

pr:=not pr;

End;

If pr then j:=j-1 else I:=I+1;

End;

15

Пример выполнения

42	23	74	11	36	58	94
42	23	74	11	36	58	94
42	23	74	11	36	58	94
36	23	74	11	42	58	94
36	23	74	11	42	58	94
36	23	42	11	74	58	94
			42

обмен

обмен

обмен

1-я подтаблица	2-я подтаблица	16

Сортировка со средним разделяющим элементом (алгоритм разделения):

i:=l; j:=r; pr:=true;		x:=t[(l+r) div 2].ключ;
while pr do
begin
while	(t[i].ключ<x)	do	i:=i+1 ;
while	(t[j].ключ>x)	do	j:=j-1 ;
if i=j then pr:=false

else

	if t[i].ключ <> t[j].ключ then
	обмен t[i], t[j]
	else begin
	i:=i+1;
	j:=j-1
	end;
end;	17

Пример выполнения

1	2	3	4	5	6	7	8	9	10
16	22	99	89	85	18	87	13	90	5	i=3, j=10 обмен
16	22	5	89	85	18	87	13	90	99	i=4, j=8 обмен
16	22	5	13	85	18	87	89	90	99	i=5, j=6 обмен
16	22	5	13	18	85	87	89	90	99	i=6, j=6
										конец шага

18