Чем пузырьковая сортировка отличается от быстрой простыми словами?
Задали разобрать пузырьковую и быструю сортировку. Вроде обе сортируют массив. В чём принципиальная разница и почему все говорят пользоваться быстрой?
3 ответа
Пузырёк тупо ходит по массиву и меняет местами соседей, если они стоят не по порядку. Проходит столько раз, сколько нужно, пока всё не уляжется. Просто, но медленно — O(n²).
Быстрая работает по принципу «разделяй и властвуй»: берёт опорный элемент (pivot), кидает всё меньшее влево, большее вправо, и рекурсивно сортирует обе половины. В среднем O(n log n), на больших данных в десятки тысяч раз быстрее.
# пузырёк
def bubble(a):
for i in range(len(a)):
for j in range(len(a) - i - 1):
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]
return a
На практике руками никто не пишет — есть sorted(). Пузырёк учат только чтобы понять идею.
Пузырёк — медленный, но устойчивый и понятный. Быстрая — быстрая, но в худшем случае (уже отсортированный массив + плохой выбор pivot) скатывается в O(n²). Поэтому в реальных либах берут гибриды типа Timsort.
В реальной жизни используй sorted().
