1.8.2. БЫСТРАЯ СОРТИРОВКА

Следующий пример - так называемая быстрая сортировка [АХУ 79], сущность которой заключается в следующем.

Пусть требуется отсортировать множество целых чисел S. Выберем из S произвольное число X и разобьем S на три подмножества S1, S2 и S3, такие, что S1 содержит числа, которые меньше X, S2 содержит числа, равные X, а S3 содержит числа, которые больше X. Отсортируем S1, S2 и S3, пусть при этом получились упорядоченные последовательности Q1, Q2 и Q3 (сортировка множества S2 - тривиальна, ибо все его элементы равны X). Тогда мы можем соединить Q1, Q2 и Q3 в новую последовательность Q1 Q2 Q3, которая и будет решением исходной задачи.

Определим функцию QSort, которая будет сортировать поданную на вход последовательность описанным выше методом. Для разбиения исходного множества чисел на три части используется функция  Split.