СОРТИРОВКА
Сортировка представляет собой процесс упорядочения множества подобных информационных объектов в порядке возрастания или убывания их значений.
Оценка алгоритмов сортировки
Для каждого метода сортировки имеется много алгоритмов. Каждый алгоритм имеет свои достоинства, но в целом оценка алгоритма сортировки формируется по следующим критериям:
- средняя скорость сортировки информации, которая прямо зависит от числа сравнений и числа необходимых операций обмена;
- время работы алгоритма для лучшего случая и для худшего случая. Этот критерий важно учитывать, когда ожидается частое появление этих случаев. Часто сортировка имеет хорошую среднюю скорость, но очень плохую скорость для худшего случая, и наоборот;
- наличие перестановки элементов для одинаковых ключей.
Способы сортировки массивов:
- сортировка обменом;
- сортировка выбором;
- сортировка вставкой.
Для описания алгоритмов будем пользоваться следующими обозначениями:
Const nmax = 30;
type MyArray = array [1..nmax] of Integer;
var A: MyArray; n:integer;
Сортировка пузырьковым методом
Наиболее известной является сортировка пузырьковым методом. Ее популярность объясняется запоминающимся названием и простотой алгоритма. Однако эта сортировка является одной из самых худших среди всех когда-либо придуманных сортировок. Сортировка пузырьковым методом использует метод обменной сортировки. Она основана на выполнении в цикле операций сравнения и при необходимости обмена соседних элементов. Ее название происходит из-за подобия процессу движения пузырьков в резервуаре с водой, когда каждый пузырек находит свой собственный уровень.
{ сортировка пузырьковым методом}
procedure Bubble (var A: MyArray; n:integer);
var i, j: integer;
v: Integer;
begin
for i:= 2 to n do
for j:= n downto i do
if A[j-1]>A[j] then begin
v:= A[j-1];
A[j-1]:= A[j];
A[j]:= v;
end;
end; {конец сортировки пузырьковым методом}
Сортировка пузырьковым методом имеет два цикла. Внешний цикл вызывает просмотр массива n - 1 раз. Это обеспечивает нахождение каждого элемента в своей позиции после завершения процедуры. Внутренний цикл предназначен для фактического выполнения операций сравнения и обмена. Эта версия сортировки пузырьковым методом может сортировать целочисленный массив в порядке возрастания значений элементов.
Для иллюстрации работы сортировки пузырьковым методом ниже
даны результаты каждого этапа сортировки массива "4 3 1 2":
- исходное положение: 4 3 1 2;
- первый проход: 1 4 3 2;
- второй проход: 1 2 4 3;
- третий проход: 1 2 3 4.
При анализе любого алгоритма сортировки определяется число операций сравнения и обмена, выполняемых в лучшем, среднем и худших случаях.
Для сортировки пузырьковым методом число сравнений остается неизменным, поскольку два цикла всегда выполняются заданное число раз вне зависимости от упорядоченности исходного массива. Это означает, что при сортировке пузырьковым методом всегда выполняется 1/2 (n2 - n) операций сравнения, где n задает число сортируемых элементов массива. Эта формула выводится на том основании, что внешний цикл сортировки пузырьковым методом выполняется n-1 раз, а внутренний цикл выполняется n/2 раз. Их перемножение даст указанную формулу. Число операций обмена будет нулевым для наилучшего случая, когда исходный массив уже является отсортированным. Число операций обмена для среднего случая будет равно 3/4 (n2-n), а для наихудшего случая будет равно 3/2 (n2 - n) раз.
Можно заметить, что по мере ухудшения упорядоченности исходного массива число неупорядоченных элементов приближается к числу сравнений (каждый неупорядоченный элемент требует три операции обмена). Сортировку пузырьковым методом называют квадратичным алгоритмом, поскольку время его выполнения пропорционально квадрату числа сортируемых элементов, поэтому сортировка большого числа элементов пузырьковым методом потребует много времени.
Сортировку пузырьковым методом можно в некоторой степени улучшить и тем самым немного улучшить ее временные характеристики. Можно, например, заметить, что сортировка пузырьковым методом обладает одной особенностью: расположенный не на своем месте в конце массива элемент (например, элемент "1" в массиве "4 3 1 2") достигает своего места за один проход, а элемент, расположенный в начале массива (например, элемент "4"), очень медленно достигает своего места. Необязательно все просмотры делать в одном направлении. Вместо этого всякий последующий просмотр можно делать в противоположном направлении. В этом случае сильно удаленные от своего места элементы будут быстро перемещаться в соответствующее место. Ниже показана улучшенная версия сортировки пузырьковым методом, получившая название "челночной сортировки" из-за соответствующего характера движений по массиву.
Хотя эта сортировка является улучшением пузырьковым методом, ее нельзя рекомендовать для использования, поскольку время выполнения по-прежнему зависит квадратично от числа элементов. Число сравнений не изменяется, а число обменов уменьшается лишь на незначительную величину.
{челночная сортировка}
procedure Shaker(var A: MyArray; n:integer);
var j, k, l, r, v: integer;
begin
l:= 2; r:= n; k:= n;
repeat
for j:= r downto l do
if A[j-1]<A[j] then begin { обмен }
v:= A[j-1];
A[j-1]:= A[j];
A[j]:= v;
k:= j;
end;
l:= k+1;
for j:= l to r do
if A[j-1]>A[j] then begin { обмен }
v:= A[j-1];
A[j-1]:= A[j];
A[j]:= v;
k:= j;
end;
r:= k-1;
until l>r;
end; { конец челночной сортировки }
Сортировка выбором
При сортировке выбором выбирается элемент с наименьшим значением и делается его обмен с первым элементом массива. Затем находится элемент с наименьшим значением из оставшихся n-1 элементов и делается его обмен со вторым элементом и так далее до обмена двух последних элементов.
Например, если сортировку выбором применить для массива "2 4 1 3", то будут получены следующие проходы:
- исходное состояние: 2 4 1 3;
- первый проход: 1 4 2 3;
- второй проход: 1 2 4 3;
- третий проход: 1 2 3 4.
В этом методе внешний цикл выполняется n-1 раз, а внутренний цикл выполняется n/2 раз. Это значит, что число сравнений для сортировки выбором равно 1/2(n2-n) и эта сортировка будет выполняться слишком медленно для большого числа элементов. Число операций обмена в наилучшем случае равно 3(n-1), а в худшем случае равно n2/4+3(n-1). В лучшем случае (когда исходный массив уже упорядочен) потребуется поменять местами только n-1 элементов, а каждая операция обмена требует три операции пересылки.
{ сортировка выбором }
procedure Seleсt(var A: MyArray; n:integer);
var i, j, k, v: integer;
begin
for i:= i to n-1 do begin
k:= i;
v:= A[i];
for j:= i+1 to n do { найти элемент с наименьшим значением }
if A[j]<v then begin
k:= j;
v:= A[j];
end;
A[k]:= A[i]; { обмен }
A[i]:= v;
end;
end; { конец сортировки выбором }
Несмотря на одинаковое число операций сравнений для сортировок пузырьковым методом и сортировок выбором, число операций обмена для среднего случая будет значительно меньшим для сортировки выбором.
Сортировка вставкой
Сортировка вставкой является последней из класса простых алгоритмов сортировки. При сортировке вставкой сначала упорядочиваются два элемента массива. Затем делается вставка третьего элемента в соответствующее место по отношению к первым двум элементам. Затем делается вставка четвертого элемента в список из трех элементов. Этот процесс повторяется до тех пор, пока все элементы не будут упорядочены.
Например, для массива "4 3 1 2" сортировка вставкой будет проходить cледующим образом:
- исходное состояние: 4 3 1 2;
- первый проход: 3 4 1 2;
- второй проход: 1 3 4 2;
- третий проход: 1 2 3 4.
Ниже приводится алгоритм сортировки вставкой:
{ сортировка вставкой }
procedure Inser(var A: MyArray; n:integer);
var i, l,v: integer;
begin
for i:= 2 to n do begin
v:= A[i];
j:= i-1;
while (v<A[j]) and (j>0) do begin
A[j+1]:= A[j];
j:= j-1;
end;
A[j+1]:= v;
end;
end; { конец сортировки вставкой }
В отличие от сортировки пузырьковым методом и сортировки выбором число операций сравнения для сортировки вставкой зависит от исходной упорядоченности массива элементов. Если исходный массив уже упорядочен, то число операций сравнения равно n-1. Если массив упорядочен в обратном порядке, то число операций сравнения равно 1/2(n2 +n)-1, давая в среднем значение 1/4 (n2+n-2). Число операций обмена будет следующим: - для лучшего случая: 2 (n-1); - в среднем: 1/4 (n2+9n-10); - для худшего случая: 1/2 (n2+3n-4).
Таким образом, число операций обмена для худшего случая будет столь же большим, как и для сортировок пузырьковым методом и сортировок выбором. Число операций обмена для среднего случая будет лишь на немного меньше. Однако сортировка вставкой имеет два преимущества.
Во-первых, она обладает естественным поведением, т.е. она выполняется быстрее для упорядоченного массива и дольше всего выполняется, когда массив упорядочен в обратном направлении. Это делает сортировку вставкой полезной для упорядочения почти отсортированных массивов.
Во-вторых, элементы с одинаковыми ключами не переставляются: если список элементов сортируется с использованием двух ключей, то после завершения сортировки вставкой он по-прежнему будет упорядочен по двум ключам. Несмотря на то, что число сравнений может быть довольно небольшим для определенных наборов данных, постоянные сдвиги массива требуют выполнения большого числа операций пересылок. Однако, сортировка вставкой имеет естественное поведение, требуя наименьшее число операций обмена для почти упорядоченного списка и наибольшее число операций обмена, когда массив упорядочен в обратном направлении.
