Введение
Быстрая сортировка — это алгоритм сортировки, разработанный Тони Хоаром в 1959 году. Он основан на подходе «разделяй и властвуй», при котором проблема делится на более мелкие подзадачи. Он широко считается лучшим универсальным алгоритмом сортировки. Итак, как это работает на самом деле?
Подход
Алгоритм основан на идее разделения массива на более мелкие подмассивы. Начнем с выбора «осевого» элемента, элемента, вокруг которого будут сортироваться другие элементы. Любой элемент массива может быть выбран в качестве опорного. Цель алгоритма — найти правильное место в отсортированном массиве для нашего опорного элемента, сравнив с ним другие элементы и создав два подмассива: один со всеми элементами, которые меньше опорного, а другой — со всеми элементами, которые больше. чем это.
Процедура
Итак, предположим, что у нас есть массив из n целых чисел, расположенных случайным образом. Выбираем опорный элемент.
Теперь мы просматриваем массив, используя 2 индекса (скажем, i и j) одновременно с обоих направлений — спереди и сзади, и ищем элементы, которые «не на месте». Точнее, мы ищем элементы больше, чем точка поворота спереди, и элементы меньше, чем точка поворота, сзади. Когда мы находим 2 элемента, 1 больший и 1 меньший, мы меняем их местами. Мы повторяем этот процесс, пока 2 индекса не пересекутся.
Как только не будет найдено больше элементов для замены, мы меняем опорные элементы на элемент с j-м индексом. Поскольку все элементы в левом подмассиве меньше, а элементы в правом подмассиве больше, чем опорный элемент, опорный элемент теперь отсортирован и имеет правильный индекс.
Теперь мы рекурсивно повторяем эту процедуру для левого и правого подмассивов, пока все элементы не будут отсортированы.
Объяснение на примере
1. Возьмем массив, состоящий из 10 элементов, расположенных в случайном порядке —
A[10] ={4, 1 ,5 ,7 ,6 ,8 ,2 ,10 ,3 ,9 }
2. Давайте выберем элемент с индексом 0 или 4 в качестве нашей «осевой».
A[10] ={4, 1 ,5 ,7 ,6 ,8 ,2 ,10 ,3 ,9 }
3. Проходя спереди, увеличивая i, мы ищем элемент больше 4. Мы находим, что 5>4.
A[10] ={4, 1 ,5 ,7 ,6 ,8 ,2 ,10 ,3 ,9 }
4. Теперь мы проходим сзади, уменьшая j, и ищем элемент меньше 4. Мы находим, что 3‹4.
A[10] ={4, 1 ,5 ,7 ,6 ,8 ,2 ,10 ,3 ,9 }
5. Мы меняем местами 3 и 5. Массив, который мы получаем, -
A[10] ={4, 1 ,3 ,7 ,6 ,8 ,2 ,10 ,5 ,9 }
6. Давайте продолжим траверс с фронта, где мы остановились, т.е. индекс 2. Мы находим, что 7›4
A[10] ={4, 1 ,3 ,7 ,6 ,8 ,2 ,10 ,5 ,9 }
7. Делаем то же самое с обратной стороны и продолжаем поиск с индекса 8. Находим, что 2‹4.
A[10] ={4, 1 ,3 ,7 ,6 ,8 ,2 ,10 ,5 ,9 }
8. Еще раз поменяем местами 2 и 10.
A[10] ={4, 1 ,3 ,2 ,6 ,8 ,7 ,10 ,5 ,9 }
9. Продолжаем обход с фронта. Находим 6›4.
A[10] ={4, 1 ,3 ,2 ,6 ,8 ,7 ,10 ,5 ,9 }
10. Поскольку мы не можем найти больше элементов меньше 4 до того, как i и j пересекутся друг с другом, мы заканчиваем наш поиск с i по индексу 4 и j по индексу 3.
11. Теперь мы меняем опорный элемент 4 на элемент с индексом 3, т.е. 2. В итоге мы получаем следующий массив:
A[10] ={2, 1 ,3 ,4 ,6 ,8 ,7 ,10 ,5 ,9 }
Как видно, массив разбивается на 2 подмассива вокруг элемента 4. Все элементы до 4 меньше 4, а все элементы после него больше.
Псевдокод
partition (A[], low, high)
pivot=A[low];
i=l, j=h;
while(i<j)
while(A[i]<=pivot)
i++;
while(A[j]>pivot)
j--;
if(i<j)
swap(A[i],A[j]);
swap(A[low],A[j]);
return j;
QuickSort(A[], low, high)
if(low<high)
x= partition(A, low, high);
QuickSort(A, low, x-1);
QuickSort(A, x+1, high);
Временная сложность
Хотя быстрая сортировка, как правило, является очень эффективным алгоритмом, его временная сложность может немного варьироваться в зависимости от расположения элементов в массиве. Давайте проанализируем временную сложность-
В лучшем случае
Наилучший случай для быстрой сортировки возникает, когда средний элемент массива выбирается в качестве опорного.
Ω (n журнал (n))
Средний случай-
В среднем временная сложность также будет одинаковой.
θ (n журнал (n))
В худшем случае
Наихудший случай для быстрой сортировки возникает, когда массив уже отсортирован и первый или последний элемент берется в качестве опорного.
O(n²)
Вот временные сложности некоторых других алгоритмов сортировки контекста.
Но зачем использовать быструю сортировку?
Как видно из приведенного выше сравнения временной сложности, существуют некоторые алгоритмы, такие как сортировка слиянием или сортировка кучей, которые имеют одинаковую временную сложность в лучшем и среднем случае, но гораздо лучшую временную сложность в худшем случае, чем быстрая сортировка. Итак, зачем использовать быструю сортировку?
- Ну, для одной быстрой сортировки требуется значительно меньше места, чем сортировка слиянием, что делает ее превосходной сортировкой, когда пространство является фактором.
- Еще одна важная вещь, которую следует отметить, заключается в том, что, хотя сортировка кучей в теории имеет гораздо лучшую временную сложность в худшем случае, на практике она редко дает преимущество. Маловероятно, что в реальной жизни мы столкнемся со сценариями, в которых сортировка краевой кучи имеет значение временной сложности в худшем случае.
- Быстрая сортировка в большинстве случаев быстрее и последовательнее и более практична, чем другие сортировки. Он не делает никаких ненужных свопов, как другие алгоритмы. Время, затрачиваемое другими типами на выполнение ненужных свопов, не учитывается в теоретической временной сложности.
Вывод
Быстрая сортировка — это высокоэффективный и широко используемый алгоритм сортировки в компьютерных науках. Он последователен, практичен и является предпочтительным алгоритмом сортировки большинства программистов.
