Сортування вибором і вставками: порівняння алгоритмів
Сортування вибором
Знаходимо мінімум у необробленій частині й ставимо його на початок.
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 |
|
i = 1 |
|
Обмінів небагато — не більше 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)).
Перевірте себе
Яка основна ідея сортування вибором?
Який метод найкраще працює для майже впорядкованого списку?
Чим
sort()відрізняється відsorted()?
BitMath · https://bitmath.com.ua/informatyka/informatyka-8-tema-7/i8-uporiadkuvannia-2