Файл: Алгоритмы сортировки данных.pdf

Четвертый этап продолжался с середины 1970-х до середины 1990-х годов. Появление вычислительных центров, объединяющих мощности отдельных вычислительных машин и позволяющих работать с разделением времени потребовало разработки новых алгоритмов сортировки и модификации существующих. Началось исследование задач сортировки в классе параллельных алгоритмов, были достигнуты значительные успехи в увеличении скорости сортировки за счет повышения эффективности уже известных к тому времени алгоритмов путем их доработки или комбинирования. Одновременно происходил поиск оптимальных входных последовательностей для разных методов сортировки, что позволяло значительно сократить ее время.

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

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

Именно поэтому исследование различных алгоритмов сортировки данных так важно. Настоящие методы сортировки данных выполняют множество прикладных задач. Они достаточно изучены, но всегда возможны новые открытия, которые необходимы для продолжения процесса их совершенствования.

Глава 2. Алгоритмы сортировки: применение на практике и сравнение эффективности

---

2.1. Анализ основных алгоритмов сортировки данных

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

Итак, далее будут перечислены 10 основных алгоритмов сортировки данных.

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

Код на языке Pascal:

const

m = 10;

var

arr: array[1..m] of integer;

i, j, k: integer;

begin

randomize;

write ('Исходный массив: ');

for i := 1 to m do begin

arr[i] := random(256);

write (arr[i]:4);

end;

writeln; writeln;

for i := 1 to m-1 do

for j := 1 to m-i do

if arr[j] > arr[j+1] then begin

k := arr[j];

arr[j] := arr[j+1];

arr[j+1] := k

end;

write ('Отсортированный массив: ');

for i := 1 to m do

write (arr[i]:4);

writeln;

readln

end.

Сортировка перемешиванием — разновидность пузырьковой сортировки. Отличается тем, что просмотры элементов выполняются один за другим в противоположных направлениях, при этом большие элементы стремятся к концу массива, а маленькие — к началу. Лучший случай для этой сортировки — отсортированный массив (О(n)), худший — отсортированный в обратном порядке (O(n²)).

Код на языке Pascal:

k:= 25; {Индекс последнего изменения}

s:= 1; {Первый элемент массива}

e:= 25; {Последний элемент массива}

while e > s do

begin

for i:= e downto s+1 do if Arr[i] < Arr[i-1] then

begin

tmp := Arr[i];

Arr[i] := Arr[i-1];

Arr[i-1] := tmp;

k := i;

end;

s:=k;

for i:= s to e-1 do if Arr[i]>Arr[i+1] then

begin

tmp := Arr[i];

Arr[i] := Arr[i+1];

Arr[i+1] := tmp;

k := i;

end;

e:=k;

end;

Сортировка вставкой — Это изящный и простой для понимания метод. Вот в чем его суть: создается новый массив, в который мы последовательно вставляем элементы из исходного массива так, чтобы новый массив был упорядоченным. Вставка происходит следующим образом: в конце нового массива выделяется свободная ячейка, далее анализируется элемент, стоящий перед пустой ячейкой (если, конечно, пустая ячейка не стоит на первом месте), и если этот элемент больше вставляемого, то подвигаем элемент в свободную ячейку (при этом на том месте, где он стоял, образуется пустая ячейка) и сравниваем следующий элемент. Так мы прейдем к ситуации, когда элемент перед пустой ячейкой меньше вставляемого, или пустая ячейка стоит в начале массива. Помещаем вставляемый элемент в пустую ячейку.

---

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

Код данного алгоритма, написанного на языке Pascal, представлен ниже:

Program InsertionSort;

Var A,B : array[1..1000] of integer;

N,i,j : integer;

Begin

{Определение размера массива A (N) и его заполнение}

…

{сортировка данных}

for i:=1 to N do

begin

j:=i;

while (j>1) and (B[j-1]>A[i]) do

begin

B[j]:=B[j-1];

j:=j-1;

end;

B[j]:=A[i];

end;

{Вывод массива B}

…

End.

Это очень простой алгоритм сортировки. Этот метод сортировки уступает в эффективности более сложным алгоритмам. Однако, у него есть ряд своих преимуществ:

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

Анализ производительности данного метода: сортировка вставками имеет сложность n2, количество сравнений вычисляется по формуле n*(n-1)/2. То есть, при n=100 количество перестановок равно 4950, а не 10000 если бы мы высчитывали по формуле n2.

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

Сортировка подсчетом - алгоритм сортировки массива, при котором подсчитывается число одинаковых элементов. Алгоритм выгодно применять, когда в массиве много элементов, но все они достаточно малы.

Идея сортировки указана в её названии — нужно подсчитывать число элементов, а затем выстраивать массив. Пусть, к примеру, имеется массив A из миллиона натуральных чисел, меньших 100. Тогда можно создать вспомогательный массив B из 99 (1..99) элементов, «пробежать» весь исходный массив и вычислять частоту встречаемости каждого элемента — то есть если A[i]=a, то B[a] следует увеличить на единицу. Затем «пробежать» счетчиком i массив B, записывая в массив A число i B[i] раз.

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

---

Цифровая сортировка - обладает линейной вычислительной сложностью (О(n)), что является лучшей возможной производительностью для алгоритма сортировки, так как в любом таком алгоритме каждый сортируемый элемент необходимо просмотреть хотя бы однажды. Однако, применение алгоритма цифровой сортировки целесообразно лишь тогда, когда сортируемые предметы имеют (или их можно отобразить в) диапазон возможных значений, который достаточно мал по сравнению с сортируемым списком. Эффективность алгоритма падает всякий раз, когда несколько различных элементов попадает в одну ячейку. Необходимость сортировки внутри ячеек лишает алгоритм смысла, так как каждый элемент придётся просматривать более одного раза. Так что, для простоты и с целью отличить «классическую» цифровую сортировку от её многочисленных вариантов, укажем, что подсчёт должен быть обратимым: если два элемента попадают в одну ячейку, то они должны иметь одинаковое значение. Несколько элементов с одним значением в одной ячейке не портят картину — их можно просто вставить в отсортированный список рядом, один за другим (это позволяет применять цифровую сортировку в качестве устойчивой).

Алгоритм цифровой сортировки действует следующим образом:

• Создаём массив изначально пустых «ячеек», по одной для каждой величины из диапазона ключей.
• Просматриваем изначальный массив, помещая каждый его элемент в свою ячейку.
• Проходим по массиву ячеек в нужном порядке и переносим элементы из непустых ячеек обратно в первоначальный массив.

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

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

Сортировка методом выбора — алгоритм сортировки, относящийся к неустойчивым алгоритмам сортировки. На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае Θ(n2), предполагая, что сравнения делаются за постоянное время.

Шаги алгоритма:

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

---

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

Существует также двунаправленный вариант сортировки методом вставок, в котором на каждом проходе отыскивается и устанавливается на своё место и минимальное, и максимальное значения.

Сортировка методом Шелла - Идея алгоритма состоит в обмене элементов, расположенных не только рядом, как в сортировке методом вставок, но и далеко друг от друга, что значительно сокращает общее число операций перемещения элементов.

Для примера возьмем файл из 16 элементов. Сначала просматриваются пары с шагом 8. Это пары элементов 1-9, 2-10, 3-11, 4-12, 5-13, 6-14, 7-15, 8-16. Если значения элементов в паре не упорядочены по возрастанию, то элементы меняются местами. Назовем этот этап 8-сортировкой. Следующий этап — 4-сортировка, на котором элементы в файле делятся на четверки: 1-5-9-13, 2-6-10-14, 3-7-11-15, 4-8-12-16. Выполняется сортировка в каждой четверке.

Следующий этап — 2-сортировка, когда элементы в файле делятся на 2 группы по 8: 1-3-5-7-9-11-13-15 и 2-4-6-8-10-12-14-16. Выполняется сортировка в каждой восьмерке. Наконец весь файл упорядочивается методом вставок. Поскольку дальние элементы уже переместились на свое место или находятся вблизи от него, этот этап будет значительно менее трудоемким, чем при сортировке вставками без предварительных «дальних» обменов.

Пирамидальная сортировка - алгоритм сортировки, работающий в худшем, в среднем и в лучшем случае (т.е. гарантированно) за О(n log n) операций при сортировке n элементов. Сортировка пирамидой использует сортирующее дерево. Сортирующее дерево – это такое двоичное дерево, у которого выполнены условия:

• Каждый лист имеет глубину либо d либо d-1;
• Значение в любой вершине больше, чем значения ее потомков.

Удобная структура данных для сортирующего дерева – такой массив Array, что Array[1] – элемент в корне, а потомки элемента Array[i] - Array[2i] и Array[2i+1].

Быстрая сортировка — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром. Даёт в среднем O(n log n) сравнений при сортировке n элементов. В худшем случае, однако, получается O(n2) сравнений. Обычно на практике быстрая сортировка значительно быстрее, чем другие алгоритмы с оценкой O(n log n), по причине того, что внутренний цикл алгоритма может быть эффективно реализован почти на любой архитектуре, и на большинстве реальных данных можно найти решения, которые минимизируют вероятность того, что понадобится квадратичное время.

---