1. Обзор
В этом руководстве мы подробно рассмотрим алгоритм QuickSort, сосредоточив внимание на его реализации на Java.
Мы также обсудим его преимущества и недостатки, а затем проанализируем его временную сложность.
2. Алгоритм быстрой сортировки
Quicksort — это алгоритм сортировки, использующий принцип «разделяй и властвуй » . Он имеет среднюю сложность O(n log n) и является одним из наиболее часто используемых алгоритмов сортировки, особенно для больших объемов данных.
Важно помнить, что быстрая сортировка не является стабильным алгоритмом. Алгоритм стабильной сортировки — это алгоритм, в котором элементы с одинаковыми значениями появляются в отсортированном выводе в том же порядке, что и во входном списке.
Входной список разделен на два подсписка с помощью элемента, называемого стержнем; один подсписок с элементами меньше, чем точка опоры, а другой - с элементами больше, чем точка опоры. Этот процесс повторяется для каждого подсписка.
Наконец, все отсортированные подсписки объединяются, чтобы сформировать окончательный результат.
2.1. Шаги алгоритма
- Мы выбираем элемент из списка, который называется стержнем. Мы будем использовать его, чтобы разделить список на два подсписка.
- Мы переупорядочиваем все элементы вокруг опорной точки — элементы с меньшим значением помещаются перед ней, а все элементы, превышающие опорную, — после нее. После этого шага стержень находится в своем конечном положении. Это важный шаг разделения.
- Мы применяем описанные выше шаги рекурсивно к обоим подспискам слева и справа от сводки.
Как мы видим, быстрая сортировка по своей природе является рекурсивным алгоритмом, как и любой подход «разделяй и властвуй».
Давайте возьмем простой пример, чтобы лучше понять этот алгоритм.
Arr[] = {5, 9, 4, 6, 5, 3}
- Предположим, мы выбрали 5 в качестве опорной точки для простоты.
- Сначала мы поместим все элементы меньше 5 в первую позицию массива: {3, 4, 5, 6, 5, 9}
- Затем мы повторим это для левого подмассива {3,4}, взяв 3 в качестве точки поворота.
- Нет элементов меньше 3
- Мы применяем быструю сортировку к подмассиву справа от опорной точки, т.е. {4}
- Этот подмассив состоит только из одного отсортированного элемента
- Мы продолжаем работать с правой частью исходного массива {6, 5, 9}, пока не получим окончательный упорядоченный массив.
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(n 2 ) .
В среднем QuickSort имеет сложность O(n log n) , что делает его подходящим для больших объемов данных.
4.2. Быстрая сортировка против сортировки слиянием
Давайте обсудим, в каких случаях мы должны выбрать QuickSort вместо MergeSort.
Хотя и быстрая сортировка, и сортировка слиянием имеют среднюю временную сложность O(n log n) , быстрая сортировка является предпочтительным алгоритмом, поскольку имеет пространственную сложность O(log(n)) . С другой стороны, сортировка слиянием требует O(n) дополнительной памяти, что делает ее довольно дорогой для массивов. ``
Быстрая сортировка требует доступа к различным индексам для своих операций, но такой доступ невозможен напрямую в связанных списках, поскольку непрерывных блоков нет; поэтому, чтобы получить доступ к элементу, мы должны перебирать каждый узел с начала связанного списка. Кроме того, Mergesort реализован без дополнительного места для LinkedLists.
В таком случае обычно предпочтительнее увеличение накладных расходов для быстрой сортировки и сортировки слиянием.
5. Вывод
Quicksort — это элегантный алгоритм сортировки, очень полезный в большинстве случаев.
Как правило, это алгоритм «на месте» со средней временной сложностью O (n log n).
Еще один интересный момент, о котором следует упомянуть, заключается в том, что метод Java Arrays.sort() использует Quicksort для сортировки массивов примитивов. Реализация использует два пивота и работает намного лучше, чем наше простое решение, поэтому для производственного кода обычно лучше использовать библиотечные методы.
Как всегда, код для реализации этого алгоритма можно найти в нашем репозитории GitHub .