Сортування включенням

Сортування включенням (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)

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

Дивіться також: