Сортування вставками та вбудоване sorted у Python
Сортування вставками
Ідея. Так сортують карти в руці: беремо наступну карту й вставляємо її на потрібне місце серед уже впорядкованих.
def insertion_sort(a):
for i in range(1, len(a)):
key = a[i]
j = i - 1
while j >= 0 and a[j] > key:
a[j + 1] = a[j]
j -= 1
a[j + 1] = key
a = [7, 3, 5, 1]
insertion_sort(a)
print(a) # [1, 3, 5, 7]Якщо масив майже впорядкований — працює дуже швидко.
Вбудоване сортування
a = [5, 2, 9]
a.sort() # на місці
b = sorted(a, reverse=True) # новий список за спаданням
words = sorted(["вишня", "яблуко", "банан"], key=len)sorted і sort використовують алгоритм Timsort — значно швидший за наші прості алгоритми. У школі ми пишемо власні, щоб зрозуміти ідею, а в роботі користуємося вбудованими.
Порівняння алгоритмів
Алгоритм | Гірший випадок | Майже впорядкований | Стабільність |
|---|---|---|---|
Обмін | n² | швидко (з ознакою) | так |
Вибір | n² | n² | ні |
Вставки | n² | швидко | так |
Вбудоване | n log n | швидко | так |
Стабільне сортування зберігає порядок рівних елементів: учні з однаковими балами лишаються в алфавітному порядку.
Експеримент
Запустіть лабораторію «Складність алгоритмів» нижче: порівняйте кількість операцій для масивів розміром 10, 100, 1000. Зростає n у 10 разів — операцій n² стає у 100 разів більше.
Перевірте себе
З чим порівнюють сортування вставками?
Що означає «стабільне сортування»?
Як відсортувати слова за довжиною?