К практическому занятию № Модели внутренней сортировки.
Листинг 1. Алгоритм „пузырька"
procedure bubble ( var A: array[1..n] of integer)
{упорядочивает массив А по неубыванию}
var i,j: integer;
begin
(1) for i:= n to n - 1 do
(2) for j:= 1 downto i + 1 do
(3) if A[j]< A[j - 1] then
(4) swap(A[j], A[j - 1])
End
Листинг 2. Процедура swap
procedure swap ( var x, у: integer )
{ swap меняет местами записи х и у }
var
temp: integer;
begin
temp:= x;
x:= y;
y:= temp;
end; { swap }
Листинг 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
Листинг 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;
К практическому занятию № Алгоритм быстрой сортировки quicksort.
Для
простых схем сортировки (см практическое
занятие № ) временная сложность как в
худшем случае ,так и в среднем равна
О(
),
то есть T(n)=O(
),
Tср(n)=O(
).
Рассмотрим
алгоритм быстрой сортировки quicksort,для
которого в худшем случае временная
сложность T(n)=O(n2),но
в среднем
(n)=O(n‧
).
Пусть требуется упорядочить элементы A[i],..,A[j].
1. Если среди элементов A[i],..,A[j] есть как минимум два различных, то перейти к шагу 2. В противном случае - закончить работу.
2. Выбрать среди элементов A[i],..,A[j] опорный элемент v. Желательно так, чтобы количество элементов меньших v и больших v было примерно одинаковым.
3. Переставить элементы A[i],.., A[j] так,чтобы A[i],..,A[k-1] были меньше v, A[k],..,A[j] были больше или равны v .
4. Рекурсивно применить шаги 1-3 к массивам A[i],..,A[k-1] и A[k],..,A[j].
Листинг 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
В приведенных далее программах используется упрощённый способ нахождения опорного элемента- v (строка (2)). Функция findpivot (нахождение опорного элемента) проверяет, все ли элементы A[i],…,A[j] одинаковы, если нет различных значений, то findpivot возвращает значение 0. В противном случае - возвращает наибольший из первых двух различных элементов (см.листинг 8.6)
При этом не гарантировано, что количество элементов меньших v и больших v будет примерно одинаковым, однако преимуществом является малая временная сложность функции findpivot.
Листинг 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 }
Функция partition (разделение) выполняет перестановки элементов согласно строке (3) и возвращает индекс l первого элемента в правой части преобразованного массива A[i],…,A[j] (см.листинг 8.7).
Листинг 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 }
В функции partition используются два курсора l и r - индекс левого и правого концов той части массива ,где переставляются элементы. Элементы левее l уже меньше pivot ,а правее r уже больше или равны pivot.
Сначала l=i и r=j. Затем повторяются следующие действия, перемещающие l вправо ,а r влево.
1. Курсор l перемещается вправо , пока не встретится элемент, который ≥ pivot; r перемещает влево ,пока не встретит элемент, который <pivot.
2.Проверка:если l>r (возможно только l=r+1), то перемещения на участке A[i],…,A[j] заканчиваются.
3.Если l<r (случай l=r невозможен) переставляются местами A[l] и A[r]. После этого A[l]<pivot,A[r]pivot. Далее l перемещается на одну позицию вправо от предыдущего значения, r - на одну позицию влево. Повторяется пункт 1.
В листинге 8.8 представлена процедура быстрой сортировки quicksort,реализующая этапы листинга 8.5. Причём строки (1) и (2) с помощью findpivot(i,j), строка (3)-с помощью partition (i,j,pivot).
Листинг 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 }