Быстрая сортировка код программы

Всем привет! Я расскажу об алгоритме быстрой сортировки и покажу, как его можно реализовать программно.

Итак, быстрая сортировка, или, по названию функции в Си, Qsort — это алгоритм сортировки, сложность которого в среднем составляет O(n log(n)). Суть его предельно проста: выбирается так называемый опорный элемент, и массив делится на 3 подмассива: меньших опорного, равных опорному и больших опорного. Потом этот алгоритм применяется рекурсивно к подмассивам.

Алгоритм

1. Выбираем опорный элемент
2. Разбиваем массив на 3 части
3. Создаём переменные l и r — индексы соответственно начала и конца рассматриваемого подмассива
4. Увеличиваем l, пока l-й элемент меньше опорного
5. Уменьшаем r, пока r-й элемент больше опорного
6. Если l всё ещё меньше r, то меняем l-й и r-й элементы местами, инкрементируем l и декрементируем r
7. Если l вдруг становится больше r, то прерываем цикл
8. Повторяем рекурсивно, пока не дойдём до массива из 1 элемента

// qsort (0, n-1);

Гарвард. CS50 на русском. 1. Короткие видео. 7. Быстрая сортировка

* This source code was highlighted with Source Code Highlighter .

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

В принципе, в качестве опорного элемента можно брать любой, но лучше, чтобы он был максимально приближен к медиане, поэтому можно выбрать его случайно или взять средний по значению из первого, среднего и последнего. Зависимость быстродействия от опорного элемента — один из недостатков алгоритма, ничего с этим не поделать, но сильная деградация производительности происходит редко, обычно если сортируется специально подобранный набор чисел. Если всё-таки нужна сортировка, работающая гарантированно быстро, можно использовать, например, пирамидальную сортировку, всегда работающую строго за O(n log n). Обычно Qsort всё же выигрывает в производительности перед другими сортировками, не требует много дополнительной памяти и достаточно прост в реализации, поэтому пользуется заслуженной популярностью.

Источник: habr.com

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

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

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

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

Быстрая сортировка (quick sort)

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

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

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

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

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

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

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

Источник: www.techiedelight.com

Быстрая сортировка

Быстрая сортировка представляет собой усовершенствованный метод сортировки, основанный на принципе обмена. Пузырьковая сортировка является самой неэффективной из всех алгоритмов прямой сортировки. Однако усовершенствованный алгоритм является лучшим из известных методом сортировки массивов. Он обладает столь блестящими характеристиками, что его изобретатель Ч. Хоар назвал его быстрой сортировкой.

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

Тем самым массив разбивается на две части:

• не отсортированные элементы слева от разрешающего элемента;
• не отсортированные элементы справа от разрешающего элемента.

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

Если требуется сортировать больше одного элемента, то нужно

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

Ключевым элементом быстрой сортировки является алгоритм переупорядочения .

Рассмотрим сортировку на примере массива:

10, 4, 2, 14, 67, 2, 11, 33, 1, 15.

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

Пусть крайний левый элемент — разрешающий pivot . Установим указатель left на следующий за ним элемент; right — на последний. Алгоритм должен определить правильное положение элемента 10 и по ходу дела поменять местами неправильно расположенные элементы.

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

Указатель left перемещается до тех пор, пока не покажет элемент больше 10; right движется, пока не покажет элемент меньше 10.

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

Процесс продолжается до тех пор, пока right не окажется слева от left .

Тем самым будет определено правильное место разрешающего элемента.

Осуществляется перестановка разрешающего элемента с элементом, на который указывает right .

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

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

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

#include
#include
#define SIZE 20
// Функция быстрой сортировки
void quickSort( int *numbers, int left, int right)
int pivot; // разрешающий элемент
int l_hold = left; //левая граница
int r_hold = right; // правая граница
pivot = numbers[left];
while (left < right) // пока границы не сомкнутся
while ((numbers[right] >= pivot) (left < right))
right—; // сдвигаем правую границу пока элемент [right] больше [pivot]
if (left != right) // если границы не сомкнулись
numbers[left] = numbers[right]; // перемещаем элемент [right] на место разрешающего
left++; // сдвигаем левую границу вправо
>
while ((numbers[left] left++; // сдвигаем левую границу пока элемент [left] меньше [pivot]
if (left != right) // если границы не сомкнулись
numbers[right] = numbers[left]; // перемещаем элемент [left] на место [right]
right—; // сдвигаем правую границу влево
>
>
numbers[left] = pivot; // ставим разрешающий элемент на место
pivot = left;
left = l_hold;
right = r_hold;
if (left < pivot) // Рекурсивно вызываем сортировку для левой и правой части массива
quickSort(numbers, left, pivot — 1);
if (right > pivot)
quickSort(numbers, pivot + 1, right);
>
int main()
int a[SIZE];
// Заполнение массива случайными числами
for ( int i = 0; i a[i] = rand() % 201 — 100;
// Вывод элементов массива до сортировки
for ( int i = 0; i printf( «%4d » , a[i]);
printf( «n» );
quickSort(a, 0, SIZE-1); // вызов функции сортировки
// Вывод элементов массива после сортировки
for ( int i = 0; i printf( «%4d » , a[i]);
printf( «n» );
getchar();
return 0;
>

Результат выполнения

Комментариев к записи: 50

Источник: prog-cpp.ru