"""
           Пузырьковая сортировка
Этот простой алгоритм выполняет итерации по списку, сравнивая
элементы попарно и меняя их местами, пока более 
крупные элементы не «всплывут» в начало списка,
а более мелкие не останутся на «дне».

              Алгоритм
Сначала 
сравниваются первые два элемента списка. 
Если первый элемент больше, они меняются местами.
Если они уже в нужном порядке, оставляем их как есть. 
Затем переходим к следующей паре элементов, 
сравниваем их значения и меняем местами при необходимости. 
Этот процесс продолжается до последней пары элементов в списке.

При достижении конца списка процесс 
повторяется заново для каждого элемента. 
Это крайне неэффективно, если в массиве нужно сделать, 
например, только один обмен. Алгоритм повторяется n² раз, 
даже если список уже отсортирован.
Для оптимизации алгоритма нужно знать, когда его остановить, то есть когда список отсортирован.

Чтобы остановить алгоритм по окончании сортировки,
нужно ввести переменную-флаг. 
Когда значения меняются местами, устанавливаем флаг в 
значение True, чтобы повторить процесс сортировки. 
Если перестановок не произошло, флаг остаётся False и 
алгоритм останавливается.

Алгоритм работает в цикле while и прерывается, 
когда элементы ни разу не меняются местами. 
Вначале присваиваем swapped значение True, 
чтобы алгоритм запустился хотя бы один раз.

Время сортировки
Если взять самый худший 
случай (изначально список отсортирован по убыванию), 
затраты времени будут равны O(n²), 
где n — количество элементов списка.
"""
def bubble_sort(nums):  
    # Устанавливаем swapped в True, чтобы цикл запустился хотя бы один раз
    swapped = True
    while swapped:
        swapped = False
        for i in range(len(nums) - 1):
            if nums[i] > nums[i + 1]:
                # Меняем элементы
                nums[i], nums[i + 1] = nums[i + 1], nums[i]
                # Устанавливаем swapped в True для следующей итерации
                swapped = True

# Проверяем, что оно работает
random_list_of_nums = [5, 2, 1, 8, 4]  
bubble_sort(random_list_of_nums)  
print(random_list_of_nums)