На этом шаге мы наметим план дальнейшего изложения.
Известная задача в информатике - разбиение списка следующим способом.
- В списке выбирается "опорный" элемент - обычно первый, средний или выбранный наугад.
- Элементы входного списка меняются местами внутри него таким образом, чтобы начальные элементы были не больше опорного, а все остальные больше него.
Рисунок 1 иллюстрирует идею на конкретном примере.
Рис.1. Разделение списка, используемого в алгоритмах quicksort и quickselect
Задача относится к числу важнейших, поскольку метод разбиения лежит в основе таких выдающихся алгоритмов, как quickselect или quicksort. Есть несколько известных и эффективных алгоритмов, также использующих "схему разбиения" и решающих ту же задачу. Самый популярный из них - метод разбиения, разработанный Чарльзом Хоаром, который мы вкратце рассмотрим в дальнейшем. Но сначала мы разберём более простые и интуитивно понятные рекурсивные алгоритмы.
На следующем шаге мы рассмотрим основную схему разбиения.
