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

Сортировка вставками (insertion sort) - это алгоритм сортировка, в котором все элементы массива просматриваются поочередно, при этом каждый элемент размещается в соответственное место среди ранее упорядоченных значений.

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

Алгоритм работы сортировки вставками заключается в следующем:

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

Реализация сортировки вставками

def insertion_sort(array): 
    length = len(array) 
    for i in range(1, length):
        key = array[i]
        j = i
        while (j - 1 >= 0) and (array[j - 1] > key):
            array[j - 1], array[j] = array[j], array[j - 1]
            j = j - 1
        array[j] = key

print("Сортировка вставками")
arr = []
length = int(input("Введите длину массива: ")) 
for i in range(0, length): 
    element = int(input("arr[" + str(i + 1) + "] = "))   
    arr.append(element)
insertion_sort(arr) 
print("Отсортированный массив: ") 
print(arr)

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

Смотрите также: