Быстрая сортировка — это широко используемый алгоритм сортировки, который выбирает определенный элемент, называемый «pivot», по-русски, стержнем, и разбивает массив или список для сортировки на две части на основе опорного значения s0 так, что элементы, которые меньше опорного, находятся слева от списка, а элементы больше, справа от списка.
Таким образом, список разбит на два подсписка. Подсписки могут быть необязательными для одного и того же размера. Затем быстрая сортировка «Quicksort» рекурсивно вызывает себя для сортировки этих двух подсписков.
Быстрая сортировка работает эффективно и быстро даже для больших массивов или списков.
В этой статье мы расскажем о работе быстрой сортировки вместе с некоторыми примерами программирования алгоритма quicksort.
В качестве опорного значения мы можем выбрать либо первое, последнее, либо среднее значение, либо любое случайное значение. Общая идея заключается в том, что в конечном итоге значение помещается в нужное место в массиве путем перемещения других элементов массива влево или вправо.
Общий алгоритм
Общий алгоритм быстрой сортировки приведен ниже:
1 2 3 4 5 6 7 8 9 10 11 |
quicksort(A, low, high) begin Declare array A[N] to be sorted low = 1st element; high = last element; pivot if(low < high) begin pivot = partition (A,low,high); quicksort(A,low,pivot-1) quicksort(A,pivot+1,high) End end |
Давайте теперь посмотрим на псевдокод демонстрирующий технику быстрой сортировки:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
//псевдокод для основного алгоритма быстрой сортировки procedure quickSort(arr[], low, high) arr = list to be sorted low – first element of array high – last element of array begin if (low < high) { // pivot – сводный элемент, вокруг которого будет разбит массив pivot = partition(arr, low, high); quickSort(arr, low, pivot - 1); // вызов quicksort рекурсивно, чтобы отсортировать вложенный массив перед pivot quickSort(arr, pivot + 1, high); // вызов quicksort рекурсивно для сортировки вложенного массива после pivot } end procedure //процедура разбиения выбирает последний элемент в качестве стержня. //Затем помещает значение в правильное место в //массиве таким образом, чтобы все элементы ниже pivot находились в первой половине массива, а //элементы выше pivot находились в верхней части массива. procedure partition (arr[], low, high) begin // pivot (элемент, который должен быть размещен в правильном месте) pivot = arr[high]; i = (low - 1) // Index of smaller element for j = low to high { if (arr[j] <= pivot) { i++; // индекс приращения меньшего элемента swap arr[i] and arr[j] } } swap arr[i + 1] and arr[high]) return (i + 1) end procedure |
Работа алгоритма разбиения описана ниже на примере:
Исходя из схемы, мы берем последний элемент в качестве точки опоры. Видно, что массив последовательно делится вокруг опорного элемента, пока в массиве не останется один элемент.
Далее, мы продемонстрируем работу быстрой сортировки на другой схеме ниже для лучшего понимания данной концепции.
Демонстрация работы
Давайте посмотрим на работу алгоритма быстрой сортировки. Рассмотрим следующий массив с последним элементом в качестве опорного. Кроме того, первый элемент помечен как низкий, а последний элемент — как высокий.
На схеме видно, что мы перемещаем указатели вверх и вниз на обоих концах массива. Всякий раз, когда low указывает на элемент, больший, чем точка опоры, а high указывает на элемент, меньший, чем точка опоры, мы меняем местами эти элементы и перемещаем нижний и верхний указатели в соответствующих направлениях.
Это делается до тех пор, пока нижний и верхний указатели не пересекутся. Как только они пересекаются, поворотный элемент помещается в нужное место, и массив разбивается на две части. Затем оба этих подмассива сортируются независимо друг от друга, с помощью быстрой рекурсивной сортировки.
Ниже приведена реализация алгоритма Quicksort на C++:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
#include <iostream> using namespace std; // Поменять местами два элемента - Служебная функция void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; } // разделение массива, используя последний элемент в качестве сводного int partition (int arr[], int low, int high) { int pivot = arr[high]; // стержень int i = (low - 1); for (int j = low; j <= high- 1; j++) { //если текущий элемент меньше, чем pivot, увеличить нижний элемент //поменяйте местами элементы в точках i и j if (arr[j] <= pivot) { i++; // индекс приращения меньшего элемента swap(&arr[i], &arr[j]); } } swap(&arr[i + 1], &arr[high]); return (i + 1); } //алгоритм быстрой сортировки void quickSort(int arr[], int low, int high) { if (low < high) { //разделить массив int pivot = partition(arr, low, high); //сортировка вложенных массивов независимо друг от друга quickSort(arr, low, pivot - 1); quickSort(arr, pivot + 1, high); } } void displayArray(int arr[], int size) { int i; for (i=0; i < size; i++) cout<<arr[i]<<"\t"; } int main() { int arr[] = {12,23,3,43,51,35,19,45}; int n = sizeof(arr)/sizeof(arr[0]); cout<<"Input array"<<endl; displayArray(arr,n); cout<<endl; quickSort(arr, 0, n-1); cout<<"Array sorted with quick sort"<<endl; displayArray(arr,n); return 0; } |
Вывод данных:
Входной массив 12 23 3 43 51 35 19 45 Массив, отсортированный с помощью быстрой сортировки 3 12 19 23 35 43 45 51 |
Здесь есть несколько подпрограмм, которые используются для разделения массива и рекурсивного вызова быстрой сортировки для сортировки раздела, базовой функции быстрой сортировки и служебных функций для отображения содержимого массива и соответствующего переключения двух элементов.
Сначала мы вызываем функцию быстрой сортировки с входным массивом. Внутри функции быстрой сортировки вызываем функцию разделения. В функции распределения используем последний элемент в качестве опорного элемента для массива. После определения точки поворота массив разбивается на две части, а затем вызывается функция быстрой сортировки для независимой сортировки обоих подмассивов.
Когда функция быстрой сортировки возвращает значение, массив сортируется таким образом, чтобы опорный элемент находился в нужном месте, а элементы, меньшие опорного значения, находились слева от опорного элемента, а элементы, превышающие опорный элемент, находились справа от опорного элемента.
Далее мы реализуем алгоритм быстрой сортировки на Java:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
// Реализация быстрой сортировки в Java class QuickSort { //разделение массива с последним элементом в качестве сводного элемента int partition(int arr[], int low, int high) { int pivot = arr[high]; int i = (low-1); // индекс меньшего элемента for (int j=low; j<high; j++) { // Если текущий элемент меньше или // равно pivot, затем элементы меняются местами if (arr[j] <= pivot) { i++; int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } // поменять местами arr[i+1] и arr[high] (или pivot) int temp = arr[i+1]; arr[i+1] = arr[high]; arr[high] = temp; return i+1; } //функция быстрой сортировки void quick_sort(int arr[], int low, int high) { if (low < high) { //разбивка массива на разделы вокруг pivot int pivot = partition(arr, low, high); //вызов quick_sort рекурсивно для сортировки вложенных массивов quick_sort(arr, low, pivot-1); quick_sort(arr, pivot+1, high); } } //отображение содержимого массива static void displayArray(int arr[]) { int n = arr.length; for (int i=0; i<n; ++i) System.out.print(arr[i]+" "); System.out.println(); } } class Main{ public static void main(String args[]) { int arr[] = {12,23,3,43,51,35,19,45}; int n = arr.length; QuickSort obj = new QuickSort(); System.out.println("Input array"); obj.displayArray(arr); obj.quick_sort(arr, 0, n-1); System.out.println("Array after sorting with quick sort"); obj.displayArray(arr); } } |
Вывод данных:
Входной массив 12 23 3 43 51 35 19 45 Массив после сортировки с помощью быстрой сортировки 3 12 19 23 35 43 45 51 |
В реализации на Java мы также использовали ту же логику, что и в реализации на C++. Мы использовали последний элемент в массиве в качестве опорного элемента, и в массиве выполнили быструю сортировку, чтобы поместить опорный элемент в правильное положение.
Анализ сложности алгоритма быстрой сортировки
Время, необходимое быстрой сортировке для сортировки массива, зависит от входного массива и стратегии или метода разделения.
Если k — количество элементов меньше, чем опорное, а n — общее количество элементов, то общее время, затрачиваемое на быструю сортировку, можно выразить следующим образом:
Т (n) = T (k) + T (nk-1) + O (n)
Здесь T(k) и T(nk-1) — время, затраченное на рекурсивные вызовы, а O(n) — время, затраченное на вызов с разбиением.
Давайте подробно проанализируем эту временную сложность для быстрой сортировки.
1) Наихудший случай. Наихудший случай в технике быстрой сортировки возникает в основном, когда мы выбираем самый низкий или самый высокий элемент в массиве в качестве точки опоры. (На приведенной выше схеме мы выбрали самый высокий элемент в качестве опорного). В такой ситуации возникает наихудший случай, когда сортируемый массив уже отсортирован по возрастанию или по убыванию.
Следовательно, приведенное выше выражение для общего затраченного времени изменяется следующим образом:
T(n) = T(0) + T(n-1) + O(n) , что разрешается в O(n 2 )
2) Наилучший случай. Наилучший случай для быстрой сортировки всегда происходит, когда выбранный элемент поворота находится в середине массива.
Таким образом, повторение в наилучшем случае:
T(n) = 2T(n/2) + O(n) = O(nlogn)
3) Средний случай. Чтобы проанализировать средний случай для быстрой сортировки, мы должны рассмотреть все перестановки массива, а затем рассчитать время, затрачиваемое на каждую из этих перестановок. Короче говоря, среднее время быстрой сортировки также становится O(nlogn).
Ниже приведены различные сложности техники быстрой сортировки:
Временная сложность в худшем случае | O(n 2) |
Временная сложность в лучшем случае | O(n*log n) |
Средняя временная сложность | O(n*log n) |
Пространственная сложность | O(n*log n) |
Мы можем реализовать быструю сортировку разными способами, просто изменив выбор опорного элемента (средний, первый или последний), однако для быстрой сортировки редко случается наихудший случай.
Трехсторонняя быстрая сортировка
В оригинальном методе быстрой сортировки мы обычно выбираем опорный элемент, а затем делим массив на подмассивы вокруг этого опорного элемента, так что один подмассив состоит из элементов, меньших, чем опорный, а другой состоит из элементов, превышающих опорный.
Но что, если мы выберем опорный элемент, а в массиве находится более одного элемента, равного опорному элементу?
Например, рассмотрим следующий массив {5,76,23,65,4,4,5,4,1,1,2,2,2,2}. Если мы выполним простую быструю сортировку этого массива и выберем 4 в качестве опорного элемента, то мы зафиксируем только одно вхождение элемента 4, а остальные будут разделены вместе с другими элементами.
Вместо этого, если мы используем трехстороннюю быструю сортировку, мы разделим массив [l…r] на три подмассива следующим образом:
- Array[l…i] — здесь i — это точка опорного элемента, и этот массив содержит меньше элементов, чем опорный.
- Array[i+1…j-1] — содержит элементы, равные опорной точке.
- Array[j…r] — содержит элементы больше, чем точка опоры.
Таким образом, трехсторонняя быстрая сортировка может использоваться тогда, когда есть более одного избыточного элемента в массиве.
Рандомизированная или случайная быстрая сортировка
Техника быстрой сортировки называется рандомизированной быстрой сортировкой, когда мы используем случайные числа для выбора опорного элемента. В рандомизированной быстрой сортировке это называется «central pivot» (центральным стержнем), и делит массив таким образом, что каждая сторона имеет не менее ¼ элементов.
Псевдокод для рандомизированной быстрой сортировки приведен ниже:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
// Сортировка массива arr[low..high] с использованием рандомизированной быстрой сортировки randomQuickSort(array[], low, high) array – массив, подлежащий сортировке low – самый низкий элемент в массиве high – самый высокий элемент в начале массива начало 1. If low >= high, тогда выход. //выбрать центральный стержень 2. В то время как точка поворота "pi" не является центральной точкой поворота. (i) Выберите равномерно случайным образом число из [low..high]. Пусть pi - случайно выбранное число. (ii) Подсчитайте элементы в массиве [low..high], которые меньше , чем массив [pi]. Пусть это число будет a_low. (iii) Подсчитайте элементы в массиве [low..high], которые больше , чем массив[pi]. Пусть это число будет большим. (iv) Пусть n = (высокий-низкий+1). Если a_low >= n /4 и a_high >= n/4, то pi является центральным стержнем. //разбить массив на разделы 3. Разделите массив[low..high] вокруг the pivot pi. 4. // сортировка первой половины randomQuickSort(array, low, a_low-1) 5. // сортировка второй половины randomQuickSort(array, high-a_high+1, high) завершение процедуры |
В приведенном выше коде на «randomQuickSort» (случайной быстрой сортировке) на шаге № 2 мы выбираем центральную точку опоры. На шаге 2 вероятность того, что выбранный элемент является центральной точкой поворота, равна ½. Следовательно, ожидается, что цикл на шаге 2 будет выполнен 2 раза. Таким образом, временная сложность шага 2 в рандомизированной быстрой сортировке составляет O(n).
Использование цикла для выбора центральной опорной точки — не идеальный способ реализации случайной быстрой сортировки. Вместо этого мы можем случайным образом выбрать элемент и назвать его центральным стержнем или перетасовать элементы массива. Ожидаемая временная сложность в наихудшем случае для рандомизированного алгоритма быстрой сортировки составляет O(nlogn).
Итог
Как следует из самого названия, быстрая сортировка — это алгоритм, который сортирует список быстрее, чем любые другие алгоритмы сортировки. Как и сортировка слиянием, быстрая сортировка также использует стратегию «разделяй и властвуй».
Как вы уже поняли, с помощью быстрой сортировки мы делим список на подмассивы с помощью элемента Pivot. Затем эти подмассивы сортируются независимо друг от друга. В конце алгоритма весь массив полностью отсортирован.
Быстрая сортировка работает быстрее и эффективнее для сортировки структур данных. Быстрая сортировка — это популярный алгоритм сортировки, который иногда даже предпочтительнее алгоритма сортировки слиянием.
В нашей следующей статье мы подробно обсудим сортировку Шелла в С++.
С Уважением, МониторБанк