47. Алгоритмы сортировки (обзор, классификация и сравнение различных алгоритмов). Пример

Алгоритм сортировки — это алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. На практике, в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма.
Оценка алгоритма сортировки
Единственного эффективнейшего алгоритма сортировки нет, ввиду множества параметров оценки эффективности:

Время — основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для упорядочения важны худшее, среднее и лучшее поведение алгоритма в терминах размера списка (n). Для типичного алгоритма хорошее поведение — это O(n log n) и плохое поведение — это O(n?). Идеальное поведение для упорядочения — O(n). Алгоритмы сортировки, использующие только абстрактную операцию сравнения ключей всегда нуждаются по меньшей мере в O(n log n) сравнениях в среднем;

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

Устойчивость (stability) — устойчивая сортировка не меняет взаимного расположения равных элементов.

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

Ещё одним важным свойством алгоритма является его сфера применения. Здесь основных типов упорядочения две:

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

• В современных архитектурах персональных компьютеров широко применяется подкачка и кэширование памяти. Алгоритм сортировки должен хорошо сочетаться с применяемыми алгоритмами кэширования и подкачки.

Внешняя сортировка оперирует с запоминающими устройствами большого объёма, но с доступом не произвольным, а последовательным (упорядочение файлов), т.е в данный момент мы 'видим' только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики. Это накладывает некоторые дополнительные ограничения на алгоритм и приводит к специальным методам упорядочения, обычно использующим дополнительное дисковое пространство. Кроме того, доступ к данным на носителе производится намного медленнее, чем операции с оперативной памятью.

• доступ к носителю осуществляется последовательным образом: в каждый момент времени можно считать или записать только элемент, следующий за текущим
• объём данных не позволяет им разместиться в ОЗУ

Пузырьковая сортировка.
Реализация данного метода не требует дополнительной памяти. Метод очень прост и состоит в следующем: берется пара рядом стоящих элементов, и если элемент с меньшим индексом оказывается больше элемента с большим индексом, то мы меняем их местами. Эти действия продолжаем, пока есть такие пары. Легко понять, что когда таких пар не останется, то данные будут отсортированными. Для упрощения поиска таких пар данные просматриваются по порядку от начала до конца. Из этого следует, что за такой просмотр находится максимум, который помещается в конец массива, а потому следующий раз достаточно просматривать уже меньшее количество элементов. Максимальный элемент как бы всплывает вверх, отсюда и название алгоритма. Так как каждый раз на свое место становится по крайней мере один элемент, то не потребуется более N проходов, где N - количество элементов. Вот как это можно реализовать:
Program BubbleSort;
Var A    : array[1..1000] of integer;
N,i,j,p : integer;
Begin
{Определение размера массива A (N) и его заполнение}
…
{сортировка данных}
for i:=1 to n do
for j:=1 to n-i do
if A[j]>A[j+1] then
begin  {Обмен элементов}
p:=A[j];
A[j]:=A[j+1];
A[j+1]:=P;
end;
{Вывод отсортированного массива A}
…
End.
Среднее число сравнений и обменов имеют квадратичный порядок роста: Theta(n2), отсюда можно заключить, что алгоритм пузырька очень медленен и малоэффективен.
Тем не менее, у него есть громадный плюс: он прост и его можно по-всякому улучшать.

Быстрая сортировка.
массив разбивается на две части, с условием, что все элементы первой части меньше любого элемента второй. Потом каждая часть сортируется отдельно. Разбиение на части достигается упорядочиванием относительно некоторого элемента массива, т. е. в первой части все числа меньше либо равны этому элементу, а во второй, соответственно, больше либо равны. Два индекса проходят по массиву с разных сторон и ищут элементы, которые попали не в свою группу. Найдя такие элементы, их меняют местами. Тот элемент, на котором индексы пересекутся, и определяет разбиение на группы. Классическая реализация алгоритма выглядит так:
Program QuickSort;
Var A  : array[1..1000] of integer;
N,T : integer;
Procedure Sort(p,q : integer); {p,q - индексы начала и конца сортируемой части массива}
Var i,j,r : integer;
Begin
if p<q then {массив из одного элемента тривиально упорядочен}
begin
r:=A[p];
i:=p-1;
j:=q+1;
while i<j do
begin
repeat
i:=i+1;
until A[i]>=r;
repeat
j:=j-1;
until A[j]<=r;
if i<j then
begin
T:=A[i];
A[i]:=A[j];
A[j]:=T;
end;
end;
Sort(p,j);
Sort(j+1,q);
end;
End;
Begin
{Определение размера массива A - N) и его заполнение}
…
{запуск сортирующей процедуры}
Sort(1,N);
{Вывод отсортированного массива A}
…
End.
Что же делает данный алгоритм таким быстрым? Ну во-первых, если массив каждый раз будет делится на приблизительно равные части, то для него будет верно соотношение время работы будет O(nlog2n). Это уже само по себе хорошо. Кроме того, константа при nlog2n очень мала, ввиду простоты внутреннего цикла программы. В комплексе это обеспечивает огромную скорость работы. Но как всегда есть одно «но». а что если массив не будет делится на равные части? Классическим примером является попытка «быстро» отсортировать уже отсортированный массив. При этом данные каждый раз будут делиться в пропорции 1 к n-1, и так n раз. Общее время работы при этом будет O(n2), тогда как вставкам, для того чтобы «понять», что массив уже отсортирован, требуется всего-навсего O(n). лучше всего сортировка сортирует случайные массивы (порядок элементов в массиве случаен). И поэтому нам предлагают ввести в алгоритм долю случайности. А точнее, вставить randomize и вместо r:=A[p]; написать r:=A[random(q-p)+p]; т. е. теперь мы разбиваем данные не относительно конкретного, а относительно случайного элемента. Благодаря этому алгоритм получает приставку к имени «вероятностный». Особо недоверчивым предлагаю на своем опыте убедится, что данная модификация быстрой сортировки сортирует любые массивы столь же быстро.
Быстрая сортировка потому быстрая, что в общем случае выполняется за N*log N времени, а пузырьком за O(n^2), что примерно означает, что если у нас 10 элементов , то выполнится за 100 с , а если 100 элементов, то за 100*100=10000 с.  В отличие от сортировки пузырьком в быстрой сортировке увеличение количества элементов к катастрофе не приводит.
Т.е. если было 10 элементов, то выполняется 100 секунд, а если 100, то не 10000, как в случае с пузырьковой, а всего 200.