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

1. Обзор

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

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

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

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

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

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

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

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 (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.