Изменения

Основной шаг алгоритма сортировки {{---}} процедура <tex>\mathrm{partition}</tex>, которая переставляет элементы массива <tex>a[l \ldots r]</tex> типа <tex> T </tex> нужным образом.Разбиение осуществляется с использованием следующей стратегии. Прежде всего, в качестве разделяющего элемента произвольно выбирается элемент а<tex> a[гr] </tex> — он сразу займет свою окончательную позицию. Далее начинается просмотр с левого конца массива, который продолжается до тех пор, пока не будет найден эле- ментэлемент, превосходящий по значению разделяющий элемент, затем выполняется про- смотрпросмотр, начиная с правого конца массива, который продолжается до тех пор, пока не отыскивается элемент, который по значению меньше разделяющего. Оба элемента, на которых просмотр был прерван, очевидно, находятся не на своих местах в разде- ленном разделенном массиве, и потому они меняются местами. Так продолжаем дальше, пока не убедимся в том, что слева от левого указателя не осталось ни одного элемента, который был бы больше по значению разделяющего, и ни одного элемента справа от правого указателя, которые были бы меньше по значению разделяющего элемента.

Переменная <tex> v </tex> сохраняет значение разделяющего элемента <tex> a[r]</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>, не нарушается. Как только значения указателей пересекаются, процедура разбиения завершает- сязавершается, меняя местами а<tex> a[гr] </tex> и <tex> a[i]</tex>, при этом <tex> v </tex> присваивается зна- чение значение <tex> a[i]</tex>, так что не будет ни одного большего элемента справа от <tex> v </tex> и ни одного меньшего элемента слева от <tex> v</tex>.