З відповідями ← До сторінки

Сортування обміном (бульбашкою) і вибором

Підказка

Що вивчимо. Два прості алгоритми сортування: обмін («бульбашка») та вибір.

Навіщо сортувати

Впорядкований масив швидше шукати (бінарний пошук), легше аналізувати, зручніше читати. Існує десятки алгоритмів; почнемо з найпростіших.

Сортування обміном («бульбашка»)

Ідея. Порівнюємо сусідні елементи; якщо порядок неправильний — міняємо місцями. Після першого проходу найбільший елемент «спливає» в кінець.

def bubble_sort(a):
    n = len(a)
    for p in range(n - 1):
        swapped = False
        for i in range(n - 1 - p):
            if a[i] > a[i + 1]:
                a[i], a[i + 1] = a[i + 1], a[i]
                swapped = True
        if not swapped:      # обмінів не було — вже відсортовано
            break

a = [5, 2, 9, 1, 7]
bubble_sort(a)
print(a)      # [1, 2, 5, 7, 9]

Покроково для [5, 2, 9, 1]:

Прохід

Масив

початок

5 2 9 1

1

2 5 1 9

2

2 1 5 9

3

1 2 5 9

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

Ідея. Знаходимо найменший елемент і ставимо його на перше місце; потім — найменший із решти на друге тощо.

def selection_sort(a):
    n = len(a)
    for i in range(n - 1):
        imin = i
        for j in range(i + 1, n):
            if a[j] < a[imin]:
                imin = j
        a[i], a[imin] = a[imin], a[i]

Обмінів небагато (не більше n − 1), але порівнянь завжди приблизно n²/2.

Порівняння

Алгоритм

Порівнянь

Обмінів

Що важливо

Обмін

до n²/2

багато

можна зупинитися раніше

Вибір

n²/2 завжди

мало

не залежить від початкового порядку

Дивіться, як працюють обидва алгоритми, в лабораторії «Сортування» нижче: вона показує кожен крок.

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

  1. Який елемент займає своє місце після першого проходу «бульбашки»?

  2. Скільки обмінів у сортуванні вибором максимум?

  3. Для чого змінна swapped?

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