13oz 02.04.2012 12:38 pidgin

поправьте, если я ошибся. в худшем случае быстрая сортировка вырождается (если так можно сказать) в сортировку пузырьком. худший случай — когда в качестве опорного элемента выбирается наибольший (для сортировки в порядке убывания) или наименьший (в порядке возрастания). так? по крайней мере, скорость выполнения — как у пузырьковой — O(n^2)

1. CodeMonkey 02.04.2012 12:44 18175212951333361540659225

Не совсем. Пузырёк подразумевает полный проход и определённый сдвиг элементов до момента, когда мы найдём самый большой. Быстрая сортировка оставит элементы как есть (точнее говоря — элементы с неравными ключами оставит как есть). Ну то есть
2 1 3
Пузырёк пройдёт за один проход и сделает 1 2 3, а быстрая сортировка (при выборе максимума на каждом шаге) сделает 2 1 3, и только потом 1 2 3.

2. 13ozCodeMonkey /1 02.04.2012 12:47 pidgin

а. ну да. что-то я затупил слегка. спасибо

Do you really want to delete ?