Как наличие одинаковых элементов в сортируемой последовательности влияет на быструю сортировку?
Допустим, все элементы массива одинаковы (вы уж простите, но в нашем колхозе последовательности не сортируют).
Тогда всякое разбиение массива на два сортируемых подмассива идёт криво: все элементы массива сбиваются по одну сторону (влево, вправо - тут зависит от реализации) от медианного.
Итого: время сортировки порядка n^2 вместо заветного n*log(n). Количество присваиваний, бл*дь, n-1 (столько раз выбирается медиана) - в отличие от количества сравнений.
Удачной сессии.
Смотря как писать сортировку - здесь всё зависит от мелких деталей.
Если не помнить, что элементы могут быть одинаковыми, легко свалиться в O(n^2).
Можно написать так, что число сравнений не изменится, но одинаковые элементы будут вхолостую переставляться друг с другом.
Можно на каждом шагу бояться, что могут встретиться одинаковые элементы, и делить массив на три части - меньше опорного, равные ему и большие его. Тогда при большом количестве одинаковых элементов будет работать быстро, но когда одинаковых элементов нет - то число сравнений будет в 1.6 раза больше.
Можно при разделении смотреть, был ли хоть один элемент равен опорному, и отделять равные только если был. Тогда будет плохо, когда каждый элемент встречается ровно два раза.
Есть и другие способы. И всё это будет quicksort. Если всё написать правильно, то чем больше одинаковых элементов, тем быстрее будет сортировка.