Изменения
→Алгоритм
==Алгоритм==
Быстрый метод сортировки функционирует по принципу "разделяй и властвуй".
Он делит сортируемый массив на две части, затем сортирует эти части независимо
друг от друга. Как будет показано далее, точное положение точки деления зависит от
исходного порядка элементов во входном файле. Суть метода заключается в процессе
разбиения файла, который переупорядочивает файл таким образом, что выполняются
следующие условия:
¦ Элемент a[i] для некоторого i занимает свою
окончательную позицию в массиве.
¦ Ни один из элементов a[i],..., a[i-l] не пре-
вышает a[i].
м Ни один из элементов a[i+l],..., а[г] не явля-
ется меньшим a[i].
* Массив <tex> a[l \ldots r]</tex> разбивается на два (возможно пустых) подмассива <tex> a[l \ldots q-1]</tex> и <tex> a[q+1 \ldots r]</tex>, таких, что каждый элемент <tex> a[l \ldots q-1]</tex> меньше или равен <tex> a[q]</tex>, который в свою очередь, не превышает любой элемент подмассива <tex> a[q+1 \ldots r]</tex>. Индекс вычисляется в ходе процедуры разбиения.
* Подмассивы <tex> a[l \ldots q-1]</tex> и <tex> a[q+1 \ldots r]</tex> сортируются с помощью рекурсивного вызова процедуры быстрой сортировки.
