Сортировка пузырьком | Алгоритмы на Python

[@mouse-ml]

Кстати, сортировку можно закончить раньше, если на одном из проходов не было сделано ни одного обмена. Худшую сложность по времени (о) это не изменит, потому что в худшем случае ранней остановки и не произойдет. Но в среднем алгоритм станет эффективнее.
Напишите, если что-то было непонятно или хочется увидеть что-то конкретное в следующих видео. А еще залетайте в Телеграм: t.me/ml_mouse

[@atamanbananan]

Я делал лабу на эту сортировку, но на C++.
То что ты показал в ролике - типичная реализация с форумов. Советую почитать Кнута. Реализация по Кнуту в 5 раз быстрее отрабатывает чем те, которые предлагает нейронка и интернет.
Проводил иследование: там на массив 5к чисел - (15 милисек - 121 микросек) было затрачено.

[@mouse-ml]

@@atamanbananan я не претендую на самую эффективную реализацию - цель видео показать ее как можно проще и нагляднее, поэтому даже ранняя остановка алгоритма в видео не показана. Тесты были на разных рандомных массивах?

[@kapykta842]

классное видео

[@bobby_ridge]

def bubble_sort(arr: list[int]):
while True:
for i in range(len(arr) - 1):
if arr[i] > arr[i + 1]:
arr[i], arr[i + 1] = arr[i + 1], arr[i]
break
else:
return arr

[@mouse-ml]

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