8. Быстрая сортировка разделением

Этот метод основан на принципе обмена. К. Хоар, создатель метода, окрестил его быстрой сортировкой (QuickSort).

Быстрая сортировка основана на том факте, что для достижения наибольшей эффективности желательно производить обмены элементов на больших расстояниях. Реализуется она на основе следующего алгоритма: выбирается любой произвольный элемент массива, называемый медианой далее массив просматривается слева направо до тех пор, пока не будет найден элемент c ключом, большим ключа медианы, допустим это элемент a[i]. Затем массив просматривается справа налево, пока не будет найден элемент a[j], ключ которого меньше ключа медианы. Найденные элементы a[i] и a[j] меняются местами. Затем продолжается процесс «просмотра с обменом», пока два просмотра не встретятся где-то в середине массива. В результате массив разделится на две части: левую  с ключами меньшими медианы; и правую  с большими ключами.

Обычно в качестве медианы выбирается срединный элемент. Если, например, выбрать средний ключ, равный 42, из массива ключей

44, 55, 12, 42, 94, 06, 18, 67,

то для того, чтобы разделить массив, потребуются два обмена:

Конечные значения индексов i=5 и j=3. Ключи a[0], ..., a[i-2] меньше или равны ключу x=42, ключи a[j], ..., a[HighIndex] больше или равны x. Следовательно, мы получили два подмассива

a[k].Кey  x.Кey для k=0, ..., i2,

a[k].Кey  x.Кey для k=j, ..., HighIndex.

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

Procedure Partition(L, R: Integer);

Var i, j: integer;

w, x: TElement;

Begin

If L=R Then Exit;

i:= L; j:= R;

x:= a[(L+R) div 2 - 1];

Repeat

While a[i-1].Key < x.Key Do i:= i+1;

While a[j-1].Key > x.Key Do j:= j-1;

If i <= j Then Begin

w:= a[i-1]; a[i-1]:= a[j-1]; a[j-1]:= w;

i:= i+1; j:= j-1;

End;

Until i > j;

If L < j Then Partition(L, j);

If i < R Then Partition(i, R);

End;

Для запуска процесса сортировки нужно выполнить процедуру QuickSort, которая имеет простую структуру:

Procedure QuickSort;

Begin

Partition(1, N);

End;

Обменная сортировка разделением  самый эффективный из известных методов внутренней сортировки. Это связано с небольшим числом обменов, выполняемых на большие расстояния. Однако быстрая сортировка все же имеет свои «подводные камни». Прежде всего, при небольших значениях N ее эффективность невелика, как и у всех усовершенствованных методов.

3. Внешняя сортировка

В случае если сортируемые данные не помещаются в оперативной памяти, а расположены на внешнем запоминающем устройстве, то методы их обработки называют «внешними методами», например, «внешний поиск», «внешняя сортировка». Исторически получилось так, что до повсеместного использования файлов прямого доступа сортируемые таблицы большого размера размещали на магнитных лентах, которые допускали только последовательный доступ. При последовательном доступе для перехода от любого текущего элемента, например х, к элементу y, расположенному перед х, приходится просматривать всю исходную таблицу с начала. Пример оперативной структуры с последовательным доступом – линейный односвязный список. В общем случае структура с последовательным доступом характеризуется тем, что в каждый момент имеется непосредственный доступ к одному и только одному элементу. Это  строгое ограничение по сравнению с возможностями, которые дает массив (массив – оперативная структура с прямым доступом), и поэтому здесь приходится применять другие методы сортировки.

Основной метод  это сортировка слиянием. Слияние означает объединение двух (или более) упорядоченных последовательностей в одну упорядоченную последовательность при помощи циклического выбора элементов, доступных в данный момент. Слияние  намного более простая операция, чем сортировка; она используется в качестве вспомогательной в более сложном процессе последовательной сортировки.

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