kristikys
@kristikys
QA

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

Стоит задача такого содержания: есть список, его надо отсортировать(пузырьком):
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]

И при этом надо еще оптимизировать с помощью булевой переменной(если за последний проход сортировки изменений не было)
Подскажите, пожалуйста, как произвести оптимизацию?
  • Вопрос задан
  • 293 просмотра
Решения вопроса 2
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: исправил циклы. После первого прохода мы знаем, что последний элемент списка максимальный (наш "пузырек" всплыл), после второго, что предпоследний - максимальный из оставшихся и т.д.
Ответ написан
Виталий уже написал правильный ответ, но вот немного теории:
За каждую итерацию мы сортируем один элемент, соответственно если в какой-то момент перестановок в итерации не случается, значит переставлять нечего. Именно для этого и вводиться флаг.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы