А лгоритм быстрой сортировки был придуман Тони Хоаром, в среднем он выполняется за n·log(n) шагов. В худшем случае сложность опускается до порядка n 2 , хотя такая ситуация довольно редкая. Быстрая сортировка обычно быстрее других "скоростных" сортировок со сложностью порядка n·log(n). Быстрая сортировка не устойчивая. Обычно, она преподносится как рекурсивная, однако, может быть с помощью стека (возможно, и без него, не проверено) сведена к итеративной, при этом потребуется не более n·log(n) дополнительной памяти.
Начнём с задачи, которую обычно называют Bolts & Nuts (Болты и Гайки). Вы пошли в магазин и купили болтов и гаек, много, целых два ведра. В одном ведре болты, в другом гайки. При этом известно, что для каждого болта из ведра есть соответствующая ему по размеру гайка, и для каждой гайки есть соответствующий по размеру болт. Одна беда - у вас отключили свет и вы не можете сравнить болт с болтом и гайку с гайкой. Вы можете сравнить только гайку с болтом и болт гайкой и проверить, подходят они друг другу или нет. Задача - найти для каждой гайки соответствующий ей болт.
Пусть у нас n пар болт-гайка. Самое простое решение - "в лоб" - берём гайку и находим для неё болт. Всего надо будет проверить n болтов. Поле этого берём вторую гайку, находим для неё болт, предстоит сделать уже n-1 проверку. И так далее. Всего надо будет сделать n + (n-1) + (n-2) + ... + 1 = n 2 /2 шагов. Существует ли более простое решение?
Самое быстрое (из известных мне) решение не самое очевидное. Применим подход "разделяй и властвуй". Если множество, которое мы хотим обработать слишком большое, то разобьём его на более мелкие и применим рекурсивно наш алгоритм к каждому из них. В конце концов, когда данных будет немного, обработаем и обратно соберём их вместе.
Возьмём любой (случайный) болт и с его помощью разобьём все гайки на те, которые меньше, и те которые больше, чем нужно для этого болта. Конечно, во время разбиения мы найдём и соответствующую ему гайку. Таким образом мы получим две кучи гаек - те, которые больше и те, которые меньше. С помощью найденной гайки разобьём все болты на те, которые меньше, и те, которые больше, чем первоначальный болт. Получим две кучи болтов, мелкие и крупные.
Далее, из кучи мелких болтов выберем случайный болт и с его помощью разобьём кучу гаек (тех, которые мелкие) на две кучи. Во время разбиения найдём подходящую гайку, с помощью которой разобьём мелкие болты на две кучи и т.д. То же самое проделаем и с большей кучей. Рекурсивно будем применять этот алгоритм к каждой "подкуче". Таким образом, предстоит сделать порядка n·log(n) шагов.
Алгоритм быстрой сортировки напоминает решение нашей задачи. Сначала мы находим опорный элемент - это случайный элемент из множества, относительно которого мы будем проводить разбиение. Далее разобьём множество на три - элементы, которые больше опорного, равны ему и элементы, которые меньше. После чего рекурсивно применим алгоритм к двум оставшимся подмножествам (меньше и больше), если их длина больше единицы.
Рекурсивное решение
Ф ункция принимает в качестве аргументов массив и левую и правую границу массива. В самом начале левая граница это 0, а правая - длина массива минус один. Нам понадобятся следующие переменные
Size_t i, j;
указывают на левый и правый элементы,
Int tmp, pivot;
первая переменная для обмена при сортировке, вторая будет хранить значение опорного элемента. Сначала задаём начальные значения
I = low; j = high; pivot = a[(low + (high-low)/2)];
Здесь следует сразу же оговориться. Выбирать всегда средний элемент в качестве опорного – достаточно рискованно. Если известно, какой элемент будет выбран в качестве опорного, то можно подобрать такую последовательность, для которой сортировка будет происходить максимально медленно, за время порядка n 2 . Поэтому в качестве элемента, относительно которого будет сортировка, берут либо случайный элемент, либо медиану из первого, последнего и среднего элементов.
Пока i будет меньше j (пока они не пересекутся) делаем следующее. Во первых, нужно пропустить все уже отсортированные элементы
Do { while (a[i] < pivot) { i++; } while (a[j] > pivot) { j--; }
If (i <= j) { if (a[i] > a[j]) { tmp = a[i]; a[i] = a[j]; a[j] = tmp; } i++; j--; } } while (i <= j);
Здесь, однако, возможна ошибка. i вряд ли переполнится - размер массива не больше, чем максимальное значение типа size_t, умноженное на размер элемента массива байт (более сложные варианты даже рассматривать не будем). Но вот переменная j вообще-то может перейти через нуль. Так как переменная целочисленная, то при переходе через нуль её значение станет больше, чем i, что приведёт к зацикливанию. Поэтому необходима превентивная проверка.
If (j > 0) { j--; }
После этого цикла i и j пересекутся, i станет больше j и мы получим ещё два массива, для которых следует применить сортировку: массив от левой границы до i, и массив от j до правой границы, если, конечно, мы не вышли за пределы границ.
If (i < high) { qsortx(a, i, high); } if (j > low) { qsortx(a, low, j); }
Void qsortx(int *a, size_t low, size_t high) { size_t i, j; int tmp, pivot; i = low; j = high; pivot = a[(low + (high-low)/2)]; do { while (a[i] < pivot) { i++; } while (a[j] > pivot) { j--; } if (i <= j) { if (a[i] > a[j]) { tmp = a[i]; a[i] = a[j]; a[j] = tmp; } i++; if (j > <= j); if (i < high) { qsortx(a, i, high); } if (j > low) { qsortx(a, low, j); } }
Функция называется qsortx, чтобы не спутать со стандартной функцией быстрой сортировки qsort.
Итеративное решение
Теперь вместо того, чтобы вызывать функцию, будем сохранять в стек крайнее левое и правое значения. Можно сохранять сразу пару значений, но мы вместо этого сделаем два параллельных стека. В первый будем класть крайнее левое значение для следующего вызова, а во второй - крайнее правое. Цикл заканчивается, когда стеки становятся пустыми.
Void qsortxi(int *a, size_t size) { size_t i, j; int tmp, pivot; Stack *lows = createStack(); Stack *highs = createStack(); size_t low, high; push(lows, 0); push(highs, size - 1); while (lows->size > 0) { low = pop(lows); high = pop(highs); i = low; j = high; pivot = a[(low + (high-low)/2)]; do { while (a[i] < pivot) { i++; } while (a[j] > pivot) { j--; } if (i <= j) { if (a[i] > a[j]) { tmp = a[i]; a[i] = a[j]; a[j] = tmp; } i++; if (j > 0) { j--; } } } while (i <= j); if (i < high) { push(lows, i); push(highs, high); } if (j > low) { push(lows, low); push(highs, j); } } freeStack(&lows); freeStack(&highs); }
Код стека
#define STACK_INIT_SIZE 100 typedef struct Stack { size_t size; size_t limit; int *data; } Stack; Stack* createStack() { Stack *tmp = (Stack*) malloc(sizeof(Stack)); tmp->limit = STACK_INIT_SIZE; tmp->size = 0; tmp->data = (int*) malloc(tmp->limit * sizeof(int)); return tmp; } void freeStack(Stack **s) { free((*s)->data); free(*s); *s = NULL; } void push(Stack *s, int item) { if (s->size >= s->limit) { s->limit *= 2; s->data = (int*) realloc(s->data, s->limit * sizeof(int)); } s->data = item; } int pop(Stack *s) { if (s->size == 0) { exit(7); } s->size--; return s->data; }
Функция в общем виде
Void qsortxig(void *a, size_t item, size_t size, int (*cmp)(const void*, const void*)) { size_t i, j; void *tmp, *pivot; Stack *lows = createStack(); Stack *highs = createStack(); size_t low, high; push(lows, 0); push(highs, size - 1); tmp = malloc(item); while (lows->size > 0) { low = pop(lows); high = pop(highs); i = low; j = high; pivot = (char*)a + (low + (high-low)/2)*item; do { while (cmp(((char*)a + i*item), pivot)) { i++; } while (cmp(pivot, (char*)a + j*item)) { j--; } if (i <= j) { if (cmp((char*)a + j*item, (char*)a + i*item)) { memcpy(tmp, (char*)a + i*item, item); memcpy((char*)a + i*item, (char*)a + j*item, item); memcpy((char*)a + j*item, tmp, item); } i++; if (j > 0) { j--; } } } while (i <= j); if (i < high) { push(lows, i); push(highs, high); } if (j > low) { push(lows, low); push(highs, j); } } freeStack(&lows); freeStack(&highs); free(tmp); }
Если вы программируете и ваш код уходит дальше написания калькулятора, ты вы не раз столкнётесь или сталкивались с необходимостью отсортировать тот или иной массив данных. Существует множество способов сортировки. В этой статье мы разберём основные из них и сделаем акцент на быстрой сортировке.
Понятие быстрой сортировки
Быстрая сортировка - Quick Sort или qsort. По названию становится понятно, что это и для чего. Но если не понятно, то это алгоритм по быстрой сортировке массива, алгоритм имеет эффективность O(n log n) в среднем. Что это значит? Это значит, что среднее время работы алгоритма повышается по той же траектории, что и график данной функции. В некоторых популярных языках имеются встроенные библиотеки с этим алгоритмом, а это уже говорит о том, что он крайне эффективен. Это такие языки, как Java, C++, C#.
Алгоритм
Метод быстрой сортировки использует рекурсию и стратегию "Разделяй и властвуй".
1. В массиве ищется некий опорный элемент, для простоты лучше взять центральный, но если вы хотите поработать над оптимизацией, то придётся попробовать разные варианты.
2. Слева от опоры ищется элемент больший, чем опорный, справа - меньший, чем опорный, затем меняем их местами. Делаем это, пока максимальный справа не будет меньше, чем минимальный слева. Таким образом, все маленькие элементы кидаем в начало, большие - в конец.
3. Рекурсивно применяем данный алгоритм к левой и правой части нашего алгоритма отдельно, затем ещё и ещё, до достижения одного элемента или определённого количества элементов. Что же это за количество элементов? Есть ещё один способ оптимизировать данный алгоритм. Когда сортируемая часть становится примерно равной 8 или 16, то можно обработать её обычной сортировкой, например пузырьковой. Так мы повысим эффективность нашего алгоритма, т.к. маленькие массивы он обрабатывает не так быстро, как хотелось бы.
Таким образом, будет обработан и отсортирован весь массив. А теперь наглядно изучим данный алгоритм
Эффективность быстрой сортировки
Является ли быстрая сортировка самым быстрым алгоритмом сортировки? Однозначно нет. Сейчас появляется всё больше и больше сортировок, на данный момент самая быстрая сортировка - это Timsort, она работает крайне быстро для массивов, изначально отсортированных по-разному. Но не стоит забывать, что метод быстрой сортировки является одним из самых простых в написании, это очень важно, ведь, как правило, для рядового проекта нужно именно простое написание, а не громадный алгоритм, который сам ты и не напишешь. Timsort - тоже не самый сложный алгоритм, но звание самого простого ему точно не светит.
Реализация алгоритма
Ну вот мы и дошли до самого "вкусного". Теперь разберём, как реализовывается данный алгоритм. Как говорилось ранее, он не слишком сложен в реализации, скорее, даже прост. Но мы всё равно полностью разберём каждое действие нашего кода, чтобы вы поняли, как работает быстрая сортировка.
Наш метод называется quickSort. В нём запускается основной алгоритм, в который мы передаём массив, первый и последний его элементы. Запоминаем в переменные i и k первый и последний элемент сортируемого отрезка, чтобы не изменять эти переменные, так как они нам нужны. Затем проверяем расстояние между первым и последним проверяемым: оно больше или равно единице? Если нет, значит, мы пришли к центру и нужно выйти из сортировки этого отрезка, а если да, то продолжаем сортировку.
Затем за опорный элемент берём первый элемент в сортируемом отрезке. Следующий цикл делаем до того момента, пока не дойдём до центра. В нём делаем ещё два цикла: первый - для левой части, а второй - для правой. Их мы выполняем, пока есть элементы, подходящие под условие, или пока не дойдём до опорного элемента. Затем, если минимальный элемент всё же справа, а максимальный - слева, меняем их местами. Когда цикл заканчивается, меняем первый элемент и опорный, если опорный меньше. Затем мы рекурсивно делаем наш алгоритм для правого и левого участка массива и так продолжаем, пока не дойдём до отрезка длиной в 1 элемент. Тогда все наши рекурсивные алгоритмы будут return, и мы полностью выйдем из сортировки. Также внизу имеется метод swap - вполне стандартный метод при сортировке массива заменами. Чтобы несколько раз не писать замену элементов, пишем один раз и меняем элементы в данном массиве.
В заключение можно сказать, что по соотношению "качество-сложность" быстрая сортировка находится на лидирующей позиции среди всех алгоритмов, поэтому вам стоит однозначно взять метод на заметку и использовать при необходимости в своих проектах.
Выбирая алгоритм сортировки для практических целей, программист, вполне вероятно, остановиться на методе, называемом «Быстрая сортировка» (также «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
)
;
Функция qsort выполняет сортировку num элементов массива, на который ссылается указатель first . Для каждого элемента массива устанавливается размер в байтах, который передается через параметр size . Последний параметр функции qsort — указатель comparator на функцию сравнения, которая используется для определения порядка следования элементов в отсортированном массиве. Алгоритм сортировки используемый этой функцией сравнивает пары значений, путем вызова указанной функции сравнения, с двумя указателями на элементы массива. Эта функция не возвращает никакого значения, но изменяет содержимое массива, на который указывает first . Таким образом, элементы массива занимают новые места, согласно отсортированному порядку. Функция должна принимать два параметра — указатели на элементы массива, типа void* . Эти параметры должны быть приведены к определённым типам данных. Возвращаемое значение этой функции должно быть отрицательным, равным нулю или положительным. Если val1 меньше, равен или больше, чем val2 , функция должна вернуть отрицательное значение, ноль или положительное значение, соответственно. Примечание: на практике обычно разделяют сортируемое множество не на три, а на две части: например, «меньшие опорного» и «равные и большие». Такой подход в общем случае оказывается эффективнее, так как для осуществления такого разделения достаточно одного прохода по сортируемому множеству и однократного обмена лишь некоторых выбранных элементов. Быстрая сортировка использует стратегию «разделяй и властвуй ». Шаги алгоритма таковы: Поскольку в каждой итерации (на каждом следующем уровне рекурсии) длина обрабатываемого отрезка массива уменьшается, по меньшей мере, на единицу, терминальная ветвь рекурсии будет достигнута всегда и обработка гарантированно завершится. Интересно, что Хоар разработал этот метод применительно к машинному переводу : дело в том, что в то время словарь хранился на магнитной ленте , и если упорядочить все слова в тексте, их переводы можно получить за один прогон ленты. Алгоритм был придуман Хоаром во время его пребывания в Советском Союзе , где он обучался в Московском университете компьютерному переводу и занимался разработкой русско-английского разговорника (говорят, этот алгоритм был подслушан им у русских студентов). //алгоритм на языке 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 является существенно улучшенным вариантом алгоритма сортировки с помощью прямого обмена (его варианты известны как «Пузырьковая сортировка » и «Шейкерная сортировка »), известного, в том числе, своей низкой эффективностью. Принципиальное отличие состоит в том, что после каждого прохода элементы делятся на две независимые группы. Любопытный факт: улучшение самого неэффективного прямого метода сортировки дало в результате эффективный улучшенный метод. Достоинства: Недостатки:
Описание
Параметры:
int funccmp(const void * val1, const void * val2);
Указатель на первый элемент сортируемого массива.
Количество элементов в сортируемом массиве, на который ссылается указатель first .
Размер одного элемента массива в байтах.
Функция, которая сравнивает два элемента. Функция должна иметь следующий прототип:Возвращаемое значение
Пример: исходный код программы
//пример использования функции qsort
#include Краткое описание алгоритма
Алгоритм
Оценка эффективности
На практике (в случае, когда обмены являются более затратной операцией, чем сравнения) быстрая сортировка значительно быстрее, чем другие алгоритмы с оценкой O(n
lg n
), по причине того, что внутренний цикл алгоритма может быть эффективно реализован почти на любой архитектуре. 2C N/2 покрывает расходы по сортировке двух полученных подмассивов; N - это стоимость обработки каждого элемента, используя один или другой указатель. Известно также, что примерное значение этого выражения равно C N = N lg N.
Худший случай даёт O(n
²) обменов. Но количество обменов и, соответственно, время работы - это не самый большой его недостаток. Хуже то, что в таком случае глубина рекурсии при выполнении алгоритма достигнет n, что будет означать n-кратное сохранение адреса возврата и локальных переменных процедуры разделения массивов. Для больших значений n худший случай может привести к исчерпанию памяти во время работы алгоритма. Впрочем, на большинстве реальных данных можно найти решения, которые минимизируют вероятность того, что понадобится квадратичное время.Улучшения
Достоинства и недостатки
Примечания
Литература