Грокаем а Иллюстрированное пособие для программистов и любопытствующих

ЧИСЛА, ЧИСЛА, БОЛЬШИЕ 33
МЕНЬШИЕ 33 (ПУСТОК МАССИБ)

т
ОПОРНЫЙ

ЭЛЕМЕНТ



Этот процесс называется разделением. Теперь у вас имеются:

• 
  подмассив всех элементов, меньших опорного;
  
• 
  опорный элемент;
  
• 
  подмассив всех элементов, больших опорного.
  

Два подмассива не отсортированы — они просто выделены из исходного массива. Но если бы они были отсортированы, то провести сортировку всего массива было бы несложно.
]
Если бы подмассивы были отсортированы, то их можно было бы объеди­нить в порядке «левый подмассив — опорный элемент — правый подмас­сив» и получить отсортированный массив. В нашем примере получается [10, 15] + [33] + [] = [10, 15, зз], то есть отсортированный массив.
Как отсортировать подмассивы? Базовый случай быстрой сортировки уже знает, как сортировать массивы из двух элементов (левый подмассив) и пустые массивы (правый подмассив). Следовательно, если применить алгоритм быстрой сортировки к двум подмассивам, а затем объединить результаты, получится отсортированный массив!
quicksort([15, 10]) + [33] + quicksort^ [ ])
> [10, 15, 33] с Отсортированный массив
Э

тот метод работает при любом опорном элементе. Допустим, вместо 33 в качестве опорного был выбран элемент 15.
Оба подмассива состоят из одного элемента, а вы уже умеете сортировать такие подмассивы. Получается, что вы умеете сортировать массивы из трех элементов. Это делается так:

1. 
   Выбрать опорный элемент.
   
2. 
   Разделить массив на два подмассива: элементы, меньшие опорного, и элементы, большие опорного.
   
3. 
   Рекурсивно применить быструю сортировку к двум подмассивам.
   

К
ак насчет массива из четырех элементов?
Предположим, опорным снова выбирается элемент 33.
Л
\Ф 15 7

евый подмассив состоит из трех элементов. Вы уже знаете, как сортирует­ся массив из трех элементов: нужно рекурсивно применить к нему быструю сортировку.
С
ледовательно, вы можете отсортировать массив из четырех элементов. А если вы можете отсортировать массив из четырех элементов, то вы так­же можете отсортировать массив из пяти элементов. Почему? Допустим, имеется массив из пяти элементов.
В
[ j ишs



5 4

от как выглядят все варианты разделения этого массива в зависимости от выбранного опорного элемента:
2-11 ] & пгрг
ГзТГГП <$> ш
ГзТз-1 ± 1 4~| ^ь> L 3
Все эти подмассивы содержат от 0 до 4 элементов. А вы уже знаете, как отсортировать массив, содержащий от 0 до 4 элементов, с использовани­ем быстрой сортировки! Таким образом, независимо от выбора опорного элемента вы можете рекурсивно вызывать быструю сортировку для двух подмассивов.