Лекция
№ 2
Тема: «Основные
виды сортировки. Алгоритмы внутренней
сортировки»
План
лекции
1. Основные виды сортировки
2. Алгоритмы внутренней сортировки
3. Сравнение алгоритмов внутренней сортировки
1.
Основные виды сортировки
Сортировка – это процесс упорядочения некоторого множества элементов, на котором определены отношения порядка >, <, ≥, ≤, =. Когда говорят о сортировке, подразумевают упорядочение множества элементов по возрастанию или убыванию. В случае наличия элементов с одинаковыми значениями, в упорядоченной последовательности они располагаются рядом друг с другом в любом порядке. Хотя иногда, бывает полезно сохранить первоначальный порядок элементов с одинаковыми значениями.
Алгоритмы сортировки имеют большое практическое применение. Их можно встретить почти везде, где речь идет об обработке и хранении больших объемов информации. Некоторые задачи обработки данных решаются проще, если данные упорядочены.
Традиционно различают внутреннюю сортировку, в которой предполагается, что данные находятся в оперативной памяти, и важно оптимизировать число действий программы (для методов, основанных на сравнении, число сравнений, обменов элементов и пр.), и внешнюю, в которой данные хранятся на внешнем устройстве с медленным доступом (диск, лента и т. д.) и, прежде всего, надо снизить число обращений к этому устройству.
2.
Алгоритмы внутренней сортировки
При дальнейшем рассмотрении внутренней сортировки определим, что множество данных, которые упорядочиваются, описывается как массив фиксированной длины:
A: array[1..n] of ItemType;
Обычно тип ItemType описывает запись с некоторым полем, играющим роль ключа, а сам массив представляет собой таблицу. Так как здесь рассматривается, прежде всего, сам процесс сортировки, то будем считать, что тип ItemType включает только ключ целого типа.
Сортировка
подсчетом
Суть метода заключается в том, что на каждом шаге подсчитывается, в какую позицию результирующего массива B надо записать очередной элемент исходного массива A (рис. 1). Если некоторый элемент A[i] помещается в результирующий массив в позицию k + 1, то слева от B[k + 1] должны стоять элементы меньшие или равные B[k + 1]. Значит, число k складывается из количества элементов меньших A[i] и, возможно, некоторого числа элементов, равных A[i]. Условимся, что из равных будут учитываться только те элементы, которые в исходном массиве стоят левее A[i]:
procedure
NumerSort(n: integer;
var A: array [1..n] of
integer);
{Процедура сортировки подсчетом}
var
i, j, k: integer;
B: array[1..n] of integer;
begin
for i := 1 to n do begin
{Вычисляем положение элемента в результирующем массиве}
k := 1;
for j := 1 to n do
if (A[j] < A[i]) or
((A[j] = A[i]) and (j < i)) then k
:= k+1;
{Включаем очередной элемент в результирующий массив}
B[k] := A[i];
end;
for i := 1 to n do A[i] := B[i];
end;
Рисунок 1 – Сортировка подсчетом
Легко видеть, что этот алгоритм всегда имеет временную сложность, пропорциональную O(n2) (два вложенных цикла, зависящих от n линейно и не зависящих от порядка элементов) и пространственную сложность, пропорциональную O(n) (результирующий массив). Также следует отметить, что данный алгоритм сохраняет порядок элементов с одинаковыми значениями.
Сортировка простым
включением
В этой сортировке массив делится на две части: отсортированную и неотсортированную. На каждом шаге берется очередной элемент из неотсортированной части и «включается» в отсортированную часть массива (рис. 2).
Пусть отсортировано начало массива A[1], A[2], ..., A[i–1], а остаток массива A[i], ..., A[n] содержит неотсортированную часть. На очередном шаге будем включать элемент A[i] в отсортированную часть, ставя его на соответствующее место. При этом придется сдвинуть часть элементов, больших A[i], (если таковые есть) на одну позицию правее, чтобы освободить место для элемента A[i]. Но при сдвиге будет потеряно само значение A[i], поскольку в эту позицию запишется первый (самый правый – с самым большим индексом) сдвигаемый элемент. Поэтому прежде чем производить сдвиг элементов необходимо сохранить значение A[i] в промежуточной переменной.
Так как массив из одного элемента можно считать отсортированным, начнем с i = 2.
Выглядит это в виде следующей процедуры:
procedure
InsertSort(n: integer;
var A: array[1..n] of integer);
{Процедура сортировки простым включением}
var
i, j, Tmp: integer;
begin
for i := 2 to n do begin
{Сохраняем текущий
элемент}
Tmp := A[i];
{Сдвигаем элементы, большие, чем текущий}
j := i;
while (A[j-1] > Tmp) and (j
> 1) do begin
A[j] := A[j-1];
j := j-1;
end;
{Вставляем текущий элемент}
A[j] := Tmp;
end;
end;
Рисунок 2 – Сортировка простым включением
Этот алгоритм также имеет максимальную и среднюю временную сложности, пропорциональные O(n2), но в случае исходно отсортированного массива внутренний цикл не будет выполняться ни разу, поэтому метод имеет временную сложность Tmin(n), пропорциональную O(n). Можно заметить, что метод использует любой частичный порядок, и чем в большей степени массив исходно упорядочен, тем быстрее он закончит работу. В отличие от предыдущего метода, этот не требует дополнительной памяти, но сохраняет порядок элементов с одинаковыми значениями.
Сортировка простым
извлечением.
В этом методе массив также делится на уже отсортированную часть A[i+1], A[i+1], ..., A[n] и еще не отсортированную A[1], A[2], ..., A[i]. Но здесь из неотсортированной части на каждом шаге извлекается максимальный элемент, просматривая ее заново на каждом шаге. Этот элемент будет минимальным элементом отсортированной части, так как все большие его элементы были извлечены на предыдущих шагах, поэтому ставим извлеченный элемент в начало отсортированной части, точнее меняем его с A[i] местами (рис. 4).
Рисунок 4 – Сортировка простым извлечением
Теперь запишем алгоритм.
procedure
ExtractSort(n: integer;
var A: array[1..n] of
integer);
{Процедура сортировки простым извлечением}
var
i, j, MaxIndex, Tmp: integer;
begin
for i := n downto 2 do begin
{Ищем максимальный элемент в неотсортированной части}
MaxIndex := 1;
for j := 2 to i do
if A[j] > A[MaxIndex] then MaxIndex :=
j;
{Меняем найденный элемент с первым из отсортированных}
Tmp := A[i]; A[i] := A[MaxIndex];
A[MaxIndex] := Tmp;
end;
end;
Простое извлечение во всех случаях имеет временную сложность, пропорциональную O(n2) (два вложенных цикла, зависящих от n линейно и не зависящих от порядка элементов). Также следует отметить, что данный алгоритм не требует дополнительной памяти и не гарантирует сохранение порядка элементов с одинаковыми значениями.
Сортировка методом
пузырька
Сортировка методом пузырька – один из наиболее широко известных алгоритмов сортировки. В этом методе массив также делится на две части: отсортированную и неотсортированную. На каждом шаге метода осуществляется просмотр от меньших индексов к большим по неотсортированной части, каждый раз сравнивая два соседних элемента. Если они не упорядочены между собой (меньший следует за большим), то меняем их местами. Тем самым за один проход путем последовательных обменов наибольший элемент неотсортированной части сдвинется к ее концу (рис. 5).
Алгоритм называют пузырьковой сортировкой, потому что на каждом шаге наибольший элемент неотсортированной части подобно пузырьку газа в воде всплывает к концу массива.
Заметим, что в том случае, когда за очередной проход не было сделано ни одного обмена, массив уже отсортирован, и следующие проходы можно пропустить. Для отслеживания такой ситуации введем логическую переменную Flag – признак совершения обмена на очередном проходе.
Теперь запишем алгоритм:
procedure
BubleSort(n: integer;
var A: array[1..n] of
integer);
{Процедура сортировки методом пузырька}
var
i, j, Tmp: integer;
Flag: boolean;
begin
for i := n-1 downto 1 do begin
Flag := false;
for j := 1 to i do
if A[j] > A[j+1] then begin
Tmp := A[j]; A[j] := A[j+1]; A[j+1] :=
Tmp;
Flag := true;
end;
if not Flag then Break;
end;
end;
Рисунок 5 – Сортировка методом пузырька
Этот алгоритм имеет среднюю и максимальную временные сложности, пропорциональную O(n2) (два вложенных цикла, зависящих от n линейно) и не требует дополнительной памяти. Введение переменной Flag и прерывание работы в случае отсортированного массива позволяет свести минимальную временную сложность к O(n). Также следует отметить, что данный алгоритм не требует дополнительной памяти и сохраняет порядок элементов с одинаковыми значениями.
3. Сравнение алгоритмов внутренней сортировки
Выше было рассмотрено достаточно большое количество алгоритмов внутренней сортировки. Возникает вопрос: зачем тогда нужно такое разнообразие алгоритмов сортировок, если есть возможность раз и навсегда определить алгоритм с наилучшим показателем эффективности и оставить «право на жизнь» исключительно за ним? Ответ прост: в реальных задачах имеются ограничения, определяемые как логикой задачи, так и свойствами конкретной вычислительной среды, которые могут существенно влиять на эффективность данной конкретной реализации алгоритма. Поэтому выбор того или иного алгоритма всегда остается за разработчиком программного обеспечения.
Теоретические временные и пространственные сложности рассмотренных методов сортировки показаны в табл. 1.
Эта таблица позволяет сделать ряд выводов.
1. На небольших наборах данных целесообразнее использовать сортировку включением, так как из всех методов, имеющих очень простую программную реализацию, этот на практике оказывается самым быстрым и при размерностях меньше ~3000 дает вполне приемлемую для большинства случаев скорость работы. Еще одно преимущество этого метода заключается в том, что он использует полную или частичную упорядоченность входных данных и на упорядоченных данных работает быстрее, а на практике данные, как правило, уже имеют хотя бы частичный порядок.
2. Алгоритм пузырьковой сортировки, причем в той его модификации, которая не использует частичный порядок данных исходного массива, хотя и часто используется, но имеет плохие показатели даже среди простых методов с квадратичной сложностью.
3. Сортировка Шелла оказывается лишь красивым теоретическим методом, потому что на практике использовать его нецелесообразно: он сложен в реализации, но не дает такой скорости, какую дают сравнимые с ним по сложности программной реализации методы.
4. При сортировке больших массивов исходных данных лучше использовать быструю сортировку.
5. Если же добавляется требование гарантировать приемлемое время работы метода (быстрая сортировка в худшем случае имеет сложность, пропорциональную O(n2), хотя вероятность такого случая очень мала), то надо применять либо древесную сортировку, либо сортировку слиянием. Как видно из таблиц, сортировка слиянием работает быстрее, но следует помнить, что она требует дополнительную память размером порядка n.
6. В тех же случаях, когда есть возможность использовать дополнительную память размером порядка n, имеет смысл воспользоваться сортировкой распределением.
Таблица 1 - Теоретические временные и пространственные сложности методов сортировки
Контрольные вопросы.
1. Что такое «сортировка»?
2. Сколько существует групп алгоритмов
сортировки?
3. Сколько существует алгоритмов сортировки?
4. По каким признакам характеризуются алгоритмы
сортировки?
5. Что нужно учитывать при выборе алгоритма
сортировки?
6. Какой алгоритм сортировки считается самым
простым?
7. Какой алгоритм сортировки считается самым
эффективным?
8. Что означает понятие «скорость сортировки»?
9. В чем заключается метод пузырьковой
сортировки?
10. В чем заключается метод сортировки отбором?
11. В чем заключается метод сортировки вставками?
12. В чем заключается метод сортировки
разделением?
13. В чем заключается метод быстрой сортировки?
14. В чем заключается метод сортировки Шелла?
16. Как зависит скорость сортировки от размера
структуры данных для разных алгоритмов?