"""
1. Отсортируйте по убыванию методом "пузырька" одномерный целочисленный массив,
заданный случайными числами на промежутке [-100; 100). Выведите на экран
исходный и отсортированный массивы. Сортировка должна быть реализована в
виде функции. Обязательно доработайте алгоритм (сделайте его умнее).

Идея доработки: если за проход по списку не совершается ни одной сортировки,
то завершение
Обязательно сделайте замеры времени обеих реализаций
и обосновать дала ли оптимизация эффективность

Подсказка: обратите внимание, сортируем не по возрастанию, как в примере,
а по убыванию
"""
import timeit
import random


def bubble_sort_desc(lst_obj):
    n = 1
    while n < len(lst_obj):
        for i in range(len(lst_obj) - n):
            if lst_obj[i] < lst_obj[i + 1]:
                lst_obj[i], lst_obj[i + 1] = lst_obj[i + 1], lst_obj[i]
        n += 1
    return lst_obj


def bubble_sort_desc_opt(lst_obj):
    n = 1
# запоминаем длину что бы каждый раз не считать
    le = len(lst_obj)
    while True:
        flag = True
        for i in range(le - n):
            if lst_obj[i] < lst_obj[i + 1]:
                lst_obj[i], lst_obj[i + 1] = lst_obj[i + 1], lst_obj[i]
                flag = False
        if flag:
            break
        n += 1
    return lst_obj


orig_list_test = [random.randint(-100, 100) for _ in range(1000)]
print(orig_list_test)
# замеры 100
print(timeit.timeit("bubble_sort_desc(orig_list_test)",
                    setup="from __main__ import bubble_sort_desc, orig_list_test", number=1))
print(orig_list_test)

orig_list_test2 = [random.randint(-100, 100) for _ in range(1000)]
print(orig_list_test2)
# замеры 100
print(timeit.timeit("bubble_sort_desc_opt(orig_list_test2)",
                    setup="from __main__ import bubble_sort_desc_opt, orig_list_test2", number=1))
print(orig_list_test2)

'''Чуть оптимизировал сортировку. Добавил выход из цикла если массив уже отсортирован 
и запоминание размера массива один рааз что бы не вычислять каждый раз длину
На случайных данных разницы почти нет. Стало работать чуть быстрее в некоторых случаях, 
однако если массив уже подается почти отсортированным,то скорость вырастает влоть до полутора раз
можно проверить увеличив параметр number в timeit'''
