Перейти к основному содержимому

Реализация алгоритма быстрой сортировки в Java

· 5 мин. чтения

1. Обзор

В этом руководстве мы подробно рассмотрим алгоритм QuickSort, сосредоточив внимание на его реализации на Java.

Мы также обсудим его преимущества и недостатки, а затем проанализируем его временную сложность.

2. Алгоритм быстрой сортировки

Quicksort — это алгоритм сортировки, использующий принцип «разделяй и властвуй » . Он имеет среднюю сложность O(n log n) и является одним из наиболее часто используемых алгоритмов сортировки, особенно для больших объемов данных.

Важно помнить, что быстрая сортировка не является стабильным алгоритмом. Алгоритм стабильной сортировки — это алгоритм, в котором элементы с одинаковыми значениями появляются в отсортированном выводе в том же порядке, что и во входном списке.

Входной список разделен на два подсписка с помощью элемента, называемого стержнем; один подсписок с элементами меньше, чем точка опоры, а другой - с элементами больше, чем точка опоры. Этот процесс повторяется для каждого подсписка.

Наконец, все отсортированные подсписки объединяются, чтобы сформировать окончательный результат.

2.1. Шаги алгоритма

  1. Мы выбираем элемент из списка, который называется стержнем. Мы будем использовать его, чтобы разделить список на два подсписка.
  2. Мы переупорядочиваем все элементы вокруг опорной точки — элементы с меньшим значением помещаются перед ней, а все элементы, превышающие опорную, — после нее. После этого шага стержень находится в своем конечном положении. Это важный шаг разделения.
  3. Мы применяем описанные выше шаги рекурсивно к обоим подспискам слева и справа от сводки.

Как мы видим, быстрая сортировка по своей природе является рекурсивным алгоритмом, как и любой подход «разделяй и властвуй».

Давайте возьмем простой пример, чтобы лучше понять этот алгоритм.

Arr[] = {5, 9, 4, 6, 5, 3}
  1. Предположим, мы выбрали 5 в качестве опорной точки для простоты.
  2. Сначала мы поместим все элементы меньше 5 в первую позицию массива: {3, 4, 5, 6, 5, 9}
  3. Затем мы повторим это для левого подмассива {3,4}, взяв 3 в качестве точки поворота.
  4. Нет элементов меньше 3
  5. Мы применяем быструю сортировку к подмассиву справа от опорной точки, т.е. {4}
  6. Этот подмассив состоит только из одного отсортированного элемента
  7. Мы продолжаем работать с правой частью исходного массива {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 .