Алгоритм сортировки вставок.Что происходит шаг за шагом? - PullRequest
Новая
       7

Алгоритм сортировки вставок.Что происходит шаг за шагом?

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

Я новый студент, изучающий данные, и пытаюсь понять, что именно происходит внутри алгоритма сортировки вставок.

Может кто-нибудь сказать мне, что происходит шаг за шагом?Это было бы очень ценно.

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

A = [4, 1, 7, 52, 10, 12]
B = [4, 1, 7, 52, 10, 12]


def InsertionSort(A):

    for j in range(1, len(A)):

        print("***************** LOOP", j, "*********************\n")

        key = A[j]
        i = j - 1
        print("i:", i, " |  A[i]:", A[i], " |  key:", key, "\n")
        print("IS i:", i, ">= 0 and", A[i], ">", key, "?", "\n")

        while i >= 0 and A[i] > key:

            print("TRUE:", i, ">= 0 and", A[i], ">", key, "\n")

            A[i + 1] = A[i]  # left cell switches places with right cell
            i = i - 1

        A[i + 1] = key

    print("\n\n")
    print("=================== END =====================")


InsertionSort(A)
print("A (not-sorted): ", B)
print("A (sorted): ", A)

Я не понимаю, как это переключает номера.

Ответы [ 3 ]

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

Функция упорядочивает данный массив. Сначала он перебирает элементы массива, начиная со второго элемента: 

for j in range(1, len(A)):

Затем он сравнивает элемент j (key) с элементом j-1 (A[i]): 

while i >= 0 and A[i] > key:

В случае, если элемент j-1 больше, чем элемент j, он должен поменять их местами, поэтому он выполняет обмен: 

A[i + 1] = A[i]

Теперь необходимо проверить, верно ли это также для элемента j-2, следовательно, цикла while. Надеюсь, это немного поможет.

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

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

Чтобы сделать это, внешнийЦикл рассматривает каждый элемент в массиве (пропустите элемент 0, потому что сравнивать его не с чем, и вы не хотите IndexError).Внутренний цикл перемещает элемент, начиная с текущего индекса i, влево, сравнивая его с каждым предыдущим элементом j-1 в массиве до тех пор, пока не будет отсортирована секция массива, видимая до сих пор.

Ваш отладочный вывод полагаетсяслишком сильно на текст и числа, а не на визуальный вид массива, и это все, что нужно, чтобы увидеть алгоритм в действии.Я также рекомендую использовать немного больший размер массива.

Кроме того, я рекомендую придерживаться Python camel_case соглашения об именах .

Играть с этим repl и пошагово пройдитесь по выводу, и я думаю, вы увидите, что происходит: 

a = [7, 3, 6, 9, 4, 5, 8, 0, 1, 2]

def insertion_sort(a):
    for i in range(1, len(a)):
        j = i
        print("moving %d:" % a[j])

        while j > 0 and a[j-1] > a[j]:
            a[j-1], a[j] = a[j], a[j-1]
            j -= 1
            print(a)
            print(" " + "   " * j + "^---")

        print()

print("original: \n" + str(a) + "\n")
insertion_sort(a)

Вывод: 

original: 
[7, 3, 6, 9, 4, 5, 8, 0, 1, 2]

moving 3:
[3, 7, 6, 9, 4, 5, 8, 0, 1, 2]
 ^---       

moving 6:
[3, 6, 7, 9, 4, 5, 8, 0, 1, 2]
    ^---

moving 9:

moving 4:
[3, 6, 7, 4, 9, 5, 8, 0, 1, 2]
          ^---
[3, 6, 4, 7, 9, 5, 8, 0, 1, 2]
       ^---
[3, 4, 6, 7, 9, 5, 8, 0, 1, 2]
    ^---

moving 5:
[3, 4, 6, 7, 5, 9, 8, 0, 1, 2]
             ^---
[3, 4, 6, 5, 7, 9, 8, 0, 1, 2]
          ^---
[3, 4, 5, 6, 7, 9, 8, 0, 1, 2]
       ^---

moving 8:
[3, 4, 5, 6, 7, 8, 9, 0, 1, 2]
                ^---

moving 0:
[3, 4, 5, 6, 7, 8, 0, 9, 1, 2]
                   ^---
[3, 4, 5, 6, 7, 0, 8, 9, 1, 2]
                ^---
[3, 4, 5, 6, 0, 7, 8, 9, 1, 2]
             ^---
[3, 4, 5, 0, 6, 7, 8, 9, 1, 2]
          ^---
[3, 4, 0, 5, 6, 7, 8, 9, 1, 2]
       ^---
[3, 0, 4, 5, 6, 7, 8, 9, 1, 2]
    ^---
[0, 3, 4, 5, 6, 7, 8, 9, 1, 2]
 ^---

moving 1:
[0, 3, 4, 5, 6, 7, 8, 1, 9, 2]
                      ^---
[0, 3, 4, 5, 6, 7, 1, 8, 9, 2]
                   ^---
[0, 3, 4, 5, 6, 1, 7, 8, 9, 2]
                ^---
[0, 3, 4, 5, 1, 6, 7, 8, 9, 2]
             ^---
[0, 3, 4, 1, 5, 6, 7, 8, 9, 2]
          ^---
[0, 3, 1, 4, 5, 6, 7, 8, 9, 2]
       ^---
[0, 1, 3, 4, 5, 6, 7, 8, 9, 2]
    ^---

moving 2:
[0, 1, 3, 4, 5, 6, 7, 8, 2, 9]
                         ^---
[0, 1, 3, 4, 5, 6, 7, 2, 8, 9]
                      ^---
[0, 1, 3, 4, 5, 6, 2, 7, 8, 9]
                   ^---
[0, 1, 3, 4, 5, 2, 6, 7, 8, 9]
                ^---
[0, 1, 3, 4, 2, 5, 6, 7, 8, 9]
             ^---
[0, 1, 3, 2, 4, 5, 6, 7, 8, 9]
          ^---
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
       ^---
0 голосов
/ 13 сентября 2018

В отличие от пузырьковой сортировки, сортировка вставками не просто меняет числа (концептуально).

Сначала она сохраняет значение с текущим индексом j в переменной key.

Затемон начинается только с предыдущего индекса i текущего индекса (i = j - 1) и движется назад (i = i - 1) к началу.Для каждого индекса он сравнивает значение с key (while i >= 0 and A[i] > key).Если значение в i больше key, оно сдвигает значение на один индекс вперед (A[i + 1] = A[i]), пока не найдет значение, равное или меньшее, чем key.Когда такое значение найдено, key должно следовать сразу после этого в отсортированном массиве, поэтому он помещает key в следующий индекс i+1 (A[i + 1] = key).Он повторяет один и тот же процесс для всех элементов и в результате сортируется массив.

Это поможет больше https://visualgo.net/bn/sorting?slide=8.

...