Фаза сканирования

Массив имеет нижнюю границу, равную 0 (low), и верхнюю границу, равную 9 (high). Его середина приходится на 4 элемент (mid). Первым центральным элементом является A[mid] = 550. Таким образом, все элементы массива A разбиваются на два подсписка: Sl и Sh. Меньший из них (Sl) будет содержать элементы, меньшие или равные центральному. Подсписок Sh будет содержать элементы большие, чем центральный. Поскольку заранее известно, что центральный элемент в конечном итоге будет последним в подсписке Sl, мы временно передвигаем его в начало массива, меняя местами с A[0] (A[low]). Это позволяет сканировать подсписок A[1]--A[9] с помощью двух индексов: scanUp и scanDown. Начальное значение scanUp соответствует индексу 1 (low+1). Эта переменная адресует элементы подсписка Sl. Переменная scanDown адресует элементы подсписка Sh и имеет начальное значение 9 (high). Целью прохода является определение элементов для каждого подсписка.

Оригинальность «быстрой сортировки» заключается во взаимодействии двух индексов в процессе сканирования списка. Индекс scanUp перемещается вверх по списку, а scanDown – вниз. Мы продвигаем scanUp вперед и ищем элемент A[scanUp] больший, чем центральный. В этом месте сканирование останавливается, и мы готовимся переместить найденный элемент в верхний подсписок. Перед тем, как это перемещение произойдет, мы продвигаем индекс scanDown вниз по списку и находим элемент, меньший или равный центральному. Таким образом, у нас есть два элемента, которые находятся не в тех подсписках, и их можно менять местами. Swap (A[scanUp], A[scanDown]); // менять местами партнеров

Этот процесс продолжается до тех пор, пока scanUp и scanDown не зайдут друг за друга (scanUp = 6, scanDown = 5). В этот момент scanDown оказывается в подсписке, элементы которого меньше или равны центральному. Мы попали в точку разбиения двух списков и указали окончательную позицию для центрального элемента. В нашем примере поменялись местами числа 600 и 450, 800 и 350, 650 и 400 (см. рисунок 20).

Рис. 20.

Затем происходит обмен значениями центрального элемента A[0] с A[scanDown]: Swap(A[0], A[scanDown]);

В результате у нас появляются два подсписка A[0] – A[5] и A[6] – A[9], причем все элементы первого подсписка меньше элементов второго, и последний элемент первого подсписка является его наибольшим элементом. Таким образом, можно считать, что после проделанных операций подсписки разделены элементом А[5] = 550 (рисунок 21). Если теперь отсортировать каждый подсписок по отдельности, то у нас получится полностью отсортированный массив. Заметьте, что по сути оба этих подсписка являются такими же массивами, как и исходный, поэтому к ним можно применить тот же самый алгоритм. Применение того же алгоритма к частям массива называется рекурсивной фазой.