Без відповідей (роздатка учню) ← До сторінки

Сортування вставками та вбудоване sorted у Python

Підказка

Що вивчимо. Сортування вставками, порівняння алгоритмів і вбудовані засоби 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 разів більше.

Приклад

Таблицю учнів сортуємо за прізвищем, а потім стабільним сортуванням за класом: учні всередині класу залишаються за алфавітом.

Перевірте себе

  1. З чим порівнюють сортування вставками?

  2. Що означає «стабільне сортування»?

  3. Як відсортувати слова за довжиною?

BitMath · https://www.bitmath.com.ua/informatyka/informatyka-9-tema-7/i9-vporiadkuvannia-2