Алгоритм сортировки в Python - PullRequest
Новая
       39

Алгоритм сортировки в Python

0 голосов
/ 19 сентября 2019

В настоящее время я нашел этот код, изучая видео.Тем не менее, в коде есть недостаток, о котором было сказано, но я не могу понять часть алгоритма и почему этот недостаток является «недостатком». 

i = len(numList) - 1

while i > 1:
    j = 0

    while j < i:

        # If the value on the left is bigger switch values
        if numList[j] > numList[j+1]:
            temp = numList[j]
            numList[j] = numList[j + 1]
            numList[j + 1] = temp
        else:
            print()

        j += 1

    i -= 1

for k in numList:
    print(k, end=", ")
print()

Код должен упорядочивать числа из спискачисел, однако я не могу понять две вещи из этого:

Одна - «Почему 1 вычитается из« я »?»

i = len(numList) - 1

И, во-вторых, когда последний номер алгоритма равен «1», алгоритм не упорядочит числа должным образом.Например, список «4, 2, 6, 3, 1» будет упорядочен как «2, 1, 3, 4, 6» вместо правильных «1, 2, 3, 4, 6».Люди из комментариев указали, что причина этого в том, что это должно быть «while i> 0» или «while i> = 1» вместо «while i> 1».

while i > 1:

Однако я не могу понять, почему это так.

Ответы [ 2 ]

1 голос
/ 19 сентября 2019

Алгоритм переносит максимум первых чисел i + 1 вперед (таким образом, i + 1-я позиция), переключая соседей до тех пор, пока максимум не «всплывет».В первой итерации i = len (numList) - 1, поэтому максимум всего numList (индекс начинается с 0 и заканчивается len (numList) - 1) переносится на фронт.Это максимальное значение, которое должно быть последним.Теперь вам нужно беспокоиться только о первых значениях i - 1, поэтому i уменьшается на единицу.Поскольку i> 1 забывает о переносе первого элемента вперед (будучи второй позицией), 2 и 1 в вашем примере не упорядочены правильно, так как они должны были бы переключаться.Поэтому вам необходим шаг итерации i = 1.

Существует отличный сайт, который помогает с визуализацией алгоритмов сортировки.https://visualgo.net/en/sorting?slide=1. Ваш алгоритм называется пузырьковой сортировкой.

1 голос
/ 19 сентября 2019

"Почему 1 вычитается из" i "?"

Поскольку коллекции индексируются с нулевым индексом.У вас есть N элементов, но последнее индексируемое значение всегда равно N-1

Когда j < i и вы получаете доступ к numList[j+1], тогда когда j имеет максимальное значение, j == i-1 и *Максимальное значение 1012 * равно len(numList) - 1, затем вы получаете доступ к numList[(i-1)+1] == numList[i] == numList[len(numList) - 1], который является последним доступным элементом.

два и тот, который причиняет мне боль больше всего

while i > 0 правильно, потому что на первой итерации, i == 1 и j == 0, и выпоменяйте местами j+1 == 1 и j == 0 index, когда numList[j] > numList[j+1], поэтому 2 (index 1) и 1 (index 0) будут перевернуты, и вы получите 1,2,3,4,6 от 2,1,3,4,6

...