Усовершенствованные алгоритмы сортировки

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

Сортировка Шелла

Сортировка Шелла получила свое название по имени ее создателя Д.Л.Шелла. Однако, это название можно считать удачным, так как выполняемые при сортировке действия напоминают укладывание морских ракушек друг на друга. ("Ракушка" - одно из значений слова shell - Примеч. пер.) Общий метод, который использует сортировку вставкой, применяет принцип уменьшения расстояния между сравниваемыми элементами.

На рис.2 показана схема выполнения сортировки Шелла для массива
"6 4 1 3 2 5". Сначала сортируются все элементы, которые смещены друг от друга на три позиции. Затем сортируются все элементы, которые смещены на две позиции. И, наконец, упорядочиваются все соседние элементы.

проход 1 6 4 1 3 2 5
проход 2 3 2 1 6 4 5
проход 3 1 2 3 5 4 6
полученный результат 1 2 3 4 5 6

{ сортировка Шелла }
procedure Shell (var A: MyArray; n:integer);
const
t = 5;
var
i, j, k, s, m: integer;
h: array[1..t] of integer;
v: Integer;
begin
h[1]:=9; h[2]:=5; h[3]:=3; h[4]:=2; h[5]:=1;
for m := 1 to t do begin
k:=h[m];
s:=-k;
for i := k+1 to n do begin
v := A[i];
j := i-k;
if s=0 then begin
s := -k;
s := s+1;
A[s] := v;
end;
while (v<A[j]) and (j<n) do begin
A[j+k] := A[j];
j := j-k;
end;
A[j+k] := v;
end;
end;
end; { конец сортировки Шелла }

При поверхностном взгляде на алгоритм нельзя сказать, что он дает хороший результат и даже то, что в результате получится отсортированный массив. Однако, он дает и то и другое. Эффективность этого алгоритма объясняется тем, что при каждом проходе используется относительно небольшое число элементов или элементы массива уже находятся в относительном порядке, а упорядоченность увеличивается при каждом новом просмотре данных. Расстояния между сравниваемыми элементами могут изменяться по-разному. Обязательным является лишь то, что последний шаг должен равняться единице. Например, хорошие результаты дает последовательность шагов 9, 5, 3, 2, 1, которая использована в показанном выше примере. Следует избегать последовательностей степени двойки, которые, как показывают сложные математические выкладки, снижают эффективность алгоритма сортировки (тем не менее, при использовании таких последовательностей шагов между сравниваемыми элементами эта сортировка будет по-прежнему работать правильно).

Внутренний цикл имеет два условия проверки. Условие "v<A[j]" необходимо для упорядочения элементов. Условия "j>0"и "j<=n" необходимы для того, чтобы предотвратить выход за пределы массива "A". Эта дополнительная проверка в некоторой степени ухудшает сортировку Шелла. Слегка измененные версии сортировки Шелла используют специальные управляющие элементы, которые не являются в действительности частью той информации, которая должна сортироваться. Управляющие элементы имеют граничные для массива данных значения, т.е. наименьшее и наибольшее значения. В этом случае необязательно выполнять проверку на граничные значения. Однако применение таких управляющих элементов требует специальных знаний о той информации, которая сортируется, и это снижает универсальность процедуры сортировки. Время выполнения сортировки Шелла пропорционально n^1.2. Эта зависимость значительно лучше квадратичной зависимости, которой подчиняются рассмотренные ранее алгоритмы сортировки.

Быстрая сортировка

Метод быстрой сортировки был разработан Ч.Ф.Р. Хоаром и он же дал ему это название. В настоящее время этот метод сортировки считается наилучшим. Он основан на использовании обменного метода сортировки. Это тем более удивительно, если учесть очень низкое быстродействие сортировки пузырьковым методом, который представляет собой простейшую версию обменной сортировки. В основе быстрой сортировки лежит принцип разбиения. Сначала выбирается некоторое значение в качестве "основы" и затем весь массив разбивается на две части. Одну часть составляют все элементы, равные или большие "основы", а другую часть составляют все элементы меньшего значения, по которому делается разбиение. Этот процесс продолжается для оставшихся частей до тех пор, пока весь массив не будет отсортирован.

Например, для массива "6 5 4 1 3 2" при использовании в качестве значения разбиения "4 " будут получены следующие проходы при выполнении быстрой сортировки:

- исходное состояние: 6 5 4 1 3 2;

- первый проход: 4 3 1 4 5 6;

- второй проход: 1 2 3 4 5 6.

Этот процесс продолжается для каждой части "2 3 1" и "4 5 6". Фактически этот процесс имеет рекурсивную природу. И действительно, наиболее "аккуратно" быстрая сортировка реализуется посредством рекурсивного алгоритма.

Выбор значения разбиения можно сделать двумя способами. Это значение можно выбирать случайным образом или путем усреднения небольшого числа значений, выбранных из массива. Для оптимальной сортировки требуется выбрать значение, которое будет находиться в точности посередине всех элементов. Однако для большинства наборов данных это сделать нелегко. Но даже в худшем случае, когда выбирается одно из экстремальных значений, быстрая сортировка работает достаточно хорошо. В приводимом ниже алгоритме быстрой сортировки в качестве значения разбиения используется среднее значение. Хотя такой подход не всегда является наилучшим, он достаточно прост и сортировка будет выполняться правильно.

{ быстрая сортировка }
procedure QuickSort(var A: MyArray; n:integer);
procedure qs(l, r: integer; var mas: MyArray);
var i, j: integer; v, y: Integer;
begin
i:=l; j:=r;
v:=mas[(l+r) div 2];
repeat
while mas[i]<v do i := i+1;
while v<mas[j] do j := j-1;
if y<=j then begin
y := mas[i];
mas[i] := mas[j];
mas[j] := y;
i := i+1; j := j-1;
end;
until i>j;
if l<j then qs(l, j, mas);
if l<r then qs(i, r, mas)
end;
begin
qs(1, n, A);
end; { конец быстрой сортировки }

В данном примере процедура быстрой сортировки обращается к основной процедуре сортировки с именем "qs". Это обеспечивает доступ к данным "A" и "n" при всех вызовах "qs". Вывод числа операций сравнения и числа операций обмена для быстрой сортировки выходит за рамки данной книги. Можно считать, что число операций сравнения равно n log n, а число операций обмена равно приблизительно
n/6 log n. Эти характеристики значительно лучше характеристик рассмотренных ранее сортировок. Равенство n = a^x можно представить в виде v = log n·a. Это, например, будет означать, чо при сортировке 100 элементов методом быстрой сортировки потребуется в среднем 100*2, т.е.200 операций сравнений, так как log 100 равен 2. Это значение является вполне хорошим по сравнению со значением 990 для сортировки пузырьковым методом. Однако, следует иметь в виду одно неприятное свойство быстрой сортировки. Если выбираемое для разбиения значение оказывается совпадающим с максимальным значением, то быстрая сортировка превращается в самую медленную с временем выполнения n. Однако, на практике этот случай не встречается. Необходимо тщательно выбирать метод определения значения разбиения. Часто это значение определяется по фактическим данным, которые сортируются. Для больших списков почтовых отправлений, когда сортировка часто делается по коду почтового индекса, значение для разбиения выбрать не сложно, так как коды почтовых индексов распределены достаточно равномерно и требуемое значение можно определить с помощью простой алгебраической процедуры. Однако, определенные базы данных могут иметь ключи сортировки с очень близкими значениями и поэтому наилучшим методом часто оказывается случайный выбор значения. Распространенный и достаточно эффективный метод заключается в выборке трех элементов из соответствующей области и вычисление их среднего значения.

МЕТОДЫ ПОИСКА

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

Поиск информации в не отсортированном массиве требует проведения последовательного просмотра массива. Просмотр начинается с первого элемента и завершается либо найденным элементом, либо достижением конца массива. Этот метод должен использоваться для неотсортированных данных, но он также может использоваться для отсортированных данных. Если данные отсортированы, то может использоваться двоичный поиск, который выполняется значительно быстрее.

Последовательный поиск

Алгоритм последовательного поиска имеет очень простой вид. Ниже представлена функция, которая выполняет поиск в символьном массиве заданной длины элемента с заданным значением ключа:

function Search(A: MyArray; n:integer; key:Integer):integer;
var
t:integer;
begin
t:=1;
while (key<>A[t]) and (t<=n) t:=t+1;
if t>n then Search:=0
else Search:=t;
end; { конец последовательного поиска }

Эта функция выдает либо значение индекса для найденного элемента массива, либо нулевое значение, когда требуемый элемент не найден. При прямом последовательном поиске в среднем проверяются n/2 элементов. В лучшем случае будет проверяться только один элемент, а в худшем случае будут проверятся n элементов. Если информация размещается на диске, то поиск может быть очень долгим. Однако, если данные не отсортированы, то последовательный поиск является единственным возможным в данном случае методом поиска.

Двоичный поиск

Если данные отсортированы, то может использоваться очень хороший метод поиска, названный двоичным поиском. Сначала производится проверка среднего элемента. Если его ключ больше ключа требуемого элемента, то делается проверка для среднего элемента из первой половины. В противном случае делается проверка среднего элемента из второй половины. Этот процесс повторяется до тех пор, пока не будет найден требуемый элемент или не будет больше элементов для проверки. Например, для поиска числа 4 в массиве 1 2 3 4 5 6 7 8 9 указанным методом сначала делается проверка среднего элемента, которым является число 5. Поскольку этот элемент больше 4, поиск будет продолжен в первой половине массива, т.е. среди чисел 1 2 3 4 5. Здесь средним элементом является 3. Это значение меньше 4 и поэтому первая половина не будет больше рассматриваться и поиск продолжается среди чисел 4 и 5. На следующем шаге нужный элемент будет найден. При двоичном поиске число сравнений в худшем случае равно log n. Для среднего случая это значение будет несколько лучше, а в лучшем случае оно равно единице.