Файл: Методы сортировки данных: эволюция и сравнительный анализ. Примеры использования (Данные).pdf

Глава 3. Методы сортировки численных данных

Сортировка представляет собой процесс упорядочения множества подобных информационных объектов в порядке возрастания или убывания их значений. Например, список i из n элементов будет отсортирован в порядке возрастания значений элементов, если i <= i <= ... <= i.

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

Классификация алгоритмов сортировки

Количество алгоритмов сортировки достаточно велико. В третьем томе монографии Дональда Кнута "Искусство программирования для ЭВМ" [20.] рассматривается более двадцати (примерно 25) алгоритмов сортировки. В настоящее время это число ещё больше увеличилось, и, вместе с экзотическими и мало распространёнными алгоритмами, приближается к 40 (и даже уже превышает 40, а с модификациями ещё больше, 42-44, скорее всего и эти цифры заниженные). Все эти алгоритмы можно классифицировать по нескольким признакам.

1. В зависимости от того, сортируются данные в оперативной памяти машины (ОЗУ) или во внешнем ЗУ, сортировка бывает внутренней или внешней (В настоящее время, благодаря огромной памяти компьютеров, этот признак стал несущественным)

2. В зависимости от того, какая структура данных подвергается сортировке, может быть сортировка массива, связного списка, дерева (пирамиды), графа.

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

4. По особенностям функциональной реализации алгоритмы сортировки делятся на группы:

А. Основные:
− сортировка перестановками (обменная);
− сортировка выбором (отбором);
− сортировка вставками;
Б. Неосновные:
− сортировка подсчетом;
− сортировка слиянием;
− распределяющая сортировка.

---

5. По широте применения − универсальные (большинство перечисленных выше групп алгоритмов) и алгоритмы для конкретных случаев.

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

7. По характеру зависимости времени работы от размера N структуры данных:

− алгоритмы, время работы которых пропорционально второй степени от количества данных -квадратичные (это самые простые);

− алгоритмы, время работы которых пропорционально k степени от количества данных, где 1<k<2 (например, k = 1,6667 или k = 1,5 или k = 1,27 и т.п. − это алгоритм Шелла); возможен также случай, когда k = 3 − это один из самых неудачных и неэффективных алгоритмов, который получил название глупая сортировка (или дурацкая сортировка);

− алгоритмы, время работы которых пропорционально логарифму от количества данных по основанию 2 (log2N) − логарифмические (например, быстрая сортировка или пирамидальная сортировка).

Возможны также некоторые другие принципы разделения алгоритмов сортировки.

При таком большом разнообразии важными оказываются критерии выбора алгоритма:

− средняя скорость сортировки (среднее время, удельная скорость);

− скорость в лучшем и худшем случаях (или минимальное и максимальное время);

− естественность поведения;

− переставляются ли элементы с совпадающими значениями (ключами).

Скорость (или время) сортировки определяется количеством операций сравнения и перестановки. У разных алгоритмов время работы находится в экспоненциальной или логарифмической зависимости от числа элементов структуры данных (массива) N.

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

Естественность поведения означает, что если массив уже упорядочен, должно выполняться минимальное число операций (в идеале 0). Максимальное число операций выполняется, если массив отсортирован в обратном порядке.

Кроме перечисленных критериев при выборе алгоритма следует принимать во внимание:

---

− размер структуры данных, которую предстоит сортировать (некоторые алгоритмы, высокоэффективные в средних случаях, например быстрая сортировка, не показывают своей высокой эффективности для массивов малого размера);

− степень исходной упорядоченности сортируемых данных;

− требования к необходимой памяти (разным алгоритмам может требоваться объём памяти машины, пропорциональный количеству данных или квадрату от этого колчества);

− трудоёмкость реализации алгоритма в сравнении со сложность решаемой в программе задачи (например, пирамидальная сортировка является одним из самых сложных алгоритмов).

Наиболее известные алгоритмы сортировки

1. Алгоритмы устойчивой сортировки

1.1. Сортировка пузырьком (англ. Bubble sort) ;

1.2. Сортировка перемешиванием (англ. Cocktail sort);

1.3. Гномья сортировка (англ. Gnome sort);

1.4. Сортировка вставками (англ. Insertion sort);

1.5. Сортировка слиянием (англ. Merge sort) ;

1.6. Сортировка с помощью двоичного дерева (англ. Tree sort);

1.7. Сортировка Timsort (англ. Timsort) — комбинированный алгоритм (используется сортировка вставками и сортировка слиянием;

1.8. Сортировка подсчётом (англ. Counting sort);

1.9. Блочная сортировка (Корзинная сортировка, англ. Bucket sort);

1.10. Поразрядная сортировка (она же цифровая сортировка).

2. Алгоритмы неустойчивой сортировки

2.1. Сортировка выбором (англ. Selection sort);

2.2. Сортировка Шелла (англ. Shell sort);

2.3. Сортировка расчёской (англ. Comb sort);

2.4. Пирамидальная сортировка (сортировка кучи, англ. Heapsort);

2.5. Плавная сортировка (англ. Smoothsort);

2.6. Быстрая сортировка (англ. Quicksort);

2.7. Интроспективная сортировка (англ. Introsort), сочетание быстрой и пирамидальной сортировки;

2.8. Терпеливая сортировка (англ. Patience sorting);

2.9. англ. Stooge sort — рекурсивный алгоритм сортировки с временной сложностью.

3. Непрактичные алгоритмы сортировки

3.1. Bogosort. Произвольно перемешать массив, проверить порядок.

3.2. Сортировка перестановкой . Для каждой пары осуществляется проверка верного порядка и генерируются всевозможные перестановки исходного массива.

3.3. Глупая сортировка (Stupid sort)

4. Требующие специального аппаратного обеспечения

4.1. Bead Sort;

4.2. Блинная сортировка (англ. Pancake sorting) .

5. Алгоритмы, не основанные на сравнениях

5.1. Блочная сортировка (Корзинная сортировка, англ. Bucket sort);

5.2. Лексикографическая или поразрядная сортировка (англ. Radix sort);

5.3. Сортировка подсчётом (англ. Counting sort)

6. Прочие алгоритмы сортировки

---

6.1. Топологическая сортировка

6.2. Внешняя сортировка

Глава 4. Примеры программной реализации сортировок

Сортировка пузырьком

Сортировка пузырьком (англ. bubble sort) - это самый естественный, он же самый медленный алгоритм сортировки. Эффективен он лишь для небольших массивов. Алгоритм считается учебным и практически не применяется вне учебной литературы, вместо него на практике применяются более эффективные алгоритмы сортировки. В то же время метод сортировки обменами лежит в основе некоторых более совершенных алгоритмов, таких как шейкерная сортировка, пирамидальная сортировка и быстрая сортировка.

Массив чисел просматривается от начала до конца до тех пор, пока любые два рядом стоящих числа не будут расположены по возрастанию. Для этого два неверно расположенные одно относительно другого числа меняются местами. При этом наименьшее число, как пузырёк, постепенно всплывает к началу массива ( а наибольшее сразу "тонет" как камень!), отсюда и название алгоритма. Время сортировки пузырьком растёт пропорционально квадрату роста количества элементов в массиве.

Пример процедуры, реализующей алгоритм сортировки методом пузырька (Arr - массив для сортировки с начальным индексом 0, n - размерность массива [29.].

procedure SortPuz (var Arr : array of Integer; n : Integer);
var
i : Integer;
Temp : Integer;
Flag : Boolean;
begin
repeat
Flag := False;
for i := 0 to n - 1 do
if Arr [i] > Arr [i + 1] then begin
Temp := Arr [i];
Arr [i] := Arr [i + 1];
Arr [i + 1] := Temp;
Flag := True;
end;
until Flag = False;
end;

void bubble_sort(int *a, int length)
{
for (int i = 0; i < length-1; i++) {
bool swapped = false;
for (int j = 0; j < length-i-1; j++) {
if (a[j] > a[j+1]) {
int b = a[j];
a[j] = a[j+1];
a[j+1] = b;
swapped = true;
}
}
if(!swapped)
break;
}
}

Шейкерная сортировка

Алгоритм сортировки пузырьком можно немного улучшить, сделав следующее:

Внутренний цикл можно модифицировать так, чтобы он поочерёдно просматривал массив то с начала, то с конца. Модифицированный таким образом алгоритм называется сортировкой перемешиванием или шейкерной сортировкой. По сути, она является разновидность пузырьковой сортировки, вот только в то время, как минимальные значения плывут к одному концу массива, максимальные идут к его дну. Итог, разумеется, один — массив становится упорядоченным.

Этот метод может использоваться для сортировки больших массивов; в том числе — расположенных не в оперативной памяти, а на жёстком диске.

---

Время выполнения в данном случае заметно меньше.

Вот образец кода: [30.]

while e>s do
begin
for i:=s to e-1 do
if X[i]>X[i+1] then
begin
tmp:=X[i];
X[i]:=X[i+1];
X[i+1]:=tmp;
end;
for i:=e downto s+1 do
if X[i]<x [i-1] then
begin
tmp:=X[i];
X[i]:=X[i-1];
X[i-1]:=tmp;
end;
s:= s+1;
e:= e-1;
end;

Здесь S — первый элемент массива, а E — последний. В данном коде по умолчанию эти значения уже известны. Когда максимальный элемент встал в один конец, а минимальный в другой, то промежуток сортировки сужается на единицу с обоих концов массива — S:=S+1; E:=E-1.

Сортировка методом нахождения минимального элемента

Ещё один вариант сортировки, более быстрый, чем метод пузырька. Заключается он в следующем: при каждом просмотре массива находим минимальный элемент и меняем местами его с первым на первом проходе, со вторым - на втором и т.д. [31.]

procedure SortMin (var Arr : array of Integer; n : Integer);
var
i, j : Integer;
Min, Pos, Temp : Integer;
begin
for i := 0 to n - 1 do begin
Min := Arr [i];
Pos := i;
for j := i + 1 to n do
if Arr [j] < Min then begin
Min := Arr [j];
Pos := j;
end;
Temp := Arr [i];
Arr [i] := Arr [Pos];
Arr [Pos] := Temp;
end;
end;

Гномья сортировка

Хотя гномам этот способ известен уже много столетий, человеческая раса о нём узнала совсем недавно. Уже 55 лет как человечество использовало сортировку слиянием, прошло 40 лет как стала известна быстрая сортировка, уже 35 лет как разработана пирамидальная сортировка – и вот, только в 2000 году, этот бесхитростный, практически детский приём, был впервые описан Диком Груном [32.]:

Гномья сортировка основана на технике, используемой обычным голландским садовым гномом (нидерл. tuinkabouter). Это метод, которым садовый гном сортирует линию цветочных горшков. По существу он смотрит на следующий и предыдущий садовые горшки: если они в правильном порядке, он шагает на один горшок вперёд, иначе он меняет их местами и шагает на один горшок назад. Граничные условия: если нет предыдущего горшка, он шагает вперёд; если нет следующего горшка, он закончил.

Разумеется, люди предложили способ по улучшению, до которого не додумались консервативные лилипуты. Если запоминать место в котором встретилось неотсортированное недоразумение и сделать несколько корректирующих итераций назад, то после наведения порядка в тылах, можно прыгнуть сразу туда где прервались и следовать по массиву далее.Так немного быстрее, хотя принципиально это временную сложность не улучшает, она как была так и остаётся пропорциональна квадрату от количества данных. Но зато это приводит нас не только к новому способу сортировки, а даже к целому новому классу сортировок. И имя этой группе алгоритмов – «Сортировки вставками».

---