Изменение Bubble Sort на Insertion Sort с небольшим изменением итерации

Question

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

L = [8, 6, 7, 1, 5, 9, 4, 3, 10, 2] // 10 items
FOR I = 1 TO 9
    FOR J = 1 TO 10 - I
        IF L[J] > L[J + 1] THEN
            TEMP = L[J]
            L[J] = L[J + 1]
            L[J + 1] = TEMP
        ENDIF
    ENDFOR J
ENDFOR I
OUTPUT L

Если я изменю шаблон итерации для I и J, как в примере ниже, я преобразовал алгоритм в Insertion Sortпожалуйста?Я думаю, что да, но я удивлен, что это может быть так просто, и различные реализации, которые я видел, имеют тенденцию отличаться больше.

L = [8, 6, 7, 1, 5, 9, 4, 3, 10, 2] // 10 items
FOR I = 1 TO 9
    FOR J = 9 TO I STEP -1
        IF L[J] > L[J + 1] THEN
            TEMP = L[J]
            L[J] = L[J + 1]
            L[J + 1] = TEMP
        ENDIF
    ENDFOR J
ENDFOR I
OUTPUT L

Answer 1

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

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

На рисунке ниже показанооперация вставки сортировки.Опять же, есть две характеристики, на которые стоит обратить внимание:

1. Массив слева расположен в отсортированном порядке, но элементы не находятся в окончательном положении.
2. Элементы справа совершенно не тронуты.

Общая концепция сортировки вставкой состоит в том, что алгоритм (концептуально) делит массив на две части: отсортированная часть в начале и несортированная часть в конце.При каждом выполнении внутреннего цикла он берет первый элемент несортированной части и перемещает его влево, пока он не будет правильно расположен в отсортированной части массива.