Rand cb быстрая сортировка случайный опорный элемент. Быстрая сортировка и с чем её едят. Как работает быстрая сортировка
Выбирая алгоритм сортировки для практических целей, программист, вполне вероятно, остановиться на методе, называемом «Быстрая сортировка» (также «qsort» от англ. quick sort). Его разработал в 1960 году английский ученый Чарльз Хоар, занимавшийся тогда в МГУ машинным переводом. Алгоритм, по принципу функционирования, входит в класс обменных сортировок (сортировка перемешиванием, пузырьковая сортировка и др.), выделяясь при этом высокой скоростью работы.
Отличительной особенностью быстрой сортировки является операция разбиения массива на две части относительно опорного элемента. Например, если последовательность требуется упорядочить по возрастанию, то в левую часть будут помещены все элементы, значения которых меньше значения опорного элемента, а в правую элементы, чьи значения больше или равны опорному.
Вне зависимости от того, какой элемент выбран в качестве опорного, массив будет отсортирован, но все же наиболее удачным считается ситуация, когда по обеим сторонам от опорного элемента оказывается примерно равное количество элементов. Если длина какой-то из получившихся в результате разбиения частей превышает один элемент, то для нее нужно рекурсивно выполнить упорядочивание, т. е. повторно запустить алгоритм на каждом из отрезков.
Таким образом, алгоритм быстрой сортировки включает в себя два основных этапа:
- разбиение массива относительно опорного элемента;
- рекурсивная сортировка каждой части массива.
Разбиение массива.
Еще раз об опорном элементе. Его выбор не влияет на результат, и поэтому может пасть на произвольный элемент. Тем не менее, как было замечено выше, наибольшая эффективность алгоритма достигается при выборе опорного элемента, делящего последовательность на равные или примерно равные части. Но, как правило, из-за нехватки информации не представляется возможности наверняка определить такой элемент, поэтому зачастую приходиться выбирать опорный элемент случайным образом.
В следующих пяти пунктах описана общая схема разбиения массива (сортировка по возрастанию):
- вводятся указатели first и last для обозначения начального и конечного элементов последовательности, а также опорный элемент mid ;
- вычисляется значение опорного элемента (first +last )/2, и заноситься в переменную mid ;
- указатель first смещается с шагом в 1 элемент к концу массива до тех пор, пока Mas [first ]>mid . А указатель last смещается от конца массива к его началу, пока Mas [last ]<mid ;
- каждые два найденных элемента меняются местами;
- пункты 3 и 4 выполняются до тех пор, пока first
После разбиения последовательности следует проверить условие на необходимость дальнейшего продолжения сортировки его частей. Этот этап будет рассмотрен позже, а сейчас на конкретном примере выполним разбиение массива.
Имеется массив целых чисел Mas , состоящий из 8 элементов (рис. 5.5): Mas . Начальным значением first будет 1, а last – 8. Пройденная часть закрашивается голубым цветом.
В качестве опорного элемента возьмем элемент со значением 5, и индексом 4. Его мы вычислили, используя выражение (first +last )/2, отбросив дробную часть. Теперь mid =5.
Первый элемент левой части сравнивается с mid . Mas >mid , следовательно first остается равным 1. Далее, элементы правой части сравниваются с mid . Проверяется элемент с индексом 8 и значением 8. Mas >mid , следовательно last смещается на одну позицию влево. Mas <mid , следовательно last остается равным 7. На данный момент first =1, а last =7. Первый и седьмой элементы меняются местами. Оба указателя смещаются на одну позицию каждый в своем направлении.
Алгоритм снова переходит к сравнению элементов. Второй элемент сравнивается с опорным: Mas >mid, следовательно first остается равным 2. Далее, элементы правой части сравниваются с mid . Проверяется элемент с индексом 6 и значением 1: Mas <mid , следовательно last не изменяет своей позиции. На данный момент first =2, а last =6. Второй и шестой элементы меняются местами. Оба указателя смещаются на одну позицию каждый в своем направлении.
Алгоритм снова переходит к сравнению элементов. Третий элемент сравнивается с опорным: Mas <mid , следовательно first смещается на одну позицию вправо. Далее, элементы правой части сравниваются с mid . Проверяется элемент с индексом 5 и значением 9: Mas >mid , следовательно last смещается на одну позицию влево. Теперь first =last =4, а значит, условие first <last не выполняется, этап разбиения завершается.
На этом этап разбиения закончен. Массив разделен на две части относительно опорного элемента. Осталось произвести рекурсивное упорядочивание его частей.
Рекурсивное доупорядочивание
Если в какой-то из получившихся в результате разбиения массива частей находиться больше одного элемента, то следует произвести рекурсивное упорядочивание этой части, то есть выполнить над ней операцию разбиения, описанную выше. Для проверки условия «количество элементов > 1», нужно действовать примерно по следующей схеме:
Имеется массив Mas [L ..R ], где L и R – индексы крайних элементов этого массива. По окончанию разбиения, указатели first и last оказались примерно в середине последовательности, тем самым образуя два отрезка: левый от L до last и правый от first до R . Выполнить рекурсивное упорядочивание левой части нужно в том случае, если выполняется условие L <last . Для правой части условие аналогично: first <R .
Реализации алгоритма быстрой сортировки:
Код программы на C++:
#include "stdafx.h"
#include
#include "stdafx.h" #include #include using namespace std ; const int n = 7 ; int first , last ; //функция сортировки void quicksort (int * mas , int first , int last ) int mid , count ; int f = first , l = last ; mid = mas [ (f + l ) / 2 ] ; //вычисление опорного элемента while (mas [ f ] < mid ) f ++ ; while (mas [ l ] > mid ) l -- ; if (f <= l ) //перестановка элементов count = mas [ f ] ; mas [ f ] = mas [ l ] ; mas [ l ] = count ; f ++ ; l -- ; } while (f < l ) ; if (first < l ) quicksort (mas , first , l ) ; if (f < last ) quicksort (mas , f , last ) ; //главная функция void main () setlocale (LC_ALL , "Rus" ) ; int * A = new int [ n ] ; srand (time (NULL ) ) ; cout << "Исходный массив: " ; for (int i = 0 ; i < n ; i ++ ) A [ i ] = rand () % 10 ; cout << A [ i ] << " " ; first = 0 ; last = n - 1 ; quicksort (A , first , last ) ; cout << endl << "Результирующий массив: " ; for (int i = 0 ; i < n ; i ++ ) cout << A [ i ] << " " ; delete A ; system ("pause>>void" ) ; |
Код программы на Pascal:
Delphi/Pascal
program qsort;
uses crt;
const n=7;
var A: array of integer;
first, last, i: integer;
{процедура сортировки}
procedure quicksort(var mas: array of integer; first, last: integer);
var f, l, mid, count: integer;
begin
f:=first;
l:=last;
mid:=mas[(f+l) div 2]; {вычисление опорного элемента}
repeat
while mas[f] program
qsort
;
uses
crt
;
const
n
=
7
;
var
A
:
array
[
1..n
]
of
integer
;
first
,
last
,
i
:
integer
;
{
процедурасортировки}
procedure
quicksort
(var
mas
:
array
[
1..n
]
of
integer
;
first
,
last
:
integer
)
;
var
f
,
l
,
mid
,
count
:
integer
;
begin
f
:=
first
;
l
:=
last
;
mid
:=
mas
[
(f
+
l
)
div
2
]
;
{
вычислениеопорногоэлемента}
repeat
while
mas
[
f
]
<
mid
do
inc
(f
)
;
while
mas
[
l
]
>
mid
do
dec
(l
)
;
Примечание: на практике обычно разделяют сортируемое множество не на три, а на две части: например, «меньшие опорного» и «равные и большие». Такой подход в общем случае оказывается эффективнее, так как для осуществления такого разделения достаточно одного прохода по сортируемому множеству и однократного обмена лишь некоторых выбранных элементов. Быстрая сортировка использует стратегию «разделяй и властвуй ». Шаги алгоритма таковы: Поскольку в каждой итерации (на каждом следующем уровне рекурсии) длина обрабатываемого отрезка массива уменьшается, по меньшей мере, на единицу, терминальная ветвь рекурсии будет достигнута всегда и обработка гарантированно завершится. Интересно, что Хоар разработал этот метод применительно к машинному переводу : дело в том, что в то время словарь хранился на магнитной ленте , и если упорядочить все слова в тексте, их переводы можно получить за один прогон ленты. Алгоритм был придуман Хоаром во время его пребывания в Советском Союзе , где он обучался в Московском университете компьютерному переводу и занимался разработкой русско-английского разговорника (говорят, этот алгоритм был подслушан им у русских студентов). //алгоритм на языке java
public
static
void
qSort(int
A, int
low, int
high)
{
int
i =
low;
int
j =
high;
int
x =
A[
(low+
high)
/
2
]
;
do
{
while
(A[
i]
<
x)
++
i;
while
(A[
j]
>
x)
--
j;
if
(i <=
j)
{
int
temp =
A[
i]
;
A[
i]
=
A[
j]
;
A[
j]
=
temp;
i++;
j--;
}
}
while
(i <
j)
;
if
(low <
j)
qSort(A, low, j)
;
if
(i <
high)
qSort(A, i, high)
;
}
//алгоритм на языке pascal
procedure
qSort(var
ar:
array
of
real
;
low,
high:
integer
)
;
var
i,
j:
integer
;
m,
wsp:
real
;
begin
i:
=
low;
j:
=
high;
m:
=
ar[
(i+
j)
div
2
]
;
repeat
while
(ar[
i]
//алгоритм на языке Visual Basic
//при первом вызове 2-ой аргумент должен быть равен 1
//3-ий аргумент должен быть равен числу элементов массива
Sub qSort(ByVal ar()
As double,
ByVal low As Integer
,
ByVal high As Integer
)
Dim i,
j As Integer
Dim m,
wsp As double
i =
low
j =
high
m =
ar((i +
j)
\ 2
)
Do
Until
i > j
Do
While
ar(i)
< m
i +=
1
Loop
Do
While
ar(j)
> m
j -=
1
Loop
If
(i <=
j)
Then
wsp =
ar(i)
ar(i)
=
ar(j)
ar(j)
=
wsp
i +=
1
j -=
1
End
If
Loop
If
(low < j)
Then
qSort(ar,
low,
j)
If
(i < high)
Then
qSort(ar,
i,
high)
End
Sub QuickSort является существенно улучшенным вариантом алгоритма сортировки с помощью прямого обмена (его варианты известны как «Пузырьковая сортировка » и «Шейкерная сортировка »), известного, в том числе, своей низкой эффективностью. Принципиальное отличие состоит в том, что после каждого прохода элементы делятся на две независимые группы. Любопытный факт: улучшение самого неэффективного прямого метода сортировки дало в результате эффективный улучшенный метод. Достоинства: Недостатки: Всем привет! Я расскажу об алгоритме быстрой сортировки и покажу, как его можно реализовать программно. // qsort (0, n-1);
Эта реализация имеет ряд недостатков, таких как возможное переполнение стека из-за большого количества вложенной рекурсии и то, что опорным элементом всегда берётся средний. Для примера это, может, и нормально, но при решении, например, олимпиадных задач, хитрое жюри может специально подобрать такие тесты, чтобы на них это решение работало слишком долго и не проходило в лимит. В принципе, в качестве опорного элемента можно брать любой, но лучше, чтобы он был максимально приближен к медиане, поэтому можно выбрать его случайно или взять средний по значению из первого, среднего и последнего. Зависимость быстродействия от опорного элемента - один из недостатков алгоритма, ничего с этим не поделать, но сильная деградация производительности происходит редко, обычно если сортируется специально подобранный набор чисел. Если всё-таки нужна сортировка, работающая гарантированно быстро, можно использовать, например, пирамидальную сортировку, всегда работающую строго за O(n log n). Обычно Qsort всё же выигрывает в производительности перед другими сортировками, не требует много дополнительной памяти и достаточно прост в реализации, поэтому пользуется заслуженной популярностью. Писáл сам, изредка поглядывая на Википедию . Пользуясь случаем, передаю спасибо замечательным преподавателям и студентам ПетрГУ, научившим меня множеству полезных вещей, в том числе и этому алгоритму! Теги:
Qsort, быстрая сортировка, алгоритмы сортировки, алгоритмы, C Представляет собой усовершенствованный метод сортировки, основанный на принципе обмена. Пузырьковая сортировка является самой неэффективной из всех алгоритмов прямой сортировки. Однако усовершенствованный алгоритм является лучшим из известных методом сортировки массивов. Он обладает столь блестящими характеристиками, что его изобретатель Ч. Хоар назвал его быстрой сортировкой. Для достижения наибольшей эффективности желательно производить обмен элементов на больших расстояниях. В массиве выбирается некоторый элемент, называемый разрешающим
. Затем он помещается в то место массива, где ему полагается быть после упорядочивания всех элементов. В процессе отыскания подходящего места для разрешающего элемента производятся перестановки элементов так, что слева от них находятся элементы, меньшие разрешающего, и справа - большие (предполагается, что массив сортируется по возрастанию). Тем самым массив разбивается на две части: Чтобы отсортировать эти два меньших подмассива, алгоритм рекурсивно вызывает сам себя. Если требуется сортировать больше одного элемента, то нужно Ключевым элементом быстрой сортировки является алгоритм переупорядочения
. Рассмотрим сортировку на примере массива: 10, 4, 2, 14, 67, 2, 11, 33, 1, 15.
Для реализации алгоритма переупорядочения используем указатель left
на крайний левый элемент массива. Указатель движется вправо, пока элементы, на которые он показывает, остаются меньше разрешающего. Указатель right
поставим на крайний правый элемент массива, и он движется влево, пока элементы, на которые он показывает, остаются больше разрешающего. Пусть крайний левый элемент - разрешающий pivot
. Установим указатель left
на следующий за ним элемент; right
- на последний. Алгоритм должен определить правильное положение элемента 10 и по ходу дела поменять местами неправильно расположенные элементы. Движение указателей останавливается, как только встречаются элементы, порядок расположения которых относительно разрешающего элемента неправильный. Указатель left
перемещается до тех пор, пока не покажет элемент больше 10; right
движется, пока не покажет элемент меньше 10. Осуществляется перестановка разрешающего элемента с элементом, на который указывает right
. Разрешающий элемент находится в нужном месте: элементы слева от него имеют меньшие значения; справа - большие. Алгоритм рекурсивно вызывается для сортировки подмассивов слева от разрешающего и справа от него. Реализация алгоритма быстрой сортировки на Си
1 #include
Было подсчитано, что до четверти времени централизованных компьютеров уделяется
сортировке данных. Это потому, что намного легче найти значение в массиве, который
был заранее отсортирован. В противном случае поиск немного походит на поиск иголки
в стоге сена. Есть программисты, которые всё рабочее время проводят в изучении и внедрении алгоритмов
сортировки. Это потому, что подавляющее большинство программ в бизнесе включает в
себя управление базами данных. Люди ищут информацию в базах данных всё время. Это означает,
что поисковые алгоритмы очень востребованы. Но есть одно "но". Поисковые алгоритмы работают намного быстрее с базами данных, которые
уже отсортированы. В этом случае требуется только линейный поиск. В то время как компьютеры находятся без пользователей в некоторые моменты времени,
алгоритмы сортировки продолжают работать с базами данных. Снова приходят пользователи,
осуществляющие поиск, а база данных уже отсортирована, исходя из той или иной цели
поиска. В этой статье приведены примеры реализации стандартных алгоритмов сортировки. Для того, чтобы отсортировать массив в порядке возрастания, следует на каждой итерации
найти элемент с наибольшим значением. С ним нужно поменять местами последний элемент.
Следующий элемент с наибольшим значением становится уже на предпоследнее место. Так
должно происходить, пока элементы, находящиеся на первых местах в массивe, не окажутся в
надлежащем порядке. Код C++
void
SortAlgo::selectionSort(int
data, int
lenD)
{
int
j = 0;
int
tmp = 0;
for
(int
i=0; i При пузырьковой сортировке сравниваются соседние элементы и меняются местами, если
следующий элемент меньше предыдущего. Требуется несколько проходов по данным. Во время
первого прохода сраваются первые два элемента в массиве. Если они не в порядке, они
меняются местами и затем сравнивается элементы в следующей паре. При том же условии они
так же меняются местами. Таким образом сортировка происходит в каждом цикле пока не будет
достигнут конец массива. Код C++
void
SortAlgo::bubbleSort(int
data, int
lenD)
{
int
tmp = 0;
for
(int
i = 0;i При сортировке вставками массив разбивается на две области: упорядоченную и
и неупорядоченную. Изначально весь массив является неупорядоченной областью.
При первом проходе первый элемент из неупорядоченной области изымается и помещается
в правильном положении в упорядоченной области. На каждом проходе размер упорядоченной области возрастает на 1, а размер неупорядоченной
области сокращается на 1. Основной цикл работает в интервале от 1 до N-1. На j-й итерации элемент [i] вставлен в
правильное положение в упорядоченной области. Это сделано путем сдвига всех
элементов упорядоченной области, которые больше, чем [i], на одну позицию вправо. [i]
вставляется в интервал между теми элементами, которые меньше [i], и теми, которые больше [i]. Код C++
void
SortAlgo::insertionSort(int
data, int
lenD)
{
int
key = 0;
int
i = 0;
for
(int
j = 1;j Код C++
void
SortAlgo::mergeSort(int
data, int
lenD)
{
if
(lenD>1){
int
middle = lenD/2;
int
rem = lenD-middle;
int
* L = new int
;
int
* R = new int
;
for
(int
i=0;i Быстрая сортировка использует алгоритм "разделяй и властвуй". Она начинается с разбиения
исходного массива на две области. Эти части находятся слева и справа от отмеченного
элемента, называемого опорным. В конце процесса одна часть будет
содержать элементы меньшие, чем опорный, а другая часть будет содержать элементы больше
опорного. Код C++
void
SortAlgo::quickSort(int
* data, int const
len)
{
int const
lenD = len;
int
pivot = 0;
int
ind = lenD/2;
int
i,j = 0,k = 0;
if
(lenD>1){
int
* L = new int
;
int
* R = new int
;
pivot = data;
for
(i=0;i
Краткое описание алгоритма
Алгоритм
Оценка эффективности
На практике (в случае, когда обмены являются более затратной операцией, чем сравнения) быстрая сортировка значительно быстрее, чем другие алгоритмы с оценкой O(n
lg n
), по причине того, что внутренний цикл алгоритма может быть эффективно реализован почти на любой архитектуре. 2C N/2 покрывает расходы по сортировке двух полученных подмассивов; N - это стоимость обработки каждого элемента, используя один или другой указатель. Известно также, что примерное значение этого выражения равно C N = N lg N.
Худший случай даёт O(n
²) обменов. Но количество обменов и, соответственно, время работы - это не самый большой его недостаток. Хуже то, что в таком случае глубина рекурсии при выполнении алгоритма достигнет n, что будет означать n-кратное сохранение адреса возврата и локальных переменных процедуры разделения массивов. Для больших значений n худший случай может привести к исчерпанию памяти во время работы алгоритма. Впрочем, на большинстве реальных данных можно найти решения, которые минимизируют вероятность того, что понадобится квадратичное время.Улучшения
Достоинства и недостатки
Примечания
Литература
незнакомец
30 мая 2011 в 15:24
Быстрая сортировка и с чем её едят
Итак, быстрая сортировка, или, по названию функции в Си, Qsort - это алгоритм сортировки, сложность которого в среднем
составляет O(n log(n)). Суть его предельно проста: выбирается так называемый опорный элемент, и массив делится на 3 подмассива: меньших опорного, равных опорному и больших опорного. Потом этот алгоритм применяется рекурсивно к подмассивам.Алгоритм
Что ж, выглядит не так уж сложно. Реализуем на Си? Нет проблем! void
qsort (int
b, int
e)
{
int
l = b, r = e;
int
piv = arr[(l + r) / 2]; // Опорным элементом для примера возьмём средний
while
(l <= r)
{
while
(arr[l] < piv)
l++;
while
(arr[r] > piv)
r--;
if
(l <= r)
swap (arr, arr);
}
if
(b < r)
qsort (b, r);
if
(e > l)
qsort (l, e);
} /* ----- end of function qsort ----- */
* This source code was highlighted with Source Code Highlighter
.
Эти элементы меняются местами и движение указателей возобновляется.
Процесс продолжается до тех пор, пока right
не окажется слева от left
.
Тем самым будет определено правильное место разрешающего элемента.
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
#define
SIZE 20
// Функция быстрой сортировки
void
quickSort(int
*numbers, int
left, int
right)
{
int
pivot; // разрешающий элемент
int
l_hold = left; //левая граница
int
r_hold = right; // правая граница
pivot = numbers;
while
(left < right) // пока границы не сомкнутся
{
while
((numbers >= pivot) && (left < right))
right--; // сдвигаем правую границу пока элемент больше
if
(left != right)
{
numbers = numbers; // перемещаем элемент на место разрешающего
left++; // сдвигаем левую границу вправо
}
while
((numbers <= pivot) && (left < right))
left++; // сдвигаем левую границу пока элемент меньше
if
(left != right) // если границы не сомкнулись
{
numbers = numbers; // перемещаем элемент на место
right--; // сдвигаем правую границу вправо
}
}
numbers = 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;
// Заполнение массива случайными числами
for
(int
i = 0; i
// Вывод элементов массива до сортировки
for
(int
i = 0; i
printf("\n"
);
quickSort(a, 0, SIZE-1); // вызов функции сортировки
// Вывод элементов массива после сортировки
for
(int
i = 0; i
printf("\n"
);
getchar();
return
0;
}
Результат выполнения
Сортировка выбором (Selection sort)
Пузырьковая сортировка (Bubble sort)
Сортировка вставками (Insertion sort)
Сортировка слиянием (Merge sort)
Быстрая сортировка (Quick sort)
