Изменения
→Способ построить массив с максимальным количеством сравнений при детерминированном выборе опорного элемента
==Алгоритм==
Быстрый метод сортировки функционирует по принципу "разделяй и властвуй". * Массив <tex> a[l \ldots r]</tex> типа <tex> T </tex> разбивается на два (возможно пустых) подмассива <tex> a[l \ldots q]</tex> и <tex> a[q+1 \ldots r]</tex>, таких, что каждый элемент <tex> a[l \ldots q]</tex> меньше или равен <tex> a[q]</tex>, который в свою очередь, не превышает любой элемент подмассива <tex> a[q+1 \ldots r]</tex>. Индекс вычисляется в ходе процедуры разбиения.* Подмассивы <tex> a[l \ldots q]</tex> и <tex> a[q+1\ldots r]</tex> сортируются с помощью рекурсивного вызова процедуры быстрой сортировки.* Поскольку подмассивы сортируются на месте, для их объединения не требуются никакие действия: весь массив <tex> a[l \ldots r]</tex> оказывается отсортированным. ==Псевдокод== '''void''' quicksort(a: '''T'''[n], '''int''' l, '''int''' r)Выбираем опорный '''if''' l < r '''int''' q = partition(a, l, r) quicksort(a, l, q) quicksort(a, q + 1, r)Для сортировки всего массива необходимо выполнить процедуру <tex>\mathrm{quicksort(a, 0, length[a] - 1)}</tex>. ===Разбиение массива===Основной шаг алгоритма сортировки {{---}} процедура <tex>\mathrm{partition}</tex>, которая переставляет элементы массива <tex>a[l \ldots r]</tex> типа <tex> T </tex> нужным образом.Разбиение осуществляется с использованием следующей стратегии. Прежде всего, в качестве разделяющего элемента произвольно выбирается элемент. <tex> a[(l + r) / 2)Разбиваем массив таким образом] </tex>. Далее начинается просмотр с левого конца массива, который продолжается до тех пор, пока не будет найден элемент, превосходящий по значению разделяющий элемент, затем выполняется просмотр, начиная с правого конца массива, который продолжается до тех пор, пока не отыскивается элемент, который по значению меньше разделяющего. Оба элемента, на которых просмотр был прерван, очевидно, находятся не на своих местах в разделенном массиве, и потому они меняются местами. Так продолжаем дальше, пока не убедимся в том, что все элементы меньшие или равные опорному будут лежать левее опроного слева от левого указателя не осталось ни одного элемента, который был бы больше по значению разделяющего, и ни одного элементасправа от правого указателя, а большие или равные правеекоторые были бы меньше по значению разделяющего элемента. 3Переменная <tex> v </tex> сохраняет значение разделяющего элемента <tex> a[(l + r)Рекурсивно сотрируем "маленькие" / 2] </tex>, a <tex> i </tex> и <tex> j </tex> представляет собой, соответственно, указатели левого и правого просмотра. Цикл разделения увеличивает значение <tex> i </tex> и уменьшает значение <tex> j </tex> на <tex> 1 </tex>, причем условие, что ни один элемент слева от <tex> i </tex> не больше <tex> v </tex> и "большие" элементыни один элемент справа от <tex> j </tex> не меньше <tex> v </tex>, не нарушается. Как только значения указателей пересекаются, процедура разбиения завершается. '''int''' partition(a: '''T'''[n], '''int''' l, '''int''' r) '''T''' v = a[(l + r) / 2] '''int''' i = l '''int''' j = r '''while''' (i <tex> \leqslant </tex> j) '''while''' (a[i] < v) i++ '''while''' (a[j] > v) j-- '''if''' (i <tex> \geqslant </tex> j) '''break''' swap(a[i++], a[j--]) '''return''' j
==Асимптотика==