На этом шаге рассмотрим "О-большое" для быстрой сортировки.
Алгоритм быстрой сортировки уникален тем, что его скорость зависит от выбора опорного элемента. Прежде чем рассматривать быструю сортировку, вспомним наиболее типичные варианты времени выполнения для "О-большое".
На графиках приведены примерные оценки времени при выполнении 10 операций в секунду. Они не претендуют на точность, а всего лишь дают представление о том, насколько различается время выполнения.
Для каждого времени выполнения также приведен пример алгоритма. Возьмем алгоритм сортировки выбором. Он обладает временем О(n2), и это довольно медленный алгоритм.
Другой алгоритм сортировки - так называемая сортировка слиянием - работает за время О(n log n). Намного быстрее! С быстрой сортировкой дело обстоит сложнее. В худшем случае быстрая сортировка работает за время О(n2).
Ничуть не лучше сортировки выбором! Но это худший случай, а в среднем быстрая сортировка выполняется за время О(n log n). Что в данном случае понимается под "худшим" и "средним" случаем? Eсли быстрая сортировка в среднем выполняется за время О(n log n), а сортировка слиянием выполняется за время О(n log n) всегда, то почему бы не использовать сортировку слиянием?
На следующем шаге рассмотрим определение "худшего" и "среднего" случаев в выборе опорного элемента быстрой сортировки.
