Вопрос №156

Сортировка. QuickSort.

Основывается на выборе опорного элемента и дальнейшей сортировке элементов на группы: меньше / равны / большего опорного. В качестве опорного элемента эффективно выбирать медианное значение. Медианное значение - значение, которое находится в середине отсортированного списка. Алгоритм:

1. Выбираем опорный элемент.
2. Перераспределяем элементы относительно опорного - слева меньше, справа больше.
3. Рекурсивно выполняем п 1 и п 2 на полученных подмассивах.
4. Рекурсия не применяется, если в подмаслила остался 1 элемент или вообще ни одного.