Стрілки або пробіл — перемикання · F — повний екран · T — проєкторна тема · ? — підказка
Впорядковані дані легше шукати (бінарний пошук), порівнювати й аналізувати. Тому сортування — одна з базових задач програмування.
Бульбашкове сортування. Проходимо масивом, порівнюємо сусідні елементи та міняємо їх, якщо вони стоять неправильно. Після кожного проходу найбільший з невпорядкованих елементів «спливає» в кінець.
Сортування вибором. Знаходимо найменший елемент у невпорядкованій частині й ставимо його на першу позицію цієї частини.
Сортування вставками. Беремо наступний елемент і вставляємо його у відповідне місце вже впорядкованої частини. Добре працює, коли масив майже впорядкований.
Обираємо опорний елемент, ділимо масив на частину з меншими й частину з більшими елементами та сортуємо їх рекурсивно. У середньому виконує порядку nlogn порівнянь.
Алгоритм | У гіршому випадку | Основна ідея |
|---|---|---|
Бульбашка | O(n2) | обмін сусідніх |
Вибір | O(n2) | пошук мінімуму |
Вставки | O(n2) | вставка в упорядковану частину |
Швидке | O(n2), у середньому O(nlogn) | поділ навколо опорного |
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