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