Модели внутренней сортировки.
Листинг 8.1. Алгоритм „пузырька"
procedure bubble ( var A: array[1..n] of integer)
{упорядочивает массив А по неубыванию}
var i,j: integer;
begin
(1) for i:= I to n - 1 do
(2) for j:= n downto i + 1 do
(3) if A[j]< A[j - 1] then
(4) swap(A[j], A[j - 1])
end
Листинг 8.2. Процедура swap
procedure swap ( var x, у: integer )
{ swap меняет местами записи х и у }
var
temp: integer;
begin
temp:= x;
x:= y;
y:= temp;
end; { swap }
Листинг 8.3. Сортировка вставками
(1) А[0]:= -∞;
(2) for i:= 2 to n do begin
(3) j:= i;
(4) while A[j] < A[j - 1] do begin
(5) swap(A[jl, A[j - 1]);
(6) j:= j - 1
end
end
Листинг 8.4. Сортировка посредством выбора
procedure sortselect ( var A: array[1..n] of integer)
{упорядочивает массив А по неубыванию}
var
lowelement: integer; { текущий наименьший элемент, найденный
при проходе по элементам A[i], …, А[n] }
lowindex: integer; { позиция элемента lowelement }
begin
for i:= 1 to n - 1 do begin
lowindex: = i;
lowelement:= A[i];
for j:= i + 1 to n do
{ сравнение элементов с текущим элементом lowelement }
if A[j]< lowelement then begin
lowelement.= A[j];
lowindex:= j
end;
swap{A[i], A[lowindex])
end
end;
Листинг 8.5. Процедура быстрой сортировки (эскиз)
(1) if A[i], ..., A[j] имеют не менее двух различных значений then begin
(2) пусть v — наибольшее из первых двух найденных различных значений;
(3) переставляются элементы А[i], ..., A[j] так, чтобы
для некоторого k, i+l<k<j, A[i], ..., А[k-1] имели значения,
меньшие, чем v, а А[k], ..., A[j] — большие или равные v;
(4) quicksort(i, k-1) ,-
(5) quicksort(к, j)
end
Листинг 8.6. функция findpivot
function findpivot ( i, j: integer ): integer;
var
firstelement: integer;
{ примет значение первого найденного элемента, т.е. A[i]}
k: integer; { текущий индекс при поиске различных элементов}
begin
firstelement:= А[i];
for k:= i + 1 to j do { просмотр элементов }
if A[k]> firstelement then { выбор наибольшего элемента}
return(к)
else if A[k]< firstelement then
return(i);
return(0) { различные элементы не найдены }
end; { findpivot }
Листинг 8.7. Функция partition
function partition ( i, j: integer; pivot: integer ): integer;
var
l, r: integer; { курсоры }
begin
l:= i;
r: = j;
repeat
swap(A[l], A[r]);
while A[l]< pivot do
l:=l + 1;
while A[r]>= pivot do
r:= r - 1
until
l > r;
return(l)
end; { partition }
Листинг 8.8. Процедура быстрой сортировки
procedure quicksort ( i, j: integer );
{ сортирует элементы A[i], ..., A[j] внешнего массива А }
var
pivot: integer; { опорное значение }
pivotindex: integer;
{ индекс элемента массива А, чье значение равно pivot }
к: integer;
{начальный индекс группы элементов, чьи значения ≥ pivot}
begin
pivotindex:= findpivot(i, j) ;
if pivotindex <> 0 then begin
{ если все значения равны, то ничего делать не надо }
pivot:= A[pivotindex];
к:= partition(i, j, pivot);
quicksort(i, k-1) ;
quicksort(k, j)
end
end; { quicksort }