9 алгоритмов сортировки на VBA
Если вы хотите начать писать макросы на VBA (да и на любом другом языке), то помимо знания самого языка программирования хорошем подспорьем в работе будет знание и умение писать алгоритмы. Как и в любом другом деле для этого потребуется практика, много практики. В этой статье мы разберем алгоритмы сортировки, знание их спрашивают практически на любом собеседование на должность программиста, да и студентов часто мучают ими. Изучите их, это хороший опыт и практика для начинающих!
О чем пойдет речь
В статье разберем 9 видов сортировок, рассмотрим суть этих алгоритмов. Скорости, сложность алгоритмов и практическое их применение оставим за скобками. Задача статьи показать, что одну и туже задачу можно решать различными способами, показать практическое применение языка VBA и помочь начинающим в его освоении.
Скачать файлик можно по кнопке выше. Поехали!
Подготовительный этап
Перед тем как начинать писать алгоритмы немного подготовимся. Создадим общую константу n для хранения размера массивов. Вставим на лист диаграмму, чтобы отслеживать как все работает. В коде объявим объект нашей диаграммы, на которой будем просматривать ход процесса сортировки. Чтобы не дублировать код в каждом алгоритме сортировки мы будем использовать процедуру инициализации Init().
Option Explicit Const n As Long = 25 Dim Chrt As ChartObject '************************************************************** ' Sub : Init ' Author : Zheltov Alexey ' Date : 24.12.2020 ' Purpose : Инициализация '************************************************************** Sub Init() Set Chrt = ActiveSheet.ChartObjects(1) End Sub
Чтобы наша диаграмма с результатом не подвисала и обновлялась напишем такую функцию.
'************************************************************** ' Sub : ChartRefresh ' Author : Zheltov Alexey ' Date : 24.12.2020 ' Purpose : Обновление диаграммы '************************************************************** Sub ChartRefresh() Chrt.Activate Application.Calculate DoEvents End Sub
В качестве массивов будем использовать диапазон ячеек A1:Y1. Напишем еще одну коротенькую процедуру для перемешивания этого массива, точнее заполнения его числами от 1 до 25 в случайном порядке.
'************************************************************** ' Sub : RandomArray ' Author : Zheltov Alexey ' Date : 24.12.2020 ' Purpose : Перемешивание массива '************************************************************** Sub RandomArray() Dim coll As New Collection Dim rndVal As Long Randomize Do While coll.count < n rndVal = CLng((n - 1) * Rnd) + 1 On Error Resume Next coll.Add rndVal, CStr(rndVal) If Err.Number = 0 Then Cells(1, coll.count) = rndVal Err.Clear Loop End Sub
Теперь все готово, давайте писать алгоритмы сортировки.
Сортировка пузырьком
Пузырьковая сортировка (или сортировка простыми обменами) пожалуй самый неэффективный алгоритм сортировки и в тоже время пожалуй самый известный.
Суть алгоритма в прохождении в цикле по всем элементами массива и в попарном сравнении текущего элемента со следующим. Если текущий элемент массива больше (для сортировки по возрастанию и меньше для сортировки по убыванию) чем следующий, то эти два элемента меняются друг с другом местами. Ход алгоритма смотрите на следующей диаграмме.
Вот код сортировки данным алгоритмом на VBA. Еще стоит обратить внимание на переменную Flag она служит индикатором того, что массив досрочно отсортирован и можно заранее выйти из цикла и сократить вычислительные ресурсы.
'************************************************************** ' Sub : BubbleSort ' Author : Zheltov Alexey ' Date : 24.12.2020 ' Purpose : Сортировка простыми обменами, сортировка пузырьком '************************************************************** Sub BubbleSort() Dim i As Long Dim j As Long Dim Flag As Boolean Init For i = 1 To n - 1 Flag = False For j = 1 To n - i If Cells(1, j) > Cells(1, j + 1) Then Swap Cells(1, j), Cells(1, j + 1): Flag = True Next If Not Flag Then Exit For Next End Sub
Далее описана процедура Swap для перестановки ячеек местами. После перестановки ячеек вызывается процедура ChartRefresh обновления диаграммы.
'************************************************************** ' Sub : Swap ' Author : Zheltov Alexey ' Date : 24.12.2020 ' Purpose : Перестановка ячеек '************************************************************** Sub Swap(A As Range, B As Range) Dim C As String C = A A = B B = C ChartRefresh End Sub
Сортировка перемешиванием
Этот алгоритм является разновидностью пузырьковой сортировки. Также этот алгоритм называют Шейкерной сортировкой или двунаправленной. Основное отличие от обычной сортировки пузырьком в том, что массив сначала просматривается слева направо и максимальный элемент перемещается вправа, а после мы проходим по массиву справа налево (от последнего отсортированного элемента) и наименьший элемент перемещается влево. Вот на графике отчетливо это видно.
Алгоритм немного больше, но по сложности аналогичный, вот его код на VBA.
Sub ShakerSort() Dim left As Long Dim right As Long Dim count As Long Dim i As Long Init left = 1 right = n count = 0 Do While left < right For i = left To right - 1 count = count + 1 If Cells(1, i) >Cells(1, i + 1) Then Swap Cells(1, i), Cells(1, i + 1) Next right = right - 1 For i = right To left + 1 Step -1 count = count + 1 If Cells(1, i - 1) > Cells(1, i) Then Swap Cells(1, i - 1), Cells(1, i) Next left = left + 1 Loop End Sub
Сортировка выбором
Тоже достаточно простой алгоритм сортировки. Суть его заключается в поиске минимального значения (максимального для сортировки по убыванию) и обмене найденного значения с первым неотсортированным значением. Т.е. нашли первое минимальное значение, поменяли его с первым элементом, нашли второе минимальное - поменяли со вторым элементом. График получается следующий:
'************************************************************** ' Sub : SelectionSort ' Author : Zheltov Alexey ' Date : 24.12.2020 ' Purpose : Сортировка выбором '************************************************************** Sub SelectionSort() Dim i As Long Dim j As Long Dim iMin As Long Init For i = 1 To n iMin = i For j = i To n If Cells(1, j) < Cells(1, iMin) Then iMin = j Next If iMin <>i Then Swap Cells(1, i), Cells(1, iMin) Next End Sub
Объединение сортировки пузырьком и сортировки выбором
Можно ускорить алгоритм сортировки пузырьком объединив его с алгоритмом сортировки выбором. Для этого нужно определять минимальный элемент во внутреннем цикле и после каждого прохода по списку обменивать найденный минимальный элемент с первым неотсортированным слева. Таким образом, мы сокращаем в 2 раза число перестановок, но при этом увеличиваем в 2 раза число сравнений.
Код отличается только 2 строчками:
'************************************************************** ' Sub : BubbleSortWhithSelection ' Author : Zheltov Alexey ' Date : 24.12.2020 ' Purpose : Объединение сортировки пузырьком и сортировки выбором '************************************************************** Sub BubbleSortWhithSelection() Dim i As Long Dim j As Long Dim iMin As Long Init For i = 1 To n - 1 iMin = i For j = i To n - i If Cells(1, j) > Cells(1, j + 1) Then Swap Cells(1, j), Cells(1, j + 1) If Cells(1, j) < Cells(1, iMin) Then iMin = j Next If iMin <>i Then Swap Cells(1, i), Cells(1, iMin) Next End Sub
Сортировка вставками
Вот определение сортировки с википедии
Это алгоритм, в котором элементы входной последовательности просматриваются по одному, и каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных элементов.
Другими словами мы во внешнем цикле проходим по всем элементам массива, а во внутреннем цикле сравниваем правый элемент с уже отсортированными элементами слева и перемещаем его при необходимости. Вот как это выглядит визуально:
Код тоже думаю окажется для вас достаточно простым.
'************************************************************** ' Sub : InsertionSort ' Author : Zheltov Alexey ' Date : 24.12.2020 ' Purpose : Сортировка вставками '************************************************************** Sub InsertionSort() Dim i As Long Dim j As Long Init For i = 2 To n j = i Do While j > 1 If Cells(1, j) > Cells(1, j - 1) Then Exit Do Swap Cells(1, j), Cells(1, j - 1) j = j - 1 Loop Next End Sub
Гномья сортировка
Визуально отличия от сортировки вставками нет, однако в код совершенно другой так как нет никаких вложенных циклов. Алгоритм в цикле проходит по всем элементам, сравнивая текущий элемент с предыдущим. Если элементы стоят верно переходит к следующему, если нет, меняет их местами и переходит к предыдущему элементу.
'************************************************************** ' Sub : GnomeSort ' Author : Zheltov Alexey ' Date : 24.12.2020 ' Purpose : Гномья сортировка '************************************************************** Sub GnomeSort() Dim i As Long Dim j As Long Init i = 2 j = 2 Do While i < n + 1 If Cells(1, i - 1) < Cells(1, i) Then i = j j = j + 1 Else Swap Cells(1, i - 1), Cells(1, i) i = i - 1 If i = 1 Then i = j j = j + 1 End If End If Loop End Sub
Сортировка слиянием
Простые алгоритмы сортировки мы разобрали, теперь давайте рассмотрим более сложные виды сортировок. Хотя главное понять суть алгоритма и его реализация уже не будет казаться сложной.
Суть алгоритма сортировки слиянием состоит в том, чтобы разбить исходный массив на более мелкие массивы, отсортировать каждый по отдельности, а после объединить результаты.
Для этого первоначальный массив разбивается на 2 части пополам (ну или почти пополам если количество нечетное), каждая половинка разбивается еще пополам и так до тех пор, пока мы не получим массивы состоящие из 1 элемента. После прохождения процедуры разбивки на части, слияние каждой части и ее сортировка. Например, массив содержит числа 5 2 1 3 4. Разбиваем его на две части: 5,2,1 и 3,4 . Первую часть 5,2,1 разбиваем еще на две части 5,2 и 1. Далее 5,2 еще на две части 5 и 2. А теперь идем обратно, сортируем и сливаем массивы. Получается 2,5 и 1, объединим дальше - 1,2,5 , последняя итерация отсортирует исходный массив 1 2 3 4 5. При слиянии учитывается тот факт, что массивы уже отсортированы по отдельности, поэтому объединение проходит быстрее.
Вот визуализация работы алгоритма:
Код состоит из двух частей. Первая MergeSort - рекурсивная функция разделения массивов, т.е. эта функция запускает саму себя. Это происходит до тех пор, пока размер массива больше 1, иначе запускается функция MergeSort для каждой из частей.
После того как массивы разобьются запускается функция Merge(left, right), которая сортирует и объединяет массив обратно.
'************************************************************** ' Function : MergeSort ' Author : Zheltov Alexey ' Date : 24.12.2020 ' Purpose : Рекурсивная функция сортировки слиянием '************************************************************** Function MergeSort(rng As Range) Dim left As Range Dim right As Range Dim result As Range Dim i As Long Dim middle As Long If rng.Cells.count = 1 Then Set MergeSort = rng Exit Function Else middle = CLng(rng.Cells.count / 2) ' Разделяем диапазон на 2 части Set left = Range(rng.Columns(1), rng.Columns(middle)) Set right = Range(rng.Columns(middle + 1), rng.Columns(rng.Columns.count)) ' Рекурсивно проходим этой же функцией по каждой части left = MergeSort(left) right = MergeSort(right) ' Объединяем части обратно в единое целое MergeSort = Merge(left, right) End If End Function
В качестве сортировки и объединения можно использовать различные алгоритмы, например такой. Если кто-то предложит более изящное решение - пишите в комментариях.
'************************************************************** ' Function : Merge ' Author : Zheltov Alexey ' Date : 24.12.2020 ' Purpose : Функция сортирует и объединяет диапазон '************************************************************** Function Merge(left As Range, right As Range) As Range Dim i As Long Dim count As Long Dim result Dim sizeLeft As Long Dim sizeRight As Long Dim FirstRng As Range Set FirstRng = left.Cells(1, 1) sizeLeft = left.count sizeRight = right.count ReDim result(1 To sizeLeft + sizeRight) i = 1 Do While sizeLeft > 0 And sizeRight > 0 If left.Columns(1) 1 Then Set left = left.Offset(, 1).Resize(, left.Columns.count - 1) sizeLeft = sizeLeft - 1 Else result(i) = right.Columns(1) If sizeRight > 1 Then Set right = right.Offset(, 1).Resize(, right.Columns.count - 1) sizeRight = sizeRight - 1 End If i = i + 1 Loop Do While sizeLeft > 0 result(i) = left.Columns(1) If sizeLeft > 1 Then Set left = left.Offset(, 1).Resize(, left.Columns.count - 1) sizeLeft = sizeLeft - 1 i = i + 1 Loop Do While sizeRight > 0 result(i) = right.Columns(1) If sizeRight > 1 Then Set right = right.Offset(, 1).Resize(, right.Columns.count - 1) sizeRight = sizeRight - 1 i = i + 1 Loop For i = 1 To UBound(result) FirstRng.Offset(, i - 1) = result(i) ChartRefresh Next Set Merge = FirstRng.Resize(, UBound(result)) End Function
Так как функция у нас рекурсивная, то первый ее запуск необходимо сделать из отдельной процедуры, вот так:
'************************************************************** ' Sub : StartMergeSort ' Author : Zheltov Alexey ' Date : 24.12.2020 ' Purpose : Запуск сортировки слиянием '************************************************************** Sub StartMergeSort() Init MergeSort Range(Cells(1, 1), Cells(1, n)) End Sub
Быстрая сортировка
Алгоритм быстрой сортировки - один из самых быстрых и эффективных и часто используется в практике. При этом он достаточно простой.
Суть алгоритма в следующем:
- Выбрать из массива опорный элемент. Например, взять элемент в середине массива (в целом это может быть любой из элементов).
- Сравнить остальные элементы массива с выбранным опорным элементов и разбить массив на 2 части:
- элементы, которые меньше или равны опорному элементу;
- элементы, которые больше опорного.
- Далее пункты 1 и 2 повторяются рекурсивно для каждой части массива, до тех пор пока размер части состоит из более чем 1 элемента.
На визуализации к сожалению что-то разглядеть сложно. Алгоритм достаточно быстро отрабатывает:
Вот код данного алгоритма на VBA.
'************************************************************** ' Sub : QuickSort ' Author : Zheltov Alexey ' Date : 24.12.2020 ' Purpose : Рекурсивная функция для быстрой сортировки '************************************************************** Sub QuickSort(rng As Range, lo, hi) Dim p As Long If lo < hi Then p = Partition(rng, lo, hi) Call QuickSort(rng, lo, p) Call QuickSort(rng, p + 1, hi) End If End Sub
'************************************************************** ' Function : Partition ' Author : Zheltov Alexey ' Date : 24.12.2020 ' Purpose : Выбор опорного элемента для быстрой сортировки '************************************************************** Function Partition(rng As Range, lo, hi) Dim i As Long Dim j As Long Dim pivot i = lo j = hi pivot = (rng.Cells(1, lo) + rng.Cells(1, hi)) / 2 Do Do While rng.Cells(1, i) < pivot i = i + 1 Loop Do While rng.Cells(1, j) >pivot j = j - 1 Loop If i >= j Then Partition = j Exit Function End If Swap rng.Cells(1, i), rng.Cells(1, j) Loop End Function
Запуск рекурсивной функции быстрой сортировки запустим из отдельного метода.
'************************************************************** ' Sub : StartQuickSort ' Author : Zheltov Alexey ' Date : 24.12.2020 ' Purpose : Запуск быстрой сортировки '************************************************************** Sub StartQuickSort() Init QuickSort Range(Cells(1, 1), Cells(1, n)), 1, n End Sub
Пирамидальная сортировка
Пирамидальная сортировка или как еще ее называют "Сортировка кучей" использует в своем алгоритме двоичное дерево.
Это такое дерево, для которого выполнены следующие условия:
- Значение в любой вершине не меньше, чем значения её потомков.
- Длина веток дерева не отличается друг от друга более чем на 1 слой.
- Последний слой заполняется слева направо без «дырок».
Вот пример дерева, которое можно найти на википедии:
Это дерево можно представить в виде следующего массива, где для любого элемента A[i] потомками являются элементы A[2i] и A[2i+1].
Т.е. для каждого элемента кучи справедливы следующие условия: A[i] >= A[2i] и A[i] >= A[2i+1].
Алгоритм пирамидальной сортировки состоит из следующих шагов:
- Построение массива в виде двоичного дерева.
- Исключение корня дерева (максимального значения массива) из массива и перенос его в конец последовательности.
- После исключения корня дерево перестраивается и его корень опять отсекается и переносится в конец.
- Так происходит до тех пор, пока вся последовательность не отсортируется.
Вот визуальное отображение выполнения этого алгоритма:
Ниже код пирамидальной сортировки на VBA. Который формирует двоичную кучу и корень этой кучи переносит в конец последовательности. Так происходит n раз.
'************************************************************** ' Sub : HeapSort ' Author : Zheltov Alexey ' Date : 24.12.2020 ' Purpose : Пирамидальная сортировка '************************************************************** Sub HeapSort() Dim i As Long Dim j As Long Init For i = 1 To n For j = CInt((n + 1) / 2) - CInt(i / 2) To 1 Step -1 If 2 * j + 1 Cells(1, 2 * j + 1) Then If Cells(1, j) < Cells(1, 2 * j) Then Swap Cells(1, j), Cells(1, 2 * j) End If Else If Cells(1, j) < Cells(1, 2 * j + 1) Then Swap Cells(1, j), Cells(1, 2 * j + 1) End If End If Else If 2 * jБыстрая сортировка
Всем привет. Сегодня продолжаем серию статей, которые я написал специально к запуску курса «Алгоритмы и структуры данных» от OTUS. По ссылке вы сможете подробно узнать о курсе, а также бесплатно посмотреть запись Demo-урока по теме: «Три алгоритма поиска шаблона в тексте».
Введение
Сортировка массива является одной из первых серьезных задач, изучаемых в классическом курсе «Алгоритмы и структуры данных» дисциплины computer science. В связи с этим задачи на написание сортировок и соответствующие вопросы часто встречаются на собеседованиях на позиции стажера или junior разработчика.
Постановка задачи
Традиционно стоит начать изложение решений задачи с ее постановки. Обычно задача сортировки предполагает упорядочивание некоторого массива целых чисел по возрастанию. Но на самом деле, это является некоторым упрощением. Излагаемые в этом разделе алгоритмы можно применять для упорядочивания массива любых объектов, между которыми установлено отношение порядка (то есть про любые два элемента можно сказать: первый больше второго, второй больше первого или они равны). Упорядочивать можно как по возрастанию, так и по убыванию. Мы же воспользуемся стандартным упрощением.
Быстрая сортировка
В прошлый раз мы поговорили о чуть более сложной сортировке — сортировке вставками. Сегодня речь пойдет о существенно более сложном алгоритме — быстрой сортировке (еще ее называют сортировкой Хоара).
Описание алгоритма
Алгоритм быстрой сортировки является рекурсивным, поэтому для простоты процедура на вход будет принимать границы участка массива от l включительно и до r не включительно. Понятно, что для того, чтобы отсортировать весь массив, в качестве параметра l надо передать 0, а в качестве r — n, где по традиции n обозначает длину массива.
В основе алгоритма быстрой сортировке лежит процедура partition. Partition выбирает некоторый элемент массива и переставляет элементы участка массива таким образом, чтобы массив разбился на 2 части: левая часть содержит элементы, которые меньше этого элемента, а правая часть содержит элементы, которые больше или равны этого элемента. Такой разделяющий элемент называется пивотом.
partition(l, r): pivot = a[random(l . r - 1)] m = l for i = l . r - 1: if a[i] < pivot: swap(a[i], a[m]) m++ return mПивот в нашем случае выбирается случайным образом. Такой алгоритм называется рандомизированным. На самом деле пивот можно выбирать самым разным образом: либо брать случайный элемент, либо брать первый / последний элемент учаcтка, либо выбирать его каким-то «умным» образом. Выбор пивота является очень важным для итоговой сложности алгоритма сортировки, но об этом несколько позже. Сложность же процедуры partition — O(n), где n = r — l — длина участка.
Теперь используем partition для реализации сортировки:
sort(l, r): if r - l = 1: return m = partition(l, r) sort(l, m) sort(m, r)Крайний случай — массив из одного элемента обладает свойством упорядоченности. Если массив длинный, то применяем partition и вызываем процедуру рекурсивно для двух половин массива.
Если прогнать написанную сортировку на примере массива 1 2 2, то можно заметить, что она никогда не закончится. Почему так получилось?
При написании partition мы сделали допущение — все элементы массива должны быть уникальны. В противном случае возвращаемое значение m будет равно l и рекурсия никогда не закончится, потому как sort(l, m) будет вызывать sort(l, l) и sort(l, m). Для решения данной проблемы надо массив разделять не на 2 части (< pivot и >= pivot), а на 3 части ( < pivot, = pivot, >pivot) и вызывать рекурсивно сортировку для 1-ой и 3-ей частей.
Анализ
Предлагаю проанализировать данный алгоритм.
Временная сложность алгоритма выражается через нее же по формуле: T(n) = n + T(a * n) + T((1 — a) * n). Таким образом, когда мы вызываем сортировку массива из n элементов, тратится порядка n операций на выполнение partition'а и на выполнения себя же 2 раза с параметрами a * n и (1 — a) * n, потому что пивот разделил элемент на доли.
В лучшем случае a = 1 / 2, то есть пивот каждый раз делит участок на две равные части. В таком случае: T(n) = n + 2 * T(n / 2) = n + 2 * (n / 2 + 2 * T(n / 4)) = n + n + 4 * T(n / 4) = n + n + 4 * (n / 4 + 2 * T(n / 8)) = n + n + n + 8 * T(n / 8) =…. Итого будет log(n) слагаемых, потому как слагаемые появляются до тех пор, пока аргумент не уменьшится до 1. В результате T(n) = O(n * log(n)).
В худшем случае a = 1 / n, то есть пивот отсекает ровно один элемент. В первой части массива находится 1 элемент, а во второй n — 1. То есть: T(n) =n + T(1) + T(n — 1) = n + O(1) + T(n — 1) = n + O(1) + (n — 1 + O(1) + T(n — 2)) = O(n^2). Квадрат возникает из-за того, что он фигурирует в формуле суммы арифметической прогрессии, которая появляется в процессе расписывания формулы.
В среднем в идеале надо считать математическое ожидание различных вариантов. Можно показать, что если пивот делит массив в отношении 1:9, то итоговая асимптотика будет все равно O(n * log(n)).
Сортировка называется быстрой, потому что константа, которая скрывается под знаком O на практике оказывается достаточно небольшой, что привело к широкому распространению алгоритма на практике.
Читать ещё
- Сортировка вставками
- Удаление узлов из красно-чёрного дерева
Как вы думаете может ли метод быстрой сортировки работать дольше чем метод выбора
На этом шаге рассмотрим определение "худшего" и "среднего" случаев выбора опорного элемента быстрой сортировки.
Допустим, у вас имеется простая функция для вывода каждого элемента в списке:
Архив с примером на языке Python можно взять здесь.
Эта функция последовательно перебирает все элементы списка и выводит их. Так как функция перебирает весь список, она выполняется за время О(n) . Теперь предположим, что вы изменили эту функцию и она делает секундную паузу перед выводом:
Архив с примером на языке Python можно взять здесь.
Перед выводом элемента функция делает паузу продолжительностью в 4 секунды. Предположим, вы выводите список из пяти элементов с использованием обеих функций:
Обе функции проходят по списку один раз, и обе выполняются за время О(n) . Как вы думаете, какая из них работает быстрее? Конечно та, которая не делает паузу перед выводом каждого элемента. Следовательно, даже при том, что обе функции имеют одинаковую скорость "О-большое" , реально первая функция работает быстрее. Когда вы используете "О-большое" , в действительности это означает следующее:
Здесь с - некоторый фиксированный промежуток времени для вашего алгоритма. Он называется константой. Например, время выполнения может составлять 10 миллисекунд * n для print_items против 1 секунды * n для print_i tems2.
Обычно константа игнорируется, потому что если два алгоритма имеют разное время "О-большое" , она роли не играет. Для примера возьмем бинарный и простой поиск. Допустим, такие константы присутствуют в обоих алгоритмах.
Теперь предположим, что поиск ведется по списку из 4 миллиардов элементов. Время будет таким:
Как видите, бинарный поиск все равно работает намного быстрее. Константа ни на что не повлияла.
Однако в некоторых случаях константа может иметь значение. Один из примеров такого рода - быстрая сортировка и сортировка слиянием. У быстрой сортировки константа меньше, чем у сортировки слиянием, поэтому, несмотря на то, что оба алгоритма характеризуются временем О(n log n) , быстрая сортировка работает быстрее. А на практике быстрая сортировка работает быстрее, потому что средний случай встречается намного чаще худшего.
Определим как выглядит средний случай по сравнению с худшим?
Быстродействие быстрой сортировки сильно зависит от выбора опорного элемента. Предположим, опорным всегда выбирается первый элемент, а быстрая сортировка применяется к уже отсортированному массиву. Быстрая сортировка не проверяет, отсортирован входной массив или нет, и все равно пытается его отсортировать.
Обратите внимание: на этот раз массив не разделяется на две половины. Вместо этого один из двух подмассивов всегда пуст, так что стек вызовов получается очень длинным. Теперь предположим, что в качестве опорного всегда выбирается средний элемент. Посмотрим, как выглядит стек вызовов в этом случае.
Массив каждый раз делится надвое, поэтому такое количество рекурсивных вызовов излишне. Вы быстрее добираетесь до базового случая, и стек вызовов получается более коротким.
Первый из рассмотренных примеров описывает худший сценарий, а второй - лучший. В худшем случае размер стека описывается как О(n). В лучшем случае он составит O(log n) .
Теперь рассмотрим первый уровень стека. Один элемент выбирается опорным, а остальные элементы делятся на подмассивы. Вы перебираете все восемь элементов массива, поэтому первая операция выполняется за время О(n). На этом уровне стека вызовов вы обратились ко всем восьми элементам. Но на самом деле вы обращаетесь к О(n) элементам на каждом уровне стека вызовов.
Даже если массив будет разделен другим способом, вы все равно каждый раз обращаетесь к О(n) элементам.
Итак, завершение каждого уровня требует времени О(n).
В этом примере существуют O(log n) уровней. А так как каждый уровень занимает время О(n) , то весь алгоритм займет время О(n) * O(log n) = О(n log n) . Это сценарий лучшего случая. В худшем случае существуют О(n) уровней, поэтому алгоритм займет время О(n)* О(n) = О(n 2 ) .
На следующем шаге рассмотрим хеш-таблицы.
Сортировка в Java
Прочел в документации и нигде не нашел объяснения (гуглил без результата), почему для реализации сортировки выбран метод слияния (пишут модифицированный, а что именно модифицировано ?), а не Qsort ? Только из-за устойчивости алгоритма слияния или какие-то особенности работы с памятью в реализации JVM обуславливают этот выбор ? Ведь Qsort требует значительно меньше дополнительной памяти да и по скорости (при разумной реализации) почти всегда превосходит (если верить Кнуту) MergeSort. Какие есть соображения на эту тему ? UPD Ответов больше нет, обсуждение закончено. Всем огромное спасибо. Просмотр материалов по MergeSort в Wiki навел меня на мысль попробовать реализовать ее (невзирая на предупреждение в Вики о большой сложности алгоритма) без выделения дополнительной памяти размером O(n). yozh, одна реализация (или минимум реализаций) это мне тоже приходило в голову. Хотелось бы узнать, так ли это на самом деле. Nikolay Artamonov, а какие еще устойчивые сложностью n*log(n) есть ? Я сходу не припоминаю. Тогда уж еще один вопрос, почему не дали выбирать из нескольких (устойчивая/неустойчивая) ? Я имею в виду наличие нескольких алгоритмов в стандартных пакетах. Возможно, что бы путаницы меньше было. И так в Java огромное количество классов-методов. 1) Спасибо за ссылку, буду смотреть (это к комментарию с ссылкой на http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms) 2) Нашел там интересный линк на реализацию в jdk7 - http://hg.openjdk.java.net/jdk7/tl/jdk/rev/bfd7abda8f79 Обещают замечательные характеристики (по дополнительной памяти max n/2 !) и вообще интересно.
Отслеживать
34.4k 15 15 золотых знаков 65 65 серебряных знаков 94 94 бронзовых знака
задан 16 сен 2011 в 22:16
45.8k 6 6 золотых знаков 46 46 серебряных знаков 115 115 бронзовых знаков
6 ответов 6
Сортировка: Сброс на вариант по умолчанию
В стандартной библиотеке Java существует три группы перегруженных методов для сортировки:
- java.util.Arrays.sort(prim[], . ) — для сортировки массивов примитивов prim ( int , byte , char , и т.д.). Использует алгоритм быстрой сортировки (quick sort).
- java.util.Arrays.sort(T[], . ) и java.util.Arrays.sort(Object[], . ) — для сортировки массивов комплексных объектов произвольного типа T или Object . Использует алгоритм сортировки слиянием (merge sort).
- java.util.Collections.sort() — для сортировки коллекций. Использует алгоритм сортировки слиянием (merge sort).
Причина, по которой для сортировки коллекций и массивов комплексных объектов выбран алгоритм сортировки слиянием, заключается в том, что данный алгоритм является устойчивой сортировкой, в отличие от быстрой сортировки, являющейся неустойчивой. Устойчивой сортировкой называется такой алгоритм, который сохраняет порядок следования элементов с одинаковыми ключами сортировки. К примеру, пусть нам требуется отсортировать следующие пары чисел по первому числу пары:
(4, 2) (3, 7) (3, 1) (5, 6) Тогда на выходе, в зависимости от использованного алгоритма сортировки, мы можем получить два различных результата:
(3, 7) (3, 1) (4, 2) (5, 6) (порядок сохранен) (3, 1) (3, 7) (4, 2) (5, 6) (порядок изменен) В первом случае пары (3, 7) и (3, 1) с равными ключами сортировки остались в том же порядке следования, как и изначально. Во втором случае они поменялись местами.
Почему важна устойчивая сортировка? Она позволяет производить цепочку последовательных сортировок, добиваясь сортировки в группах и подгруппах коллекции. Покажем, что это означает, на примере (примеры записаны на языке Scala для минимизации избыточного кода, присущего Java, но смысл будет ясен). Пусть мы имеем структуру данных для представления музыкальных записей:
// `albumName` - имя музыкального альбома; // `trackNumber` - номер трека в альбоме. case class Record(albumName: String, trackNumber: Int) Разместим в списке несколько музыкальных произведений (из дискографии группы Metallica) в произвольном порядке:
val records = List(Record("Master of Puppets", 7), Record("Load", 4), Record("Load", 2), Record("Reload", 5), Record("Load", 3), Record("Reload", 3)) Теперь отсортируем записи по номеру трека:
scala> val byTrackNumber = records.sortBy(_.trackNumber) byTrackNumber: List[Record] = List(Record(Load,2), Record(Load,3), Record(Reload,3), Record(Load,4), Record(Reload,5), Record(Master of Puppets,7)) А затем отсортируем еще раз, но уже по имени альбома:
scala> byTrackNumber.sortBy(_.albumName) res4: List[Record] = List(Record(Load,2), Record(Load,3), Record(Load,4), Record(Master of Puppets,7), Record(Reload,3), Record(Reload,5)) Что мы получили? Мы получили список записей, отсортированный по имени альбома, а в каждом альбоме отсортированный по номеру трека! Для этого мы сначала применили сортировку по менее значимому ключу (номер трека), которая сортирует для нас записи в подгруппах (альбомах). Затем сортировку по более значимому ключу - имени альбома. Такая последовательность важна. Следует заметить, что этот результат можно было бы получить, если сразу отсортировать записи по альбому И номеру трека за один раз, но существуют ситуации, когда нам неизвестны заранее все ключи, по которым мы будем сортировать коллекцию. К примеру, пользователь программы может выбрать в графическом интерфейсе сначала сортировку по полю "номер трека", а только затем по полю "альбом".
В случае, если бы мы применили нестабильную сортировку, вышеуказанный результат не гарантирован. Почему тогда для сортировки примитивов используется быстрая сортировка, являющаяся неустойчивой? Потому что равные примитивы (числа, символы) неотличимы друг от друга при перестановке, в отличие от комплексных объектов. Иными словами, примитивы можно сортировать только по одному ключу (их значениям). Поэтому для них допустимо применить более быстрый алгоритм, коим и является быстрая сортировка.