Логический тупик в простой сортировке вставок - PullRequest
Новая
       14

Логический тупик в простой сортировке вставок

1 голос
/ 07 августа 2011

Я учу себя Python, и у меня возникают трудности с относительно простой концепцией.Цель состоит в том, чтобы отсортировать список в порядке возрастания, используя сортировку вставкой.Вот код: 

def InsertionSort(A):
    for j in range(1, len(A)):
        key = A[j]
        i = j - 1
        while (i >=0) and (A[i] > key):
            A[i+1] = A[i] # this is the not understood point
            i = i - 1
        A[i+1] = key
    print A

Я не понимаю, как работает жирный шаг.Например, если бы у меня был список [6,5,4,3,1], и я добрался до второй итерации, разве мой список теперь не был бы [6,6,4,3,1]?Я присваиваю A [i + 1] (в самом первом случае это будет 5) значение A [i] (6 в первом случае).Что случилось с моей 5?Моя первоначальная попытка кода была: 

def InsertionSort(A):
    for j in range(1, len(A)):
        key = A[j]
        i = j - 1
        while (i >=0) and (A[i] > key):
            temp = A[i+1]
            A [i+1] = A[i]
            A[i] = temp
            i = i - 1
        A[i+1] = key
    print A

Этот метод тоже работает.Я не понимаю, почему первый делает так же.Кто-нибудь хочет сделать удар?

Ответы [ 2 ]

3 голосов
/ 07 августа 2011

Я думаю, что это просто из-за строки A[i+1]=key.

Первый алгоритм делает следующее: Рассмотрим список [1,2,4,5,3], предположим, что мы находимся в итерации, где j=4, т.е. мы рассматриваем списокэлемент 3.Алгоритм сохраняет элемент 3 в key и проверяет следующее: 

[1,2,4,5,3]
       ^    5>3 (key) => move 5 forward by 1 => [1,2,4,5,5]
[1,2,4,5,5]
     ^      4>3 (key) => move 4 forward by 1 => [1,2,4,4,5]
[1,2,4,4,5]
   ^        2<3 => stop inner while loop
now, make A[i+1]=key (remember: key is 3):
[1,2,3,4,5]

В отличие от вышеизложенного, второй алгоритм фактически меняет элементы в каждой итерации: 

[1,2,4,5,3]
       ^    5>3 (key) => swap 5 and 3 => [1,2,4,3,5]
[1,2,4,3,5]
     ^      4>3 (key) => swap 4 and 3 => [1,2,3,4,5]
[1,2,3,4,5]
   ^        2<3 => stop while loop 
now, make A[i+1]=key (remember: key is 3): (this is unnecessary!)
[1,2,3,4,5]
2 голосов
/ 07 августа 2011

Если вы начнете с [6,5,4,3,1], итерации будут выглядеть следующим образом:

Первый шаг: 

[6,5,4,3,1] 
    ## first number sorted`

Второй шаг (j=2): 

key <- 5

A <- [6,6,4,3,1], i <- -1  
    ## the 5 will be overridden but is still save in the key variable

A <- [5,6,4,3,1]        
    ## A[i+1] = key will restore the 5

Единственное значение, которое может быть потеряно, - это значение, содержащееся в A[j]. Но это значение всегда сохраняется в переменной key и, таким образом, может быть восстановлено на самом последнем шаге.

...