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

Например, предположим, что в качестве опорного выбирается элемент 3. Вы применяете быструю сортировку к подмассивам.
\lUl3l4|S
Подмассивы отсортированы, и теперь из них можно собрать отсортирован­ный массив. Решение работает даже в том случае, если выбрать в качестве опорного элемент 5:
jsov-t (huuui) <§>
T
3 4- S

TjTgTtl Ф [ J
Итак, решение работает независимо от выбора опорного элемента. Следо­вательно, вы можете отсортировать массив из пяти элементов. По той же логике вы можете отсортировать массив из шести элементов и т. д.
ДОКАЗАТЕЛЬСТВО ПО ИНДУКЦИИ
Вы только что познакомились с методом доказательства по индук­ции! Это один из способов, доказывающих, что ваш алгоритм рабо­тает. Каждое индуктивное доказательство состоит из двух частей: базы (базового случая) и индукционного перехода. Звучит знакомо? Допустим, я хочу доказать, что могу подняться на самый верх стре­мянки. Если мои ноги стоят на ступеньке, то я могу переставить их на следующую ступеньку, - это индукционный переход. Таким об­разом, если я стою на ступеньке 2. то могу подняться на ступеньку 3. Что касается базового случая, я сейчас стою на ступеньке 1. Из этого следует, что я могу подняться на самый верх стремянки, каждый раз поднимаясь на одну ступеньку.
Аналогичные рассуждения применимы к быстрой сортировке. Ра­ботоспособность алгоритма для базового случая - массивов с раз­мером 0 и 1 - была продемонстрирована. В индукционном перехо­де я показал, что если быстрая сортировка работает для массива из 1 элемента, то она будет работать для массива из 2 элементов. А если она работает для массивов из 2 элементов, то она будет работать для массивов из 3 элементов и т. д. Из этого можно сделать вывод, что быстрая сортировка будет работать для всех массивов любого разме­ра. Я не буду подробно рассматривать доказательства по индукции, но это интересный метод, который идет рука об руку со стратегией <• разделя i i 11 властвуй ».