Как именно работает цикл в алгоритме пузырьковой сортировки?(Python 3) - PullRequest
Новая
       11

Как именно работает цикл в алгоритме пузырьковой сортировки?(Python 3)

0 голосов
/ 18 сентября 2018

Пример кода: 

def bubble_sort(my_list):
    n = len(my_list)

    for i in range(n):
        for j in range(0, n - 1 - i):
            if my_list[j] > my_list[j + 1]:
                my_list[j], my_list[j + 1] = my_list[j + 1], my_list[j]


my_list = [94, 17, 5, 28, 7, 63, 44]
bubble_sort(my_list)
print(my_list)

В приведенном выше коде я запутался в части for для __ in range () вложенного цикла.Что это делает и как это делает?Кроме того, как my_list [j], my_list [j + 1] = my_list [j + 1], my_list [j] переставляет значения списка?Извините, если это звучит глупо, но я хочу понять логику синтаксиса, который я пишу, и я не смог найти место, которое бы хорошо объяснило логику, так что, надеюсь, кто-то, кто увидит это, сможет.Спасибо за любую помощь!

1 Ответ

0 голосов
/ 18 сентября 2018

Хорошие вопросы. Я постараюсь ответить на два вопроса, которые я обнаружил в вашем посте.

Вопрос 1: Что означает для __ в диапазоне () ? Функция диапазона просто генерирует список чисел. Например, предполагая, что n = 5, диапазон (5) равен диапазону (n), который в свою очередь генерирует [0, 1, 2, 3, 4]. Длина этого списка составляет 5, 0 включительно и 5 исключительно. Поскольку списки являются итеративными в python, цикл for выполняет итерации по списку.

Например: 

for i in range(5): print(i, end=' ')

Напечатает 0 1 2 3 4

Сказав все это, что делает вложенный цикл? Ну, первое, что следует заметить, это то, что в этом случае диапазон начинается с нуля (0), поэтому у вас есть range (0, ... ). Что действительно сбивает с толку, так это вторая часть внутри функция диапазона. Чтобы понять, почему это так, нам нужно понять, как ведет себя пузырьковая сортировка.

Взяв список ввода в качестве примера: 

my_list = [94, 17, 5, 28, 7, 63, 44]

Сортировка пузырьков будет выглядеть следующим образом: 

[17, 5, 28, 7, 63, 44, 94]
[5, 17, 7, 28, 44, 63, 94]
[5, 7, 17, 28, 44, 63, 94]
[5, 7, 17, 28, 44, 63, 94]
[5, 7, 17, 28, 44, 63, 94]
[5, 7, 17, 28, 44, 63, 94]
[5, 7, 17, 28, 44, 63, 94]

Теперь обратите внимание на что-то действительно интересное в том, как сортировка по пузырькам организует список. Что делает, это берет наибольшее число и помещает его в конец списка (94), затем занимает второе по величине число и помещает его рядом с 94 в порядке (63), и так далее. Фактически наш список содержит две стороны: упорядоченную и неупорядоченную. Поскольку у нас уже есть заказанные товары, нет причин для их повторения. Вот почему у вас есть - i в выражении n - 1 - i .

Теперь, почему вы делаете вычитание -1 , вы можете спросить. Причиной является обмен, который относится ко второму вопросу.

Вопрос 2: Как, черт возьми, это (my_list [j], my_list [j + 1] = my_list [j + 1], my_list [j]) переставить мои предметы?

Приведенный выше код эквивалентен выполнению этого на других языках: 

int temp = item[i];
item[i] = item[i + 1];
item[i + 1] = temp;

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

Поскольку нам нужно поместить значение item [i] в ​​item [i + 1], было бы неправильно делать это 

item[i] = item[i + 1]

потому что тогда как мы можем назначить 

item[i + 1] = item[i]

, так как мы уничтожили предыдущее значение в item [i]. В этом случае подход заключается в использовании временной переменной, которая используется для хранения значения одного из «контейнеров», чтобы мы могли успешно выполнить обмен. Единственное, что Python делает это прекрасно, используя синтаксический сахар и позволяя программистам менять значения, просто набрав что-то вроде: 

(my_list[j], my_list[j + 1] = my_list[j + 1], my_list[j])

В заключение, для второго вопроса мы добавим -1 , потому что мы хотим поменять местами последние и вторые без получения и IndexError .

...