Сортировка массива методом вставки на Python

В данной статье мы рассмотрим сортировку методом вставки, реализованную на языке Python.

Еще статья: Сортировка массива методом пузырька на Python
Еще статья: Сортировка массива методом выбора на Python


Описание алгоритма:

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

Суть сортировки:

1. Перебираются элементы в неотсортированной части массива.

2. Каждый элемент вставляется в отсортированную часть массива на то место, где он должен находиться.

 # Функция сортировки массива методом вставки

def sort_insertion(massiv):

    

    for i in range(1, len(massiv)):

        

        tmp = massiv[i]

        j = i

        while j > 0 and massiv[j - 1]  < tmp:

            massiv[j] = massiv[j - 1]

            j -= 1

        massiv[j] = tmp

                   

    # Возвращаем отсортированный массив

    return massiv

# Тестируем

def test():

    print("Tест1",sort_insertion([10,7,4,1,2,5,3,9,6,8]))

    print("Tест2",sort_insertion([1,4,7,10,2,5,8,3,6,9]))

    print("Tест3",sort_insertion([1,3,5,7,9,10,8,6,4,2]))

# Запуск программы

test()

               

Результат работы программы.

Исходник программы:

Cкачать из Облака

Еще алгоритмы тут: Алгоритмы.