«1. Обзор
В этом руководстве мы подробно рассмотрим алгоритм QuickSort, сосредоточив внимание на его реализации на языке Java.
Мы также обсудим его преимущества и недостатки, а затем проанализируем его временную сложность.
2. Алгоритм быстрой сортировки
Быстрая сортировка — это алгоритм сортировки, использующий принцип «разделяй и властвуй». Он имеет среднюю сложность O(n log n) и является одним из наиболее часто используемых алгоритмов сортировки, особенно для больших объемов данных.
Важно помнить, что быстрая сортировка не является стабильным алгоритмом. Алгоритм стабильной сортировки — это алгоритм, в котором элементы с одинаковыми значениями появляются в отсортированном выводе в том же порядке, что и во входном списке.
Входной список разделен на два подсписка с помощью элемента, называемого pivot; один подсписок с элементами меньше, чем точка опоры, а другой — с элементами больше, чем точка опоры. Этот процесс повторяется для каждого подсписка.
Наконец, все отсортированные подсписки объединяются, чтобы сформировать окончательный результат.
2.1. Шаги алгоритма
- We choose an element from the list, called the pivot. We’ll use it to divide the list into two sub-lists.
- We reorder all the elements around the pivot – the ones with smaller value are placed before it, and all the elements greater than the pivot after it. After this step, the pivot is in its final position. This is the important partition step.
- We apply the above steps recursively to both sub-lists on the left and right of the pivot.
Как мы видим, быстрая сортировка по своей природе является рекурсивным алгоритмом, как и любой подход «разделяй и властвуй».
Давайте рассмотрим простой пример, чтобы лучше понять этот алгоритм.
Arr[] = {5, 9, 4, 6, 5, 3}- Let’s suppose we pick 5 as the pivot for simplicity
- We’ll first put all elements less than 5 in the first position of the array: {3, 4, 5, 6, 5, 9}
- We’ll then repeat it for the left sub-array {3,4}, taking 3 as the pivot
- There are no elements less than 3
- We apply quicksort on the sub-array in the right of the pivot, i.e. {4}
- This sub-array consists of only one sorted element
- We continue with the right part of the original array, {6, 5, 9} until we get the final ordered array
2.2. Выбор оптимальной опорной точки
Важным моментом в QuickSort является выбор наилучшей опорной точки. Средний элемент, конечно, лучший, так как он разделил бы список на два равных подсписка.
Но нахождение среднего элемента в неупорядоченном списке сложно и занимает много времени, поэтому мы берем в качестве точки опоры первый элемент, последний элемент, медиану или любой другой случайный элемент.
3. Реализация на Java
Первый метод quickSort() принимает в качестве параметров массив для сортировки, первый и последний индекс. Сначала мы проверяем индексы и продолжаем, только если есть еще элементы для сортировки.
Получаем индекс отсортированного свода и используем его для рекурсивного вызова метода partition() с теми же параметрами, что и у метода quickSort(), но с другими индексами:
public void quickSort(int arr[], int begin, int end) {
if (begin < end) {
int partitionIndex = partition(arr, begin, end);
quickSort(arr, begin, partitionIndex-1);
quickSort(arr, partitionIndex+1, end);
}
}Продолжим с partition() метод. Для простоты эта функция принимает последний элемент в качестве опорного. Затем проверяет каждый элемент и меняет его местами перед поворотом, если его значение меньше.
К концу разбиения все элементы, меньшие опорной точки, находятся слева от нее, а все элементы, превышающие опорную, находятся справа от нее. Сводная точка находится в своей конечной отсортированной позиции, и функция возвращает эту позицию:
private int partition(int arr[], int begin, int end) {
int pivot = arr[end];
int i = (begin-1);
for (int j = begin; j < end; j++) {
if (arr[j] <= pivot) {
i++;
int swapTemp = arr[i];
arr[i] = arr[j];
arr[j] = swapTemp;
}
}
int swapTemp = arr[i+1];
arr[i+1] = arr[end];
arr[end] = swapTemp;
return i+1;
}4. Анализ алгоритма
4.1. Временная сложность
В лучшем случае алгоритм разделит список на два подсписка одинакового размера. Итак, первая итерация полного списка размером n требует O (n). Сортировка оставшихся двух подсписков с n/2 элементами занимает 2*O(n/2) каждый. В результате алгоритм QuickSort имеет сложность O(n log n).
В худшем случае алгоритм будет выбирать только один элемент на каждой итерации, поэтому O(n) + O(n-1) + … + O(1), что равно O(n2).
В среднем QuickSort имеет сложность O(n log n), что делает его подходящим для больших объемов данных.
4.2. Быстрая сортировка против сортировки слиянием
Давайте обсудим, в каких случаях следует выбирать быструю сортировку, а не сортировку слиянием.
Хотя и быстрая сортировка, и сортировка слиянием имеют среднюю временную сложность O(n log n), быстрая сортировка является предпочтительным алгоритмом, так как имеет пространственную сложность O(log(n)). С другой стороны, сортировка слиянием требует O(n) дополнительной памяти, что делает ее довольно дорогой для массивов.
Быстрая сортировка требует доступа к различным индексам для своих операций, но такой доступ невозможен напрямую в связанных списках, так как нет непрерывных блоков; поэтому, чтобы получить доступ к элементу, мы должны перебирать каждый узел с начала связанного списка. Кроме того, Mergesort реализован без дополнительного места для LinkedLists.
В таком случае обычно предпочтительнее увеличение накладных расходов для быстрой сортировки и сортировки слиянием.
5. Заключение
Quicksort — элегантный алгоритм сортировки, очень полезный в большинстве случаев.
«Как правило, это алгоритм «на месте» со средней временной сложностью O (n log n).
Еще один интересный момент, о котором стоит упомянуть, это то, что метод Java Arrays.sort() использует Quicksort для сортировки массивов примитивов. Реализация использует два пивота и работает намного лучше, чем наше простое решение, поэтому для производственного кода обычно лучше использовать библиотечные методы.
Как всегда, код для реализации этого алгоритма можно найти в нашем репозитории GitHub.