Сортування обміном (бульбашкою) і вибором
Навіщо сортувати
Впорядкований масив швидше шукати (бінарний пошук), легше аналізувати, зручніше читати. Існує десятки алгоритмів; почнемо з найпростіших.
Сортування обміном («бульбашка»)
Ідея. Порівнюємо сусідні елементи; якщо порядок неправильний — міняємо місцями. Після першого проходу найбільший елемент «спливає» в кінець.
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 завжди | мало | не залежить від початкового порядку |
Дивіться, як працюють обидва алгоритми, в лабораторії «Сортування» нижче: вона показує кожен крок.
Перевірте себе
Який елемент займає своє місце після першого проходу «бульбашки»?
Скільки обмінів у сортуванні вибором максимум?
Для чого змінна
swapped?
BitMath · https://www.bitmath.com.ua/informatyka/informatyka-9-tema-7/i9-vporiadkuvannia-1