Сортування вибором і вставками: порівняння алгоритмів

Стрілки або пробіл — перемикання · F — повний екран · T — проєкторна тема · ? — підказка

Сортування вибором

Знаходимо мінімум у необробленій частині й ставимо його на початок.

a = [5, 2, 4, 1]
for i in range(len(a) - 1):
    imin = i
    for j in range(i + 1, len(a)):
        if a[j] < a[imin]:
            imin = j
    a[i], a[imin] = a[imin], a[i]

Крок

Список

i = 0

[1, 2, 4, 5]

i = 1

[1, 2, 4, 5]

Обмінів небагато — не більше n−1.

Сортування вставками

Беремо наступний елемент і вставляємо на правильне місце серед уже впорядкованих, як карти в руці.

a = [5, 2, 4, 1]
for i in range(1, len(a)):
    x = a[i]
    j = i - 1
    while j >= 0 and a[j] > x:
        a[j + 1] = a[j]
        j -= 1
    a[j + 1] = x

Для майже впорядкованих списків працює дуже швидко.

Порівняння

Метод

Ідея

Особливість

Бульбашка

обмін сусідніх

багато обмінів

Вибір

пошук мінімуму

мало обмінів

Вставки

вставка в упорядковану частину

швидкий для майже впорядкованих

Усі три роблять порядку n² операцій для n елементів.

Вбудоване сортування

a.sort()                        # змінює список
b = sorted(a, reverse=True)     # новий список за спаданням

На практиці використовують вбудоване — воно значно швидше (O(n log n)).

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

  1. Яка основна ідея сортування вибором?

  2. Який метод найкраще працює для майже впорядкованого списку?

  3. Чим sort() відрізняється від sorted()?

✕ Вийти 1 / 1