Быстрая сортировка

ФИО автора: Трофимов Виктор Геннадьевич

Место работы: ГКООУ санаторная школа-интернат №28 г. Ростова-на-Дону

Должность: учитель информатики и ИКТ

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

Быстрая сортировка - алгоритм сортировки массива, в большинстве случаях выполняющийся гораздо быстрей, чем простая «пузырьковая сортировка». При этом в основу быстрой сортировки положен механизм пузырьковой, но доработанный и делающий выборку не прямым проходом всех элементов массива, а лишь половины.

У нас есть массив целых чиселa[1..10]: integer:

Требуется отсортировать массив в порядке возрастания.

Сортировка производится с помощью рекурсии, процедура рекурсии должна принимать на вход два параметра - первый и последний элемент текущего отрезкадля сортировки. В самом начале сортировки текущим отрезком у нас будет отрезок с началом в 1-ый и концом в 10-й элемент.

Назовём процедуру Qsort.

procedure Qsort(p1, p2: integer);

begin

end;

Вызываться из основной части программы она будет командой qsort(1, 10):

begin

Qsort(1, 10);

end.

Так как нам придётся в течение работы программы обменивать значения, напишем ещё одну процедуру, которая будет менять значения массива друг с другом. Назовём еёSwap, на вход она получает два параметра - переменные, значения которых нужно изменить. Располагаться в теле программы процедура Swapдолжна выше процедурыQsort(мы обязаны обеспечить доступность процедурыQsort к механизмуSwap):

procedure Swap(var sw1, sw2: integer);

var tmp: integer;

begin

tmp := sw1;

sw1 := sw2;

sw2 := tmp;

end;

Идея быстрой сортировки заключается в следующем: мы находим некоторое число в массиве (произвольно, но чаще пользуются элементом массива, стоящим посередине. Так мы и сделаем). Перемещаем в правую часть массива все числа, большие значения среднего элемента, а в левую часть - меньшие значения. Дальше повторяем тот же алгоритм для первой «половины» массива, потом для «левой половины половины», «правой половины половины» массива и т.д., пока «половина» подмассива не станет состоять из одного элемента.

Для понимания «на слух» этот алгоритм недостаточно прост. Лучше один раз увидеть.

Наш массив:

Находим значение среднего элемента по формуле a[(p1 + p2) div 2]и сохраняем в переменную m (от «middle»):

m := a[(p1 + p2) div 2];

В нашем примере m становится равной 9 (a[(1 + 10) div 2] = a[5] = 9).

Здесь и далее значения маркеровp1 иp2 будут равны значениям индексов массива, а переменнойm - значение элемента массива.

Также мы должны создать ещё две переменных, отвечающих за начало и конец нашего отрезка. Данные эти понадобятся неизменными, поэтому создаём ещё две переменных, т.к. p1иp2в процессе работы будут меняться:

procedure Qsort(p1, p2: integer);

var start, finish, m: integer;

begin

start := p1;

finish := p2;

m := a[(p1 + p2) div 2];

end;

Дальше мы должны найти элемент от p1, значение которого будет больше m, постепенно приращивая на единицу p1:

while(a[p1] < m) do inc(m);

То же самое мы должны сделать для маркераp2, но уже уменьшая его на единицу каждый раз, когда значениемассива больше, чем m.

while(a[p2] > m) do dec(m);

Всё это размещается в теле процедурыQsort:

procedure Qsort(p1, p2: integer);

var start, finish, m: integer;

begin

start := p1;

finish := p2;

m := a[(p1 + p2) div 2];

while(a[p1] < m) do inc(m);

while(a[p2] > m) do dec(m);

end;

Как только цикл while закончился, мы должны обменять значения массива на найденных позициях (p1, p2), но поменять только в том случае, когда первой число стоит левее или на месте второго. И продолжить «движение» маркеров на увеличение и уменьшение:

if (p1 <= p2) then

begin

Swap(a[p1], a[p2]);

inc(p1);

dec(p2);

end;

Трассировочная таблица, обязательно разберитесь:

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

repeat

while(a[p1] < m) do inc(m);

while(a[p2] > m) do dec(m);

if (p1 <= p2) then

begin

Swap(a[p1], a[p2]);

inc(p1);

dec(p2);

end;

until(p1 > p2);

Для того, чтобы p1 когда-нибудь стало больше p2, мы в условии после обмена значений используем inc(p1) иdec(p2).

Трассировочная таблица. Попробуйте разобрать действия алгоритма:

Теперь p1 стало больше, чем p2. Цикл repeatпрекращает работу. В этом месте мы должны рекурсивно вызвать процедуруqsort, отправив параметрами новые значения с учётом переменныхstartиfinish. Выглядит это так:

if (start < p2) then Qsort(start, p2);

if (p1 < finish) then Qsort(p1, finish);

Попробуем разобраться, что же происходит.p2 = 8,start = 1,то есть условие выполняется и процедура Qsort рекурсивно вызывается с параметрами Qsort(1, 8). Работает тот же самый алгоритм для ограниченного отрезка от 1 до 8, т.е. находим значение среднего элемента среди представленных, потом меняем значения переменных больших среднему на меньшие среднему и т.п.

Что же делает вторая строка? То же самое, только вызывает процедуруQsort с параметрамиQsort(9, 10). И наша рекурсия работает с двумя последними элементами массива, значения которых 10 и 9. То есть попросту меняет их местами, и мы получаем нужную возрастающую последовательность: 9, 10.

Так как всё выполняется рекурсивно, то в конце концов мы придём к тому, что элементы будут располагаться в массиве в порядке возрастания - от 1 до 9. На понимание этого у некоторых уходит достаточное длительное время, но всё же попытайтесь смоделировать в уме цепочку рекурсивных вызовов с параметрами, сокращающими первичную длину массива.

Достаточно много хорошо изложенной информации можно посмотреть на Википедии по запросу «Быстрая сортировка». Так же на текущий момент (апрель, 2015) там предоставлена анимация работы алгоритма.

Удачи!

Текст процедур:

procedure Swap(var sw1, sw2: integer);

var tmp: integer;

begin

tmp := sw1;

sw1 := sw2;

sw2 := tmp;

end;

procedure Qsort(p1, p2: integer);

var start, finish, m: integer;

begin

start := p1;

finish := p2;

m := a[(p1 + p2) div 2];

repeat

while(a[p1] < m) do inc(m);

while(a[p2] > m) do dec(m);

if (p1 <= p2) then

begin

Swap(a[p1], a[p2]);

inc(p1);

dec(p2);

end;

until(p1 > p2);

if (start < p2) then Qsort(start, p2);

if (p1 < finish) then Qsort(p1, finish);

end;

Адрес публикации: https://www.prodlenka.org/metodicheskie-razrabotki/125367-bystraja-sortirovka