Быстрая cортировка в C++

Техника быстрой cортировкиБыстрая сортировка — это широко используемый алгоритм сортировки, который выбирает определенный элемент, называемый «pivot», по-русски, стержнем, и разбивает массив или список для сортировки на две части на основе опорного значения s0 так, что элементы, которые меньше опорного, находятся слева от списка, а элементы больше, справа от списка.

Таким образом, список разбит на два подсписка. Подсписки могут быть необязательными для одного и того же размера. Затем быстрая сортировка «Quicksort» рекурсивно вызывает себя для сортировки этих двух подсписков.

Быстрая сортировка работает эффективно и быстро даже для больших массивов или списков.

В этой статье мы расскажем о работе быстрой сортировки вместе с некоторыми примерами программирования алгоритма quicksort.

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

Общий алгоритм

Общий алгоритм быстрой сортировки приведен ниже:

Давайте теперь посмотрим на псевдокод демонстрирующий технику быстрой сортировки:

Работа алгоритма разбиения описана ниже на примере:

Работа алгоритма разбиения

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

Далее, мы продемонстрируем работу быстрой сортировки на другой схеме ниже для лучшего понимания данной концепции.

Демонстрация работы

Давайте посмотрим на работу алгоритма быстрой сортировки. Рассмотрим следующий массив с последним элементом в качестве опорного. Кроме того, первый элемент помечен как низкий, а последний элемент — как высокий.

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

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

Читать также:  Static в С++

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

Вывод данных:

Входной массив
12 23 3 43 51 35 19 45
Массив, отсортированный с помощью быстрой сортировки
3 12 19 23 35 43 45 51

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

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

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

Далее мы реализуем алгоритм быстрой сортировки на Java:

Вывод данных:

Входной массив
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) — время, затраченное на вызов с разбиением.

Читать также:  Двухсторонняя очередь (Deque) в C++

Давайте подробно проанализируем эту временную сложность для быстрой сортировки.

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] на три подмассива следующим образом:

  1. Array[l…i] — здесь i — это точка опорного элемента, и этот массив содержит меньше элементов, чем опорный.
  2. Array[i+1…j-1] — содержит элементы, равные опорной точке.
  3. Array[j…r] — содержит элементы больше, чем точка опоры.

Читать также:  Согласование приводов и датчиков с контроллером робота

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

Рандомизированная или случайная быстрая сортировка

Техника быстрой сортировки называется рандомизированной быстрой сортировкой, когда мы используем случайные числа для выбора опорного элемента. В рандомизированной быстрой сортировке это называется «central pivot» (центральным стержнем), и делит массив таким образом, что каждая сторона имеет не менее ¼ элементов.

Псевдокод для рандомизированной быстрой сортировки приведен ниже:

В приведенном выше коде на «randomQuickSort» (случайной быстрой сортировке) на шаге № 2 мы выбираем центральную точку опоры. На шаге 2 вероятность того, что выбранный элемент является центральной точкой поворота, равна ½. Следовательно, ожидается, что цикл на шаге 2 будет выполнен 2 раза. Таким образом, временная сложность шага 2 в рандомизированной быстрой сортировке составляет O(n).

Использование цикла для выбора центральной опорной точки — не идеальный способ реализации случайной быстрой сортировки. Вместо этого мы можем случайным образом выбрать элемент и назвать его центральным стержнем или перетасовать элементы массива. Ожидаемая временная сложность в наихудшем случае для рандомизированного алгоритма быстрой сортировки составляет O(nlogn).

Итог

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

Как вы уже поняли, с помощью быстрой сортировки мы делим список на подмассивы с помощью элемента Pivot. Затем эти подмассивы сортируются независимо друг от друга. В конце алгоритма весь массив полностью отсортирован.

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

В нашей следующей статье мы подробно обсудим сортировку Шелла в С++.

С Уважением, МониторБанк

Добавить комментарий