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

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

1. Таким образом, сначала сравниваются удаленные элементы (и, если необходимо, переставляются), а соседние элементы сравниваются на последнем проходе.
2. Усиление получается благодаря тому, что на каждом этапе сортировки задействовано относительно немного элементов, или эти элементы уже достаточно хорошо упорядочены, и требуется небольшое количество перестановок. Последнее представление сортировки Shell выполняется по тому же алгоритму, что и при сортировке челнока. Предыдущие представления аналогичны представлениям обработки челнока, но они сравнивают не смежные элементы, а элементы, которые отделены заданным расстоянием h. Большой шаг на начальных этапах сортировки позволяет сократить количество вторичных сравнений на более поздних этапах.
3. При анализе этого алгоритма возникают довольно сложные математические проблемы, многие из которых еще не решены. Например, неизвестно, какая последовательность расстояний дает наилучшие результаты, хотя было обнаружено, что расстояния h1 не должны быть множителями друг друга. Мы можем порекомендовать следующие последовательности (они написаны в обратном порядке):
4. 1, 4, 13, 40, 121, ... , где h_k-1=3h_k+1, h_p=1 и p=log₂n-1
5. 1, 3, 7, 15, 31, ... , где h_k-1=2h_k+1, h_p=1 и p=log₂n-1

В приложении[рис.4] изображена демонстрация сортировки Шелла.

Общий метод, который использует сортировку включением, применяет принцип уменьшения расстояния между сравниваемыми элементами. Сначала сортируются все элементы, смещенные друг от друга на позиции. Затем сортируются все элементы, которые смещены на две позиции. И, наконец, упорядочиваются все соседние элементы [4].

Метод, предложенный Дональдом Л. Шеллом, является неустойчивой сортировкой. Эффективность метода Шелла объясняется тем, что сдвигаемые элементы быстро попадают на нужные места. Среднее время для сортировки Шелла равняется O(nlg²n) [1].

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

Этот алгоритм получил свое название благодаря тому, что используемое здесь частично упорядоченное дерево сортировки имеет форму «пирамиды». Отметим также, что в русском издании книги [3] этот метод сортировки называется «разновидностью дерева», то есть упорядочением по дереву сортировки [1].

Этот метод сортировки был предложен J.W.J. Уильямс и Р. У. Флойд в 1964 г.

Метод пирамидальной сортировки - это улучшение традиционной сортировки с помощью дерева [6].

Сортировка основана на использовании структуры данных - пирамиды (дерево сортировки, куча). Пирамида - это двоичное дерево, для которого выполняются условия:

1. Значение в любой вершине не меньше, чем значения ее потомков.

2. Глубина листьев (расстояние до корня) отличается не более чем на 1 слой.

3. Последний слой заполняется слева направо.

Наиболее наглядный способ построения пирамиды выглядит в виде дерева массива, показанного в приложении [рис. 5]. Массив представлен в виде двоичного дерева, корень которого соответствует элементу массива a [1]. На втором уровне находятся элементы a [2] и a [3]. На третьем - a [4], a [5], a [6], a [7] и т. Д. Как видно, для массива с нечетным числом элементов соответствующее дерево будет сбалансировано, а длямассив с четным числом элементов n, элемент a [n] будет единственным (самым левым) листом «почти» сбалансированного дерева [6].

На [рис. 6] приложение показывает, как сортировать, используя построенную пирамиду. Суть алгоритма заключается в следующем. Позвольте мне быть наибольшим индексом массива, для которого условия пирамиды являются значимыми. Затем, начиная с [1] до [i], выполняются следующие действия. На каждом шаге выбирается последний элемент пирамиды (в нашем случае элемент a [8] будет выбран первым). Его значение изменяется вместе со значением a [1], после чего a [1] просеивается. Более того, на каждом шаге число элементов в пирамиде уменьшается на 1 (после первого шага a [1], a [2], ..., a [n-1] рассматриваются как элементы пирамиды; a [1], a [2], ..., a [n-2] и т. Д., Пока один элемент не останется в пирамиде) [5].

Процедура сортировки по пирамиде требует выполнения ≈n log n шагов (логарифм является двоичным) в худшем случае, что делает его особенно привлекательным для сортировки больших массивов [8].

3.2.3.Сортировка методом Xoapa (быстрая сортировка)

Применение принципа «разделяй и властвуй» в сортировке приводит нас к одному алгоритму сортировки, который важен в информатике, с которым знаком каждый программист, к алгоритму, который мы имеем в виду, когда говорим о сортировке, без каких-либо мыслей об алгоритмах. Этот алгоритм называется быстрой сортировкой; он был разработан C.E.P. (Toni) Xoap в 1961 году [5].

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

Суть метода заключается в следующем. Мы найдем такой элемент массива, который разделит весь массив на два подмножества: те, которые меньше, чем разделяющий элемент, и те, которые не меньше его (то есть, сортируют один элемент по определение его конечного местоположения) [3].

Затем примените ту же процедуру к более коротким левому и правому подмножествам.

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

Точка разделения массива может быть определена следующим образом.

Введены два указателя i и j, и в начале i = слева, а j = вправо. I-й и j-й элементы сравниваются и, если обмен не требуется, тогда j = j + 1, и этот процесс повторяется, После первого обмена i увеличивается на единицу (i = i + 1), и сравнения продолжаются с увеличением i до следующего обмена. Затем снова уменьшайте j и т. Д. До тех пор, пока i = j. К моменту i = j элемент aj займет свою конечную позицию, так как не будет больше элементов слева и меньших элементов справа. Таким образом, проблема решена [6]. Демонстрация метода представлена ​​на [рис. 7] в приложении.

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

Общий анализ эффективности «быстрой» сортировки довольно сложен. Было бы лучше показать его вычислительную сложность, посчитав количество сравнений при некоторых идеальных допущениях. Предположим, что n является степенью двойки, n = 2k (k = log2n), и центральный элемент расположен точно посередине каждого списка и разбивает его на два подсписка примерно одинаковой длины [4].

Во время первого сканирования выполняется n-1 сравнение. В результате создаются два подсписка размером n / 2. На следующем этапе обработка каждого подсписка требует приблизительно n / 2 сравнений. Общее количество сравнений на этом этапе составляет 2 (n / 2) = n. На следующем этапе обрабатываются четыре подсписка, что требует 4 (n / 4) сравнений и т. Д. В конце процесс разделения заканчивается после k проходов, когда результирующие подсписки содержат по одному элементу за раз. Общее количество сравнений составляет примерно

n + 2 (n / 2) + 4 (n / 4) + ... + n (n / n) = n + n + ... + n = n * k = n * log2n

Для общего списка вычислительная сложность «быстрой» сортировки составляет O (n log2 n) [4].

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

3.2.4 Сравнение методов внутренней сортировки

Для простых методов сортировки, обсуждаемых в начале этой части, существуют точные формулы, вычисление которых дает минимальное, максимальное и среднее количество ключевых сравнений (C) и передач элементов массива (M). Таблица 1 в приложении содержит данные, приведенные в книге Никласа Вирта [2]

Нет точных формул для оценки сложности продвинутых методов сортировки. Известно только, что для сортировки по методу Шелла порядок C и M равен O (n (1.2)), а для методов быстрой сортировки, Heapsort и сортировки со слиянием - O (n log n). Тем не менее, результаты экспериментов показывают, что Quicksort показывает результаты, которые в 2-3 раза лучше, чем Heapsort (Таблица 2 показывает выборку результатов из таблицы, опубликованной в книге Wirth; результаты были получены при запуске программ, написанных на Modula-2) , По этой причине Quicksort обычно используется в стандартных утилитах сортировки (в частности, в утилите сортировки, поставляемой с операционной системой UNIX) [7].

4. Методы внешней сортировки

Обычно файлы сортировки, расположенные во внешней памяти, слишком велики, чтобы полностью перенести их в основную память и применить один из внутренних методов сортировки, описанных в предыдущем разделе. Чаще всего внешняя сортировка используется в системах управления базами данных при выполнении запросов, и производительность СУБД существенно зависит от эффективности используемых методов [1].

Следует уточнить, почему речь идет о последовательных файлах, то есть файлах, которые могут быть прочитаны запись за записью в последовательном режиме, и вы можете писать только после последней записи. Внешние методы сортировки появились, когда магнитные ленты были наиболее распространенными устройствами внешней памяти. Для лент чисто последовательный доступ был совершенно естественным. Когда произошел переход к устройствам хранения с магнитными дисками, обеспечивающими «прямой» доступ к любому блоку информации, казалось, что чисто последовательные файлы утратили свою актуальность. Однако это чувство было ошибочным [6].

Дело в том, что почти все используемые в настоящее время дисковые устройства оснащены подвижными магнитными головками. При замене с дисководом головки подаются в требуемый цилиндр, выбираются требуемые головки (дорожки), блок дисков прокручивается до начала требуемого блока и, наконец, блок считывается или записывается. Среди всех этих действий самое большое время - доставка голов. Это время определяет общее время операции. Единственный доступный метод оптимизации доступа к магнитным дискам - это «ближайшее» расположение на диске последовательно адресуемых файловых блоков. Но в этом случае движение головок будет минимизировано только тогда, когда файл будет прочитан или записан в чисто последовательном режиме. Именно с такими файлами современные СУБД работают с необходимостью сортировки [1].

Следует также отметить, что на самом деле скорость выполнения внешней сортировки зависит от размера буфера (или буферов) основной памяти, который можно использовать для этих целей. Рассмотрим основные методы внешней сортировки, работающие с минимальными затратами основной памяти [6].

4.1.Прямое слияние

Сортировка с слиянием, как правило, используется в тех случаях, когда требуется отсортировать последовательный файл, который не умещается полностью в основной памяти [3].

Предположим, что существует последовательный файл A, состоящий из записей a1, a2, ..., an (опять же, для простоты, предположим, что n - степень 2). Мы предполагаем, что каждая запись состоит только из одного элемента, который является ключом сортировки. Для сортировки используются два вспомогательных файла B и C (размер каждого из них будет n / 2).

Сортировка состоит из последовательности шагов, каждый из которых выполняет распределение состояния файла A по файлам B и C, а затем объединяет файлы B и C в файл A. На первом этапе файл A последовательно читается для распространения, и записи a1, a3, ..., a (n-1) записываются в файл B, а записи a2, a4, ..., an - в файл C (первоначальное распространение). Начальное объединение выполняется для пар (a1, a2), (a3, a4), ..., (a (n-1), an), и результат записывается в файл A. На втором этапе файл A снова читается последовательно, а файл B записывается последовательными парами с нечетными числами, а в файл C - с четными числами. При объединении упорядоченные четверки записей формируются и записываются в файл А. И так далее. Перед выполнением последнего шага файл A будет содержать две упорядоченные подпоследовательности размером n / 2 каждая. При распределении первый файл перейдет в файл B, а второй в файл C. После объединения файл A будет содержать полностью упорядоченную последовательность записей [5]. Таблица 3 в приложении показывает пример внешней сортировки путем простого слияния.