13oz
02.04.2012 12:38 pidgin
поправьте, если я ошибся. в худшем случае быстрая сортировка вырождается (если так можно сказать) в сортировку пузырьком. худший случай — когда в качестве опорного элемента выбирается наибольший (для сортировки в порядке убывания) или наименьший (в порядке возрастания). так? по крайней мере, скорость выполнения — как у пузырьковой — O(n^2)
3 comments
recommend
bookmark
subscribe
Не совсем. Пузырёк подразумевает полный проход и определённый сдвиг элементов до момента, когда мы найдём самый большой. Быстрая сортировка оставит элементы как есть (точнее говоря — элементы с неравными ключами оставит как есть). Ну то есть
2 1 3
Пузырёк пройдёт за один проход и сделает 1 2 3, а быстрая сортировка (при выборе максимума на каждом шаге) сделает 2 1 3, и только потом 1 2 3.
а. ну да. что-то я затупил слегка. спасибо
http://blog.gamedeff.com/?p=259