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

Сортировка методом прочёсывания (comb sort) не относится к стандартным алгоритмам. На сегодняшний день он малоизвестен, тем не менее, он отличается достаточно быстрым уровнем быстродействия и удобной реализацией. Метод был разработан Стефаном Лейси (Stephan Lacey) и Ричардом Боксом (Richard Box) в 1991 году. Фактически он использует пузырьковую сортировку таким же образом, как и сортировка методом Шелла сортировку методом вставок.

Рис. 6 Сортировка методом прочёсывания

Перетасуйте карты и разложите на столе. Выделите 1 и 9 карту (расстояние между картами 8), если они находятся в неправильном порядке - поменяйте их местами. Выделите 2 и 10 карты (расстояние между картами 6) и, при необходимости, поменяйте их местами. То же самое проделайте для 3 и 11 карты (расстояние между картами 4), 4 и 12 карты (расстояние между картами 3), а затем 5 и 13 (расстояние между картами 2). Далее сравнивайте и переставляйте пары карт (1, 7), (2, 8), (3, 9), (4, 10), (5, 11), (6, 12) и (7, 13), т.е. карты отстоящие друг от друга на шесть позиций. А теперь выполните проход по разложенным картам, отстоящим друг от друга на четыре позиции, затем на три и две позиции, как показано на рисунке 6. После этого выполните стандартную пузырьковую сортировку.^[6]

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

Каким образом были получены значения расстояний 8, 6, 4 ,3, 2, 1? Разработчики этого метода сортировки провели большое количество экспериментов и эмпирическим путём пришли к выводу, что значение каждого последующего расстояния «прыжка» должно быть получено в результате деления предыдущего значения расстояния на 1,3.

Разработчики метода выявили, что сортировка методом причёсывания немного быстрее сортировки методом Шелла (на последовательности Д. Кнута). Очевидно, что данный вид сортировки также принадлежит к группе неустойчивых алгоритмов.

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

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

Метод пирамидальной сортировки более подробно изложен в книге Т. Кормена, Ч. Лейзерсона, Р. Ривеста и К. Штайн: «Алгоритмы: построение и анализ, 2-издание» и в учебном пособии для студентов вузов Л.Г. Гагариной и В.Д. Колдаева «Алгоритмы и структуры данных».

Метод сортирующего дерева основан на повторяющихся поисках наименьшего значения среди n элементов массива, среди оставшихся n-1 элементов и т.д. Например, сделав n/2 сравнений, можно определить в каждой паре значений меньшее значение. С помощью n/4 сравнений — меньшее значение из пары уже выбранных меньших и т. д. Проделав n - 1 сравнений, мы можем построить дерево выбора, вроде представленного на рисунке 7.1 и идентифицировать его корень как нужное нам наименьшее значение.

06

06

06

06

12

12

12

44

44

55

42

94

18

18

67

Рис. 7.1. Повторяющиеся выборы среди двух значений

Второй этап сортировки — спуск вдоль пути, отмеченного наи­меньшим элементом, и исключение его из дерева путем замены на пустой элемент (дырку), как показано на рисунке 7.2. ^[7]

12

12

12

44

44

55

42

94

18

18

67

Рис. 7.2. Исключение наименьшего значения

Эле­мент, передвинувшийся в корень дерева, как показано на рисунке 7.3, вновь будет наименьшим (теперь уже вторым) элементом, и его можно исключить. После n таких шагов дерево станет пустым (т. е. в нем останутся только пустые элементы - «дырки»), и процесс сортировки заканчивается.

12

18

67

12

12

12

44

44

55

42

94

18

18

67

Рис.7.3. Сдвигание элементов и заполнение пустых элементов (дырок)

Обратите внимание - на каждом из n шагов выбора требуется только log₂ n сравнений. Поэтому на весь процесс понадобится порядка n×log₂ n эле­ментарных операций плюс еще n шагов на построение дерева. Естественно, сохранение дополнительной информации делает за­дачу более изощренной, поэтому в сортировке по дереву увеличилась сложность отдельных шагов. Ведь для сохране­ния избыточной информации, получаемой при начальном прохо­де, создается некоторая древообразная структура.

Желательно избавиться от необходимости в пустых элементах (дырах), которые заполняют всё дерево и приводят к большому количеству ненужных сравнений. Дж. Уильямс в 1964 году предложил метод, названный пирамидальной сортировкой.

Пирамида определяется как последовательность ключей h_l, h_l+1,...,h_r, такая, что hi <= h_2i. и hi< =h_2i+1, для i =l,..., r/2.

Если любое двоичное дерево рассматривать как массив, представленный на рисунке 7.4, то можно говорить, что деревья сортировок, представленными на рисунках 7.5 и 7.6 являются пирамидами, а элемент h_l её наименьший элемент: h_l = min(h₁, h₂,…, h_n).

h₁

h₃

h₇

h₂

h₅

h₁₀

h₄

h₈

h₉

h₁₁

h₁₂

h₆

h₁₃

h₁₅

h₁₄

Рис. 7.4. Массив h, представленный в виде двоичного дерева

h₁

06

12

42

94

55

18

Рис.7.5. Пирамида из семи элементов.

Предположим, есть некоторая пи­рамида с заданными элементами hi,.., hr. Возьмем, в качестве примера, исходной пирамиду h1, ...,h7, показанную на рисунке 7.5, и расширим эту пирамиду влево, добавив к ней элемент h1 = 44.

Новый элемент, в нашем случае это - h1 = 44, сначала помещается в вершину дерева, а затем «просеивается» по пути, на котором находятся меньшие по сравнению с ним элементы, которые, в свою очередь, поднимутся вверх, так как их значение меньше помещаемого в дерево элемента. В нашем случае 44 меняется местами с 06, затем с 12, и так формируется дерево, показанное на рисунке 7.6.

06

122

44

42

94

55

18

Рис.7.6.Просеивание ключа - 44 через пирамиду.

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

Алгоритм быстрой сортировки (quicksort) был разработан К.А.Р. Хоаром (C.A.R. Hoare) в 1960 году. В настоящее время он является самым широко используемым в программировании методом сортировки, что вызвано его крайне положительными характеристиками: это алгоритм класса O(n×log(n)) для общего случая, он требует лишь незначительного объёма дополнительной памяти, работает с различными типами массивов и достаточно удобен для реализации. Также быстрая сортировка имеет несколько нежелательных характеристик: при его реализации допускается слишком много ошибок, быстродействие в худшем случае составляет O(n²) и к тому же она неустойчива.^[8]

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

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

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

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

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

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

После выбора базового элемента перейдём к описанию алгоритма разбиения массива. Будем оперировать с двумя индексами: первый будет использоваться для прохождения по элементам массива слева направо, второй - справа налево. Начинаем справа и идём к левому краю массива, сравнивая значение каждого элемента со значением базового элемента. Выполнение цикла завершается, если найден элемент, значение которого меньше или равно значению базового элемента. Это был внутренний цикл № 1: сравнение двух элементов и уменьшение значения индекса. Затем та же операция выполняется слева. Проход выполняется к правому концу массива. Значение каждого элемента сравнивается со значением базового элемента. Выполнение цикла завершается, если найден элемент, значение которого больше или равно значению базового элемента. Это был внутренний цикл № 2: сравнение двух элементов и увеличение значения индекса.^[9]

Заключение