Как проверить сортируемый список с помощью булевой переменной?

Question

[Kris]

Стоит задача такого содержания: есть список, его надо отсортировать(пузырьком):

a = [1, 8, 3, 5, 7, 4]
for i in range(len(a), 0, -1):
    for j in range(0, len(a) - 1):
        if a[j] > a[j + 1]:
            a[j], a[j + 1] = a[j + 1], a[j]

И при этом надо еще оптимизировать с помощью булевой переменной(если за последний проход сортировки изменений не было)
Подскажите, пожалуйста, как произвести оптимизацию?

Comments

[Roman K]

А для чего вам, если не секрет, оптимизировать неэффективный алгоритм? Для учёбы?

[Kris]

Roman Kitaev: Да, задача для учёбы.

Answer 1

[Виталий]

for i in range(len(a)-1, 0, -1):
    swapped = False
    for j in range(i):
        if a[j] > a[j + 1]:
            a[j], a[j + 1] = a[j + 1], a[j]
            swapped = True
    if not swapped:
        break

upd: исправил циклы. После первого прохода мы знаем, что последний элемент списка максимальный (наш "пузырек" всплыл), после второго, что предпоследний - максимальный из оставшихся и т.д.

Answer 2

[Никита Каменев]

Виталий уже написал правильный ответ, но вот немного теории:
За каждую итерацию мы сортируем один элемент, соответственно если в какой-то момент перестановок в итерации не случается, значит переставлять нечего. Именно для этого и вводиться флаг.