Сортировка вставками?

Question

[qw1klyy]

является ли мой код реализацией алгоритма сортировки Вставками?

k=[2,3,3,4,1,50,5]
f = 1
for i in range(1, len(k)):
    m = k[i]
    n = k[i-1]
    f = 1
    if m>=n:
        continue
    for j in range(i-2, -1, -1):
        if m > k[j]:
            del k[i]
            k.insert(j+1, m)
            f = 0
            break
    if f == 1:
        y = k[i]
        del k[i]
        k.insert(0, y)

Работает нормально, сортирует список как положено

Answer 1

[0xC0000005]

Можно проще:

def sort_insertion(array: list) -> list:
    for i in range(1, len(array)):
        x = array[i]

        j = i

        while j > 0 and array[j - 1] > x:
            array[j] = array[j - 1]

            j -= 1

        array[j] = x

    return array

sort_insertion([2, 3, 3, 4, 1, 50, 5]) # => [1, 2, 3, 3, 4, 5, 50]

Первый вариант: 7600 наносекунд
Второй вариант (sort_insertion): 5200 наносекунд (т.е быстрее на 32%)

Comments

[qw1klyy]

скорость та же?

[0xC0000005]

qw1klyy, обновил

[0xC0000005]

qw1klyy, можете сами проверить:

t = perf_counter_ns()

k=[2,3,3,4,1,50,5]
f = 1
for i in range(1, len(k)):
    m = k[i]
    n = k[i-1]
    f = 1
    if m>=n:
        continue
    for j in range(i-2, -1, -1):
        if m > k[j]:
            del k[i]
            k.insert(j+1, m)
            f = 0
            break
    if f == 1:
        y = k[i]
        del k[i]
        k.insert(0, y)

print(perf_counter_ns() - t)

t = perf_counter_ns()

sort_insertion([2, 3, 3, 4, 1, 50, 5]) # => [1, 2, 3, 3, 4, 5, 50]

print(perf_counter_ns() - t)