Перейти до змісту

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

▶ Слайди Друк / PDF

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

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

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()?

Практика

Візуалізатор алгоритмів сортування окрема сторінка

Складність алгоритмів: графіки зростання кількості операцій окрема сторінка