вставки Сортировать - проблемы чтения MIT Введение в Algos

Question

МИТ Введение в алгоритмы описывает вставки вроде как:

Я написал это в Python как:

def sort(A): 
    for j in range(1, len(A)): 
     key = A[j]; 
     i = j - 1; 

     # i > 0 should be i >= 0 
     while i > 0 and A[i] > key: 
      A[i + 1] = A[i] 
      i = i - 1; 
     A[i + 1] = key 

    return A 

Однако линия while i > 0 ПРЕДСТАВЛЯЕТ ошибка - первые два ключа находятся в неправильном положении. Изменение этого параметра на while i >= 0 устраняет эту проблему.

Почему это не включено в книгу MIT Intro? Я читаю это неправильно?

Answer 1

Алгоритм в книге предполагает индексирование от 1 до A.length включительно, поэтому он начинается с индекса 2. Python имеет индексирование массива от 0 до len(A) - 1. Вы исправили это в своем range, но вы пренебрегли исправлением для него в тесте цикла. Это устраняет проблему.

Answer 2

@pjs - это точно. Я добавлю, что методический способ преобразования алгоритма, написанного для массивов на основе 1, в 0 без ошибок, заключается в использовании алгоритма as-is, кроме вычитания 1 в каждой ссылке массива, а затем использовать алгебру для упрощать. Здесь вы в конечном итоге с:

def sort(A): 
    for j in range(2, len(A) + 1): # +1 is because Python ranges exclude high limit 
    key = A[j - 1] 
    i = j - 1 
    while i > 0 and A[i - 1] > key: 
     A[i + 1 - 1] = A[i - 1] 
     i = i - 1 
    A[i + 1 - 1] = key 
    return A 

Конечно, это легко упростить, удалив + 1 - 1, так что это добавление к нулю! Результат отлично работает.

Если вы хотите, чтобы сделать код красивее с запуском внешнего диапазона на 1, а не 2, сделать замену jj = j - 1, который (при добавлении 1 к обеим сторонам) означает j = jj + 1:

def sort(A): 
    for jj in range(1, len(A)): 
    key = A[jj + 1 - 1] 
    i = jj + 1 - 1 
    while i > 0 and A[i - 1] > key: 
     A[i] = A[i - 1] 
     i = i - 1 
    A[i] = key 
    return A 

Снова удаление + 1 - 1 сек , у нас есть

def sort(A): 
    for jj in range(1, len(A)): 
    key = A[jj] 
    i = jj 
    while i > 0 and A[i - 1] > key: 
     A[i] = A[i - 1] 
     i = i - 1 
    A[i] = key 
    return A 

Это выглядит великолепно, и я бы остановился здесь. Но при замене ii = i - 1 или i = ii + 1 возможна еще одна вариация.

def sort(A): 
    for jj in range(1, len(A)): 
    key = A[jj] 
    ii + 1 = jj 
    while ii + 1 > 0 and A[ii + 1 - 1] > key: 
     A[ii + 1] = A[ii + 1 - 1] 
     ii + 1 = ii + 1 - 1 
    A[ii + 1] = key 
    return A 

Хммм ... Эти задания ii выглядят странно. Но мы все еще можем выправить все с помощью алгебры.

def sort(A): 
    for jj in range(1, len(A)): 
    key = A[jj] 
    ii = jj - 1 # Subtracted 1 from both sides 
    while ii >= 0 and A[ii] > key: # x + 1 > 0 iff x >= 0 
     A[ii + 1] = A[ii] 
     ii = ii - 1 # Subtracted 1 from both sides and simplified 
    A[ii + 1] = key 
    return A 

Ну и вот, у нас есть код, который вы предложили. Работает каждый раз.