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

Сортировка вставками

Это ещё один простой способ сортировки. Здесь поступательно обрабатываются отрезки массива, начиная с первого элемента и затем расширяя подмассив, вставляем на своё место очередной неотсортированный элемент.

Для вставки используется буферная область памяти, в которой хранится элемент, ещё не оказавшийся на своём место (так называемый ключевой элемент). В подмассиве, начиная с правого края, просматриваются элементы и сравниваются с ключевым. Если больше ключевого, то очередной элемент сдвигается на одну позицию вправо, освобождая место для последующих элементов. Если в результате этого перебора попадается элемент, меньший или равный ключевому, то значит в текущую свободную ячейку можно вставить ключевой элемент. Тот же оптимизированный «гномик», но только для обмена используется буфер.

Временная сложность у этой сортировки пропорционально квадрату от количества данных, но не это главное. Сортировка вставками, судя по всему — наиболее эффективный вариант для почти отсортированных массивов. Этот факт используется в некоторых сложных алгоритмах сортировки. Таких, как FlashSort [33.], там при помощи вероятностного распределения быстро создаётся почти отсортированный массив, который затем доупорядочивается сортировкой вставками. Сортировка вставками используется в финальной части JSort [34.], где путём построениянеполной кучи массив оперативно почти сортируется. Timsort [35.] начинает сортировку массива с нахождения в нём почти упорядоченных отрезков, они также сортируются вставочным методом, а затем объединяются модифицированной сортировкой слиянием.

Хотя сортировка вставками сама по себе работает медленно, потенциал у алгоритма огромен [36.].

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

Поиск перебором

Чтобы найти какие-то данные в неупорядоченном массиве, применяется алгоритм простого перебора элементов. Следующая функция возвращает индекс заданного элемента массива. Её аргументы: массив с первым индексом 0, количество элементов в массиве и искомое число. Если число не найдено, возвращается -1. [37.]

function SearchPer (Arr : array of Integer; n, v : Integer) : Integer;
var
i : Integer;
begin
Result := -1;
for i := 1 to n do
if Arr [i] = v then begin
Result := i;
Exit;
end;
end;

---

Бинарный поиск

При поиске в упорядоченном массиве можно применить гораздо более быстрый метод поиска - бинарный. Суть его в следующем: В начале переменная Up указывает на самый маленький элемент массива (Up := 0), Down - на самый большой (Down := n, где n - верхний индекс массива), а Mid - на средний. Дальше, если искомое число равно Mid, то задача решена; если число меньше Mid, то нужный нам элемент лежит ниже среднего, и за новое значение Up принимается Mid + 1;и если нужное нам число меньше среднего элемента, значит, оно расположено выше среднего элемента, и Down := Mid - 1. Затем следует новая итерация цикла, и так повторяется до тех пор, пока не найдётся нужное число, или Up не станет больше Doun. [38.]

function SearchBin (Arr : array of Integer; v, n : Integer) : Integer;
var
Up, Down, Mid : Integer;
Found : Boolean;
begin
Up := 0; Down := n;
Found := False; Result := -1;
repeat
Mid := Trunc ((Down - Up) / 2) + Up;
if Arr [Mid] = v then
Found := True
else
if v < Arr [Mid] then
Down := Mid – 1
else
Up := Mid + 1;
until (Up > Down) or Found;
if Found then
Result := Mid;
end;

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

Быстрая сортировка - очень эффективный алгоритм, и известна как в среднем самая быстрая из универсальных алгоритмов сортировки. Быстрая сортировка сравнивает все элементы массива с одним, выбранным практически наугад, элементом (опорным элементом) и тем самым делит массив на две части - в одну попадают числа меньшие опорного, а в другую - большие опорного. Затем каждая из этих двух частей также подвергается аналогичной сортировке, и так до тех пор, пока очередная часть не окажется состоящей из единственного элемента. Время сортировки пропорционально логарифму от количества элементов. По какому принципу делится массив? Выбираем элемент массива и относительно него все ячейки уходят в две группы — большие и меньшие этого элемента. Затем вызываем функцию сортировки для каждой из наших появившихся частей. Думаю, результат таких действий можно предугадать — все элементы массива найдут свои законные места.

Назначение: хаотично заполненные массивы (для частично упорядоченных массивов оптимальным методом будет пузырьковая сортировка). Не рекомендуется пробовать на достаточно длинных списках данных — выполнение цикла с рекурсией в таких случаях может привести к переполнению стека, аварийному выходу программы и прочим нехорошим вещам.[39.]

procedure QuickSort(var X: array of integer; min,max: Integer);
Var
i, j, mid, tmp: integer;
Begin
if min<max then
begin
mid:=X[min];
i:=min-1;
j:=max+1;
while i<j do
begin
repeat i:=i+1;
until X[i]>=mid;
repeat j:=j-1;
until X[j]< =mid;
if i<j then
begin
tmp:=X[i];
X[i]:=X[j];
X[j]:=tmp;
end;
end;
QuickSort(X, min, j);
QuickSort(X, j+1, max);
end;
end;

---

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

Сортировку Шелла придумал Дональд Шелл в 1959 году. Метод Шелла (англ. Shell sort) Сортировка Шелла— алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Дональда Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга; иными словами — это сортировка вставками, но с предварительными «грубыми» проходами.

Аналогичный метод усовершенствования «пузырьковой» сортировки называется «сортировка расчёской». Для этого сначала нужно сравнивать не соседей, а элементы, между которыми достаточно внушительное расстояние. Это позволяет на начальном этапе маленькие значения закинуть поближе к началу массива, большие – поближе к концу. Затем уменьшая разрыв, мы сортируем уже намного быстрее. . Суть алгоритма заключается в том, чтобы вначале устранить массовый беспорядок в массиве, сравнивая далеко стоящие друг от друга элементы. Как видно из кода, интервал между сравниваемыми элементами постепенно уменьшается до единицы. В итоге на поздних стадиях сортировка сводится просто к перестановкам соседних элементов (разумеется, если такие перестановки являются необходимыми).

Временная сложность у «шелла» – достаточно сложный вопрос. Дело в том, что до сих пор нет строгой формулы, по которой строится оптимальный числовой ряд изменяющихся расстояний между элементами в подгруппах. Последовательность строится эмпирически, на основании многочисленных тестов с различными входными данными и последнее наилучшее уточнение для вышеупомянутых «дельт» было определено в 2001 году:

1, 4, 10, 23, 57, 132, 301, 701. [40.]

Эффективность сортировки Шелла, — в определённых случаях, — обеспечивается тем, что элементы «быстрее» встают на свои места (в простых методах сортировки, — например, пузырьковой, — каждая перестановка двух элементов уменьшает количество инверсий в списке максимум на 1, а при сортировке Шелла — это число может быть больше).

Невзирая на то, что сортировка Шелла во многих случаях медленнее, чем быстрая сортировка — она имеет ряд преимуществ:

Отсутствие потребности в памяти под стек;

Отсутствие деградации при неудачных наборах.

Реализация на C [41.]
// BaseType - любой перечисляемый тип
// typedef int BaseType – пример
void ShellsSort(BaseType *A, unsigned N)
{
BaseType t;
for(unsigned k = N/2; k > 0; k /= 2)
for(unsigned i = k; i < N; i += 1)
{
t = A[i];
unsigned j;
for(j = i; j >= k; j -= k)
{
if(t < A[j-k])
A[j] = A[j-k];
else
break;
}
A[j] = t;
}
}

---

Сортировка подсчётом

Особый метод, где собственно не используются привычные для нас операции сравнения элементов. Алгоритм работает невероятно быстро, если элементами массива являются целые числа, со значениями, которые занимают, относительно узкий диапазон. Пока выполняются эти условия, алгоритм работает отлично. Для примера можно привести результат сортировки 1 миллиона элементов со значением от 1-10000, на том же компьютере с процессором Pentium-133. Время быстрой сортировки было равно 3,93 секунды, результат же сортировки подсчётом был 0,37 секунды, то есть быстрее в 10 раз.[42.]

procedure CountingSort(var X: array of integer; min, max: integer);
var
counter: array[0..100000] of integer;
i, j, index: Integer;
begin
// для всех элементов массива
// указываем значение ноль
for i:=0 to high(counter)
do tmpX[i]:=0;
for i:=min to max
do counter[ar[i]]:=counter[ar[i]]+1;
// устанавливаем значение
// в правильную позицию
index:=min;
for i:=min to high(counter)-1 do
begin
for j:=0 to counter[i]-1 do
begin
ar[index]:=i;
index:=index+1;
end;
end;
end;

Глупая сортировка

Глупая сортировка (англ. Stupid sort) — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Время работыагоритма пропорционально третьей степени от количества элементов. [43.]

В действительности под глупыми сортировками часто подразумевают совершенно другие алгоритмы, в частности Bogosort [44.]. Термин «глупая сортировка» очень перегружен и лучше избегать его использования, или по крайней мере уточнять, о какой именно глупой сортировке идёт речь в том или ином контексте.

Имеет нечто общее с сортировкой пузырьком: идёт поиск от начала массива, текущий элемент сравнивается со следующим, если следующий меньше, то производится обмен и возврат в начало цикла.

Пример реализации на С

// A - сортируемый массив, n - количество элементов
void stupidSort(int *A, int n)
{
int i = 0, tmp;
while (i < n - 1)
{
if (A[i+1] < A[i])
{
tmp = A[i];

A[i] = A[i+1];
A[i+1] = tmp;
i = 0;
}
else i++;
}
}

Пирамидальная сортировка

Пирамидальная сортировка ( англ. Heapsort, «Сортировка кучей» [45.]) — алгоритм сортировки, работающий в худшем, в среднем и в лучшем случае (то есть гарантированно) за время, пропорциональное (n log n) операций при сортировке n элементов.

Может рассматриваться как усовершенствованная сортировка пузырьком, в которой элемент всплывает) / тонет) по многим путям.

Пирамидальная сортировка была предложена Дж. Уильямсом в 1964 году.

---

Достоинства:

- имеет доказанную оценку худшего случая;

- сортирует на месте, то есть практически не требует дополнительной памяти.

Недостатки:

- сложен в реализации;

- неустойчив;

- на почти отсортированных массивах работает столь же долго, как и на хаотических данных.

На одном шаге выборку приходится делать хаотично по всей длине массива — поэтому алгоритм плохо сочетается с кэшированием и подкачкой памяти.

Методу требуется «мгновенный» прямой доступ; не работает на связанных списках и других структурах памяти последовательного доступа.

Из-за сложности алгоритма выигрыш получается только на больших n. На небольших n (до нескольких тысяч) быстрее сортировка Шелла.

Пример реализации:

static void HeapSort(int[] a)
{
int i;
int temp;
for (i = a.Length / 2 - 1; i >= 0; i--)
{
shiftDown(a, i, a.Length);
}

for (i = a.Length - 1; i >= 1; i--)
{
temp = a[0];
a[0] = a[i];
a[i] = temp;
shiftDown(a, 0, i);

}
}

static void shiftDown(int[] a, int i, int j)
{
bool done = false;
int maxChild;
int temp;

while ((i * 2 + 1 < j) && (!done))
{
if (i * 2 + 1 == j - 1)
maxChild = i * 2 + 1;
else if (a[i * 2 + 1] > a[i * 2 + 2])
maxChild = i * 2 + 1;

Else
maxChild = i * 2 + 2;

if (a[i] < a[maxChild])
{
temp = a[i];
a[i] = a[maxChild];
a[maxChild] = temp;
i = maxChild;
}
else
{
done = true;
}
}
}

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

Быстрая сортировка, сортировка Хоара (англ. QuickSort), часто называемая qsort (по имени в стандартной библиотеки языка Си) — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.

Один из самых быстрых известных универсальных алгоритмов сортировки массивов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками.

Быстрая сортировка является существенно улучшенным вариантом алгоритма сортировки с помощью прямого обмена (его варианты «Пузырьковая сортировка» и «Шейкерная сортировка»). Принципиальное отличие состоит в том, что в первую очередь производятся перестановки на наибольшем возможном расстоянии и после каждого прохода элементы делятся на две независимые группы. Любопытный факт: улучшение самого неэффективного прямого метода сортировки дало в результате один из наиболее эффективных улучшенных методов.

Общая идея алгоритма состоит в следующем:

Выбрать из массива элемент, называемый опорным. Это может быть любой из элементов массива или же число, вычисленное на основе значений элементов; от выбора этого числа сильно зависит эффективность алгоритма.

Сравнить все остальные элементы с опорным и переставить их в массиве так, чтобы разбить массив на три непрерывных отрезка, следующие друг за другом: «меньшие опорного», «равные» и «большие». [39.]

---