Добавлен: 16.05.2023
Просмотров: 75
Скачиваний: 3
Пирамидальная сортировка представляет собой так называемую сортировку на месте и не нуждается в дополнительной памяти. На ее основе хорошо видно,как работают кучи и как происходит сохранение полного бинарного дерева в массиве. И хотя производительность O(nlog(n)) высока для алгоритма, сортирующего путем сравнений, далее пойдет речь об алгоритме, который показывает еще более быстрые результаты.
Приведенный ниже алгоритм делит массив на две части и впоследствии рекурсивно вызывает сам себя для их сортировки.
Листинг 7 – Псевдокод быстрой сортировки
Quicksort(Data: values[], Integer: start, Integer: end)
<Выбираем элемент из массива. Называем его разделяющим элементом.>
<Переносим элементы, которые меньше разделяющего, в начало массива.>
<Переносим элементы, которые больше разделяющего или равны ему, в конец массива. >
<Пусть серединой будет индекс, где помещен разделяющий элемент.>
// Рекурсивно сортируем две части массива.
Quicksort(values, start, middle - 1)
Quicksort(values, middle + 1, end)
End Quicksort
В верхней части рисунка 10 показан массив для сортировки. В качестве разделяющего элемента выбрано первое значение 6. На среднем фрагменте значения, которые меньше, чем разделяющий элемент, были перемещены в начало массива, а значения, которые больше или равны ему, – в конец. Разделяющий элемент с индексом 6 закрашен темно-серым Обратите внимание, что еще один элемент массива со значением 6 следует за разделителем.
Рисунок 10 – Быстрая сортировка
Далее алгоритм рекурсивно вызывает сам себя, чтобы отсортировать части массива до и после разделяющего элемента. Результат этого процесса показан на нижнем фрагменте рисунка 10.
Перед тем как приступить к подробному анализу алгоритма, изучим время его работы.
Для начала рассмотрим особый случай, когда при каждом шаге разделяющий элемент делит анализируемый массив пополам (рис. 11).
Рисунок 11 – Разделение массива
В каждой вершине дерева, изображенного на рисунке 11, происходит обращение к алгоритму быстрой сортировки. Толстыми линиями отмечено разделение массива надвое. Стрелки символизируют алгоритм быстрой сортировки, он вызывает себя дважды – для каждой половины массива. Внизу дерева вызов осуществляется единожды (и возвращается, ничего не сделав), поскольку список из одного элемента уже отсортирован. Достигнув последнего уровня в пирамидальной структуре данных, вызовы начинают возвращаться к собственным методам – так происходит контроль снизу вверх.
Если изначально в массиве содержится n элементов и они разделены четко по-полам, дерево вызовов быстрой сортировки имеет высоту log(n) уровней. При каж-дом вызове проверяются элементы в той части массива, которая подвергаетсясортировке. Например, в массиве из четырех элементов будут исследованы все четыре элемента с целью последующего разделения их значений.
Все элементы из исходного массива представлены на каждом уровне дерева. Та-ким образом, любой уровень содержит n элементов. Если добавить те, которые должен проверять каждый вызов быстрой сортировки на определенном уровне дерева, получится n элементов. Это значит, что вызовы быстрой сортировки потребуют n шагов. Поскольку дерево имеет высоту log(n) уровней и для каждого из них нужно n шагов, общее время работы алгоритма составит O(n log(n)).
Подобный алгоритм предполагает разделение массива на две равные части прикаждом шаге, что выглядит не очень правдоподобно. Однако в большинстве случаевразделяющий элемент будет отстоять недалеко от середины — не точно по центру,но и не с самого края. Например, на рисунке 10 на среднем фрагменте разделяющий элемент 6 находится хотя и не ровно посередине, но близко к ней. В этом случае алгоритм быстрой сортировки все еще обладает временем работы O(n log(n)). В худшем случае разделяющий элемент может оказаться меньше любого другого в той части массива, которую делит, либо все они будут иметь равные значения.
Тогда ни один из элементов не перейдет в левую часть массива — все, кроме разделяющего, окажутся в правой. Первый рекурсивный вызов вернется немедленно, поскольку сортировка не понадобится, зато в ходе второго потребуется обработать почти каждый элемент. Если первому вызову быстрой сортировки надо отсортировать n элементов, то рекурсивному – n – 1.
Если разделяющий элемент всегда меньше остальных в сортируемой части массива, алгоритм вызывается для сортировки вначале n элементов, затем n – 1, n – 2 и т. д. В таком случае дерево вызовов, изображенное на рисунке 11, является очень тонким и имеет высоту n.
Вызовы быстрой сортировки на уровне i в дереве должны проверить n – i элементов. Суммирование всех элементов, проверяемых на всех вызовах, даст n + (n – 1) + (n – 2) + ... + 1 = n(n + 1)/2, что равняется O(). Таким образом, в худшем случае время работы алгоритма составит O(). Кроме вышесказанного, следует обратить внимание на требуемый объем памяти. Он частично зависит от метода, с помощью которого массив делится на части, а также от глубины рекурсии алгоритма. Если последовательность рекурсивных вызовов слишком глубока, программа расходует стековое пространство и зависнет.
В примере с деревом, изображенным на рисунке 11, алгоритм быстрой сортировки рекурсивно вызывает сам себя до глубины n. Таким образом, в ожидаемом случае стек вызова программы будет иметь глубину O(log(n)) уровней. Для большинства компьютеров это не проблема. Даже если в массиве содержится 1 млрд элементов, в log(n) их всего 30, а стек вызова должен обладать возможностью работать с 30 рекурсивными вызовами. Однако в худшей ситуации, когда дерево высокое и тонкое, глубина рекурсии составит n. Немногие программы способны создать стек вызова с 1 млрд рекурсивных вызовов. Вы можете избежать наихудшего сценария, если заставите алгоритм работать в течение разумного времени и с разумной глубиной рекурсии путем тщательного выбора разделяющего элемента. В следующих подразделах рассматриваются необходимые для этого стратегии, приводятся два метода разделения массива на части, а также резюмируются сведения по использованию быстрой сортировки на практике.
В качестве разделяющего элемента можно использовать первый элемент из той части массива, которая сортируется. Это простой и, как правило, эффективный способ. К сожалению, если массив изначально отсортирован в прямом или обратном порядке, ситуация окажется наихудшей. Лучше всего, если элементы располагаются в случайном порядке, но чаще сортировка является частичной или полной. Решить проблему поможет предварительная рандомизация массива перед вызовом быстрой сортировки. Если элементы расположены в случайном порядке,
маловероятно, что описанный метод каждый раз будет выбирать плохой разделяющий элемент, и мы получим худший вариант его работы. В главе 2 рассказывалось, как рандомизировать массив за время O(n) и не увеличить при этом ожидаемую производительность алгоритма быстрой сортировки O(n log (n)). Однако на практике для работы с большим массивом требуется довольно много времени, поэтому опытные программисты не используют такой метод.
Можно прибегнуть к другому варианту: определить первый, последний и средний элементы в сортируемой части массива и использовать в качестве разделителя элемент, чье значение находится между любыми двумя значениями из этого трио. Нет абсолютной гарантии, что результат не будет приближаться к наибольшему или наименьшему элементу в данной части массива, однако незначительная вероятность есть.
И наконец, последний метод заключается в том, чтобы выбрать случайный индекс из сортируемой части массива, а затем использовать в качестве разделителя значение элемента с данным индексом. Маловероятно, что каждый такой выбор приведет к плохому результату и худшему варианту работы алгоритма.
3.3 Сортировка слиянием
Подобно быстрой сортировке, сортировка слиянием использует стратегию «разделяй и властвуй». Если в первом случае выбирается разделитель, а оставшиеся элементы делятся на две группы — большие и меньшие его, то во втором разделение происходит на две равные части, а затем алгоритм рекурсивно вызывает сам себя для их сортировки. Потом отсортированные половины сливаются в комбинированный отсортированный список. Описанный алгоритм представлен в следующем псевдокоде.
Листинг 8 – Псевдокод сортировки слиянием
Mergesort(Data: values[], Data: scratch[], Integer: start, Integer: end)
// Если в массиве только один элемент — он отсортирован.
If (start == end) Then Return
// Разбиваем массив на левую и правую половины.
Integer: midpoint = (start + end) / 2
// Вызываем Mergesort для сортировки двух половин.
Mergesort(values, scratch, start, midpoint)
Mergesort(values, scratch, midpoint + 1, end)
// Соединяем отсортированные половины.
Integer: left_index = start
Integer: right_index = midpoint + 1
Integer: scratch_index = left_index
While ((left_index <= midpoint) And (right_index <= end))
If (values[left_index] <= values[right_index]) Then
scratch[scratch_index] = values[left_index]
left_index = left_index + 1
Else
scratch[scratch_index] = values[right_index]
right_index = right_index + 1
End If
scratch_index = scratch_index + 1 End While
// Завершаем копирование из непустой половины.
For i = left_index To midpoint
scratch[scratch_index] = values[i]
scratch_index = scratch_index + 1
Next i
For i = right_index To end
scratch[scratch_index] = values[i]
scratch_index = scratch_index + 1
Next i
// Копируем значения в исходный массив.
For i = start To end
values[i] = scratch[i]
Next i
End Mergesort
Кроме сортируемых массивов, начального и конечного индексов, алгоритм также берет в качестве параметра рабочий массив, который использует для объединения отсортированных половин.
Код начинает работу с проверки общего количества элементов в части массива. Если элемент один, значит, массив отсортирован и алгоритм прекращает выполняться. Если элементов несколько, алгоритм рассчитывает индекс того, что находится в середине части, и рекурсивно вызывает сам себя для сортировки половин. Затем отсортированные половины объединяются. Они пересматриваются в цикле, при этом меньший элемент копируется в рабочий массив. Если одна половина пуста, алгоритм копирует остальные элементы из другой половины. На завершающем этапе объединенные элементы из рабочего массива переносятся обратно в исходный массив values
Анализ времени работы для быстрой сортировки применим и для сортировки слиянием. Таким образом, производительность рассмотренного выше алгоритма составит O(n log(n)). Как и в случае пирамидальной сортировки, она не зависит от изначального расположения элементов, поэтому всегда одинакова. Нет здесь и худшего варианта, как в быстрой сортировке. Сортировку слиянием тоже можно распараллелить. Когда алгоритм рекурсивно вызывает сам себя, он вправе передать один из таких вызовов другому процессору. Однако это требует некоторой координации: исходный вызов должен подождать, пока оба рекурсивных вызова закончатся, чтобы объединить их результаты. Быстрая сортировка, напротив, может приказать рекурсивным вызовам отсортировать определенную часть массива и не ждать их возвращения.
Сортировка слиянием особенно полезна, когда данные не содержатся в памяти единовременно. Например, программе нужно отсортировать 1 млн записей о клиентах, каждая из которых занимает 1 Мбайт. Для комплексной загрузки данных ей понадобится 1018 байт памяти, или 1000 Тбайт, что намного больше, чем в основной массе компьютеров. Сортировка слиянием не требует такого количества ресурсов, алгоритму даже не нужно обращаться к элементам массива, пока не вернутся его рекурсивные вызовы. Он проходит через отсортированные половины линейным способом и объединяет их, что сокращает необходимость разбивать память компьютера на страницы. В противоположность вышесказанному быстрая сортировка, перемещая элементы в разные половины массива, перепрыгивает с одного места на другое, увеличивая разбивку на страницы и очень сильно замедляя алгоритм.
4. Алгоритмы быстрее O(N log(N))
В работе уже упоминалось, что самому быстрому алгоритму, использующему сравнение, для сортировки n элементов требуется как минимум O(n log(n)) времени. Рассмотренные сортировки (пирамидальная, слиянием и быстрая) в ожидаемом случае достигают такого предела, поэтому может показаться, что тема исчерпана. Но если заострить внимание на словах «алгоритму, использующему сравнения» и воспользоваться другим методом, то указанная производительность не предел. В следующих подразделах будет рассмотрено ещё два алгоритма, где сортировка осуществляется за время, которое значительно меньше, чем O(n log(n)).
4.1 Сортировка подсчетом
Подобный метод удобно использовать в том случае, если сортировать приходится целые числа, лежащие в относительно небольшом диапазоне. Например, вам нужно упорядочить 1 млн целых чисел от 0 до 1000. Основная идея заключается в том, чтобы установить количество элементов массива с определенным значением, а затем скопировать это значение по порядку нужное количество раз обратно в массив. Реализацию такого метода показывает следующий код.
Листинг 9 – Псевдокод сортировки подсчётом
Countingsort(Integer: values[], Integer: max_value)
// Создаем массив счетчиков.
Integer: counts[0 To max_value]
// Инициализируем массив счетчиков
// (требуется не во всех языках программирования).
For i = 0 To max_value
counts[i] = 0
Next i
// Считаем количество элементов для каждого значения.