Как наличие одинаковых элементов в сортируемой последовательности влияет на быструю сортировку?

Question

[Оленька Юринова]

Как наличие одинаковых элементов в сортируемой последовательности влияет на быструю сортировку?на количество присваиваний,и в целом?

Answer 1

[bobrovskyserg]

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

Comments

[LapunovaLiza]

Такой ты неприятный, фу

Answer 2

[Mrrl]

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

Comments

[Алексей Мережко]

Хотелось бы получить ссылки на примеры реализаций алгоритма quicksort при работе с одинаковыми данными, чтобы они не перемешивались. Т.е. деление массива на 3 части с последующей обработкой.