Быстрая сортировка реализация java

Алгоритм быстрой сортировки — реализация на C++, Java и Python

Дан целочисленный массив, отсортируйте его с помощью алгоритма быстрой сортировки.

Обзор быстрой сортировки

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

Быстрая сортировка в среднем дает O(n.log(n)) сравнения для сортировки n Предметы. В худшем случае получается O(n 2 ) сравнения, хотя такое поведение встречается очень редко.

Как работает быстрая сортировка?

Быстрая сортировка — это Разделяй и властвуй алгоритм. Как и все алгоритмы «разделяй и властвуй», он сначала делит большой массив на два меньших подмассива, а затем рекурсивно сортирует подмассивы. По сути, весь процесс включает три этапа:

• Выбор опоры: Выберите элемент, называемый опорным, из массива (обычно это самый левый или самый правый элемент раздела).
• Разделение: Переупорядочите массив таким образом, чтобы все элементы со значениями меньше опорного располагались перед опорным. Напротив, все элементы со значениями больше, чем точка опоры, идут после нее. Равные значения могут идти в любом направлении. После этого разбиения стержень занимает свое конечное положение.
• Повторять: Рекурсивно примените описанные выше шаги к подмассиву элементов с меньшими значениями, чем у опорного, и отдельно к подмассиву элементов с большими значениями, чем у опорного.

Базовым случаем рекурсии являются массивы размером 1 , которые никогда не нужно сортировать. На следующей диаграмме показано, как мы выбираем крайний левый элемент в качестве опорного на каждом этапе алгоритма быстрой сортировки, разбиваем массив по опорному элементу и повторяемся в двух подмассивах, которые мы получаем после процесса разделения:

Обратите внимание, что этапы выбора опоры и разбиения могут быть выполнены несколькими способами, и выбор конкретных схем реализации существенно влияет на производительность алгоритма. Мы обсудим все это подробно позже, а сейчас давайте перейдем к части кодирования.

Ниже приведена реализация алгоритма Quicksort на C++, Java и Python:

Источник

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

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

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

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

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

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

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

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

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

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

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

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

1. Предположим, мы выбрали 5 в качестве опорной точки для простоты.
2. Сначала мы поместим все элементы меньше 5 в первую позицию массива:
3. Затем мы повторим это для левого подмассива , взяв 3 в качестве точки поворота.
4. Нет элементов меньше 3
5. Мы применяем быструю сортировку к подмассиву справа от опорной точки, т.е.
6. Этот подмассив состоит только из одного отсортированного элемента
7. Мы продолжаем работать с правой частью исходного массива , пока не получим окончательный упорядоченный массив.

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 .

Источник