На этом шаге продолжим рассматривать быструю сортировку.
Этот метод работает при любом опорном элементе. Допустим, вместо 33 в качестве опорного был выбран элемент 15.
Оба подмассива состоят из одного элемента, а вы уже умеете сортировать такие подмассивы. Получается, что вы умеете сортировать массивы из трех элементов. Это делается так:
- Выбрать опорный элемент.
- Разделить массив на два подмассива: элементы, меньшие опорного, и элементы, большие опорного.
- Рекурсивно применить быструю сортировку к двум подмассивам.
Как насчет массива из четырех элементов?
Предположим, опорным снова выбирается элемент 33.
Левый подмассив состоит из трех элементов. Вы уже знаете, как сортируется массив из трех элементов: нужно рекурсивно применить к нему быструю сортировку.
Следовательно, вы можете отсортировать массив из четырех элементов. А если вы можете отсортировать массив из четырех элементов, то вы также можете отсортировать массив из пяти элементов. Почему? Допустим, имеется массив из пяти элементов.
Вот как выглядят все варианты разделения этого массива в зависимости от выбранного опорного элемента:
Все эти подмассивы содержат от О до 4 элементов. А вы уже знаете, как отсортировать массив, содержащий от О до 4 элементов, с использованием быстрой сортировки! Таким образом, независимо от выбора опорного элемента вы можете рекурсивно вызывать быструю сортировку для двух подмассивов.
Итак, решение работает независимо от выбора опорного элемента. Следовательно, вы можете отсортировать массив из пяти элементов. По той же логике вы можете отсортировать массив из шести элементов и т. д.
На следующем шаге рассмотрим программный код быстрой сортировки.
