Алгоритми сортування: бульбашка, вибір, вставки та швидке
Що таке сортування
Впорядковані дані легше шукати (бінарний пошук), порівнювати й аналізувати. Тому сортування — одна з базових задач програмування.
Прості алгоритми
Бульбашкове сортування. Проходимо масивом, порівнюємо сусідні елементи та міняємо їх, якщо вони стоять неправильно. Після кожного проходу найбільший з невпорядкованих елементів «спливає» в кінець.
Сортування вибором. Знаходимо найменший елемент у невпорядкованій частині й ставимо його на першу позицію цієї частини.
Сортування вставками. Беремо наступний елемент і вставляємо його у відповідне місце вже впорядкованої частини. Добре працює, коли масив майже впорядкований.
Швидке сортування
Обираємо опорний елемент, ділимо масив на частину з меншими й частину з більшими елементами та сортуємо їх рекурсивно. У середньому виконує порядку порівнянь.
Складність
Алгоритм | У гіршому випадку | Основна ідея |
|---|---|---|
Бульбашка | обмін сусідніх | |
Вибір | пошук мінімуму | |
Вставки | вставка в упорядковану частину | |
Швидке | , у середньому | поділ навколо опорного |
Сортування в Python
numbers = [5, 2, 9, 1, 7]
numbers.sort() # змінює список
print(sorted(numbers, reverse=True)) # новий список за спаданнямВласну реалізацію бульбашки:
def bubble_sort(a):
for end in range(len(a) - 1, 0, -1):
for i in range(end):
if a[i] > a[i + 1]:
a[i], a[i + 1] = a[i + 1], a[i]
return a
BitMath · https://bitmath.com.ua/informatyka/alhorytmy/alhorytmy-sortuvannia