Изменения

Проведем анализ рассекающего элемента. На рисунке обозначены закрашенные области, в левом верхнем и в правом нижнем углах. В эти области попали все элементы, которые точно меньше или больше рассекающего элемента, соответственно. В каждой области по <tex> 8 </tex> элементов, всего же в массиве <tex> 25 </tex>, то есть мы получили хорошее (то есть соответствующее нашему утверждению) разбиение массива относительно опорного элемента, так как <tex> 8 > </tex> <tex>\frac{3 \cdot 25}{10}</tex>. Теперь докажем, что алгоритм также хорошо выбирает опорный элемент и в общем случае. Доказательство представлено ниже.