В чем проблема в сортировке вставками с барьером?

Question

Есть задание отсортировать одномерный массив сортировкой вставками с барьером. Во многих книжках код для нее один и тот же. Я просто переписал его на python. Но в результате выходит чушь какая-то. В чем проблема и как решить? Сама сортировка находится почти в конце кода, если кому лень искать. Также еще прикрепил пример работы проги. Он элемент с индексом 0 теряет, а с индексом n-1 дублирует.

import random


def _print(a, n):
    for i in range(n):
        print(a[i], end="  |  ")
    print()


def _fill(a, n):
    a = [round(random.triangular(-9, 9, 0), 2) for i in range(n)]
    a[random.randint(0, n)] = 0
    return a


def main():
    while True:
        n = int(input('Введите количество элементов массива n: '))
        if n > 2:
            break

    a = [0] * n
    last_zero = 0
    summa = 0

    # print('Введите элементы массива: ')

    a = _fill(a, n)

    for i in range(0, n):
        if a[i] >= 0:
            summa += 1
        if a[i] == int(0):
            last_zero = i

    print('\n\nОдномерный массив: ')
    _print(a, n)
    print('\nКоличество положительных элементов: %d' % summa)
    summa = 0

    for i in range(last_zero, n):
        summa += a[i]

    print('Сумма элементов после крайнего справа 0: %.2f' % summa)

    for i in range(n-1):
        for j in range(i, n):
            i_min = i
            if abs(a[i]) >= 1:
                i_min = j
            tmp = a[i]
            a[i] = a[i_min]
            a[i_min] = tmp

    print('\n\nМассив, преобразованный в соотвествии с п.2: ')
    _print(a, n)

    # Сортировка вставками с барьером!!!!!!!
    for i in range(2, n):
        if a[i - 1] > a[i]:
            a[0] = a[i]
            j = i - 1
            while a[j] > a[0]:
                a[j + 1] = a[j]
                j = j - 1
            a[j + 1] = a[0]

    print('\n\nСортировка вставками с барьером: ')
    _print(a, n)


if __name__ == "__main__":
    main()

Answer 1

Ну, смотрите, как описан алгоритм - массив объявляется с дополнительным нулевым элементом, куда складывается минимальный, чтобы цикл по j всегда остановился на нем.

Если дословно переводить из паскаля, можно сдвинуть весь список, первый вариант

a = [0] + a

for i in range(2, len(a)):
    if a[i - 1] > a[i]:
        a[0] = a[i]
        j = i - 1
        while a[j] > a[0]:
            a[j + 1] = a[j]
            j = j - 1
        a[j + 1] = a[0]

a = a[1:]
print(a)

или из-за того, что элемент с индексом -1 - это последний элемент массива, добавить дополнительный элемент в конец

a = a + [0]
for i in range(1, len(a)):
    if a[i - 1] > a[i]:
        a[-1] = a[i]
        j = i - 1
        while a[j] > a[-1]:
            a[j + 1] = a[j]
            j = j - 1
        a[j + 1] = a[-1]

print(a[:-1])

Похоже, что оба работающие, но это не очень по питоновски. Вам стоит подумать, как сделать сдвиг массива срезами

БЛОГ НА HUSL

В чем проблема в сортировке вставками с барьером?

Ответы (1 шт):