@alex11235

Как это работает (оптимизация пузырьковой сортировки)?

Всем привет. Изучаю основы Python и в задаче по оптимизации пузырькового алгоритма сортировки столкнулся с тем, что правильный на первый взгляд код выдавал не до конца отсортированный список. Вот сам код:
a = [3, 2, 4, 1, 9, 6, 5, 7]
swap = True
for i in range(len(a) - 1):   
    if swap == False:
        break
    for j in range(len(a) - i - 1):
        x1, x2 = a[j], a[j + 1]
        if a[j] > a[j + 1]:
            a[j], a[j + 1] = a[j + 1], a[j]            
            swap = True
        else:
            swap = False
print(a)


Методом тыка я выяснил, что в предпоследней строке после 'else:' надо оставить только False, а 'swap =' убрать. Получилось так:
a = [3, 2, 4, 1, 9, 6, 5, 7]
swap = True
for i in range(len(a) - 1):   
    if swap == False:
        break
    for j in range(len(a) - i - 1):
        x1, x2 = a[j], a[j + 1]
        if a[j] > a[j + 1]:
            a[j], a[j + 1] = a[j + 1], a[j]            
            swap = True
        else:
            False
print(a)

Всё работает. Но, в чём разница я не понимаю. На 14-м шаге (смотрю на pythontutor) правильный код после строки if a[j] > a[j + 1]: идёт на новый цикл, а не правильный идёт на 12-ю строку и меняет значение переменной swap на False. Собственно вопрос мой следующий: в чём по сути заключается разница между этими двумя вариантами? Мне на первый взгляд казалось, что после else: естественно писать swap = False, ведь мы присваиваем переменной новое значение, значит, она (переменная) должна быть указана слева от знака присвоения, а фактически программа работает только без указания там самой переменной. Понимаю, что упустил что-то важное, но что, не могу додуматься.
  • Вопрос задан
  • 147 просмотров
Пригласить эксперта
Ответы на вопрос 2
Sanasol
@Sanasol
нельзя просто так взять и загуглить ошибку
Ну так во втором варианте вы убили всю логику связанную со swap т.е. оно никогда не становится false, и соответственно сортирует как и должно до упора.

А когда вы впиливаете туда свой непонятный swap с проверкой, то на следующих итерациях первого цикла ничего не происходит.
Получается что в момент когда сортировка доходит до каких-то двух чисел которые НЕ надо перемещать сортировка ломается об swap = false, а выдаёт то что насортировало до этого момента, а оставшуюся часть в том порядке как было изначально.
Ответ написан
milssky
@milssky
Координатор племени фиолетовых обезьянок
Самое время почувствовать, в чем разница между break и continue.
Ответ написан
Ваш ответ на вопрос

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

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