Конспект урока "Быстрая сортировка"
ФИО автора: Трофимов Виктор Геннадьевич
Место работы: ГКООУ санаторная школа-интернат №28 г. Ростова-на-Дону
Должность: учитель информатики и ИКТ
БЫСТРАЯ СОРТИРОВКА
Быстрая сортировка - алгоритм сортировки массива, в большинстве случаях выполняющийся
гораздо быстрей, чем простая «пузырьковая сортировка». При этом в основу быстрой сортировки
положен механизм пузырьковой, но доработанный и делающий выборку не прямым проходом
всех элементов массива, а лишь половины.
У нас есть массив целых чисел a[1..10]: integer:
№
1
2
3
4
5
6
7
8
9
10
Значение
1
7
2
6
9
8
3
10
4
5
Требуется отсортировать массив в порядке возрастания.
Сортировка производится с помощью рекурсии, процедура рекурсии должна принимать на
вход два параметра - первый и последний элемент текущего отрезка для сортировки. В самом
начале сортировки текущим отрезком у нас будет отрезок с началом в 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;
Идея быстрой сортировки заключается в следующем: мы находим некоторое число в массиве
(произвольно, но чаще пользуются элементом массива, стоящим посередине. Так мы и сделаем).
Перемещаем в правую часть массива все числа, большие значения среднего элемента, а в левую
часть - меньшие значения. Дальше повторяем тот же алгоритм для первой «половины» массива,
потом для «левой половины половины», «правой половины половины» массива и т.д., пока
«половина» подмассива не станет состоять из одного элемента.
Для понимания «на слух» этот алгоритм недостаточно прост. Лучше один раз увидеть.
Наш массив:
№
1
2
3
4
5
6
7
8
9
10
Значение
1
7
2
6
9
8
3
10
4
5
Находим значение среднего элемента по формуле a[(p1 + p2) div 2] и сохраняем в
переменную m (от «middle»):
m := a[(p1 + p2) div 2];
В нашем примере m становится равной 9 (a[(1 + 10) div 2] = a[5] = 9).
Переменная
p1
m
p2
№
1
2
3
4
5
6
7
8
9
10
Значение
1
7
2
6
9
8
3
10
4
5
Здесь и далее значения маркеров 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
m
p2
№
1
2
3
4
5
6
7
8
9
10
Значение
1
7
2
6
9
8
3
10
4
5
while(a[p1] <
m) do inc(m);
1
1 < 9? да, значит inc(p1)
Переменная
p1
m
p2
№
1
2
3
4
5
6
7
8
9
10
Значение
1
7
2
6
9
8
3
10
4
5
while(a[p1] <
m) do inc(m);
2
7 < 9? да, значит inc(p1)
Переменная
p1
m
p2
№
1
2
3
4
5
6
7
8
9
10
Значение
1
7
2
6
9
8
3
10
4
5
while(a[p1] <
m) do inc(m);
3
2 < 9? да, значит inc(p1)
Переменная
p1
m
p2
№
1
2
3
4
5
6
7
8
9
10
Значение
1
7
2
6
9
8
3
10
4
5
while(a[p1] <
m) do inc(m);
4
6 < 9? да, значит inc(p1)
Переменная
p1
m
p2
№
1
2
3
4
5
6
7
8
9
10
Значение
1
7
2
6
9
8
3
10
4
5
while(a[p1] <
m) do inc(m);
5
9 < 9? нет. Продолжаем со вторым циклом while
Переменная
p1
m
p2
№
1
2
3
4
5
6
7
8
9
10
Значение
1
7
2
6
9
8
3
10
4
5
while(a[p2] >
m) do dec(m);
6
5 > 9? нет. Всё. Стоп.
if (p1 <= p2)
7
5 <= 10? да. Меняем значения, используя Swap.
Swap(a[p1],
a[p2]);
8
Меняются элементы, стоящие на 5 и 10 местах, т.е. 9 и 5.
inc(p1);
9
6
dec(p2);
10
9
Переменная
p1
p2
m
№
1
2
3
4
5
6
7
8
9
10
Значение
1
7
2
6
5
8
3
10
4
9
Но! Мы должны перебрать все элементы массива в границах 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
m
№
1
2
3
4
5
6
7
8
9
10
Значение
11
1
7
2
6
5
8
3
10
4
9
Переменная
p1
p2
m
№
1
2
3
4
5
6
7
8
9
10
Значение
12
1
7
2
6
5
8
3
10
4
9
Переменная
p1
p2
m
№
1
2
3
4
5
6
7
8
9
10
Значение
13
1
7
2
6
5
8
3
10
4
9
Переменная
p1
p2
m
№
1
2
3
4
5
6
7
8
9
10
Значение
14
1
7
2
6
5
8
3
10
4
9
Переменная
p2
p1
m
№
1
2
3
4
5
6
7
8
9
10
Значение
15
1
7
2
6
5
8
3
4
10
9
Теперь 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;
