5 алгоритмів сортування на Python, які вам треба знати

25.03.21 ⏰4 хв

Програмування не так вимагає знань математики, хоч цим налякані початківці, як от справжнім викликом для молодого розробника з часом стають алгоритми. Про них створено багато жартів, намальовано безліч мемів, в їх честь пролито багато сліз (гіпербола).

Сортування — навичка потрібна не тільки для успішного проходження співбесід, але і для розуміння дисципліни в цілому. Алгоритми сортування демонструють як внутрішня логіка може впливати на складність, швидкість та ефективність програми.

Розберемо 5 найпоширеніших базових алгоритмів та реалізуємо їх за допомогою Python.

Bubble Sort (сортування бульбашкою)

Цей вид сортування вивчають на початку знайомства з дисципліною Computer Science, оскільки він максимально просто демонструє саму концепцію сортування.

Цей підхід полягає у тому, що перебір здійснюється за списком і з порівнянням сусідніх елементів. Вони міняються місцями в тому випадку, якщо порядок неправильний. І так триває до тих пір, поки всі елементи не розташуються в потрібному порядку. У бульбашкового сортування складність в гіршому випадку - O (n ^ 2), через велику кількість повторень.

Selection Sort (сортування вибором)

Сортування вибором також доволі простий алгоритм, але більш ефективний у порівнянні з бульбашковим сортуванням.

У цьому алгоритмі список (або масив) ділиться на дві частини: список з відсортованими елементами та список з елементами, які потрібно відсортувати. Спочатку шукається найменший елемент у другому списку. Він додається в кінець першого. Таким чином алгоритм поступово формує список від меншого до більшого. Так відбувається до тих пір, поки не буде готовий відсортований масив.

Insertion Sort (сортування вставками)

Сортування вставками швидке і просте. На кожній ітерації програма бере один з елементів і підшукує для нього місце у вже відсортованому списку. Так відбувається до тих пір, поки не залишиться жодного невикористаного елемента.

Merge Sort (сортування злиттям)

Сортування злиттям складається з двох етапів:

1. Невідсортований список послідовно ділиться на N списків, де кожен включає один «невідсортований» елемент, а N — це число елементів в оригінальному масиві.
2. Списки послідовно зливаються групами по два, створюючи нові відсортовані списки до тих пір, поки не з'явиться один фінальний відсортований список.

Quick Sort (швидке сортування)

Алгоритм трохи складніший, але в стандартних реалізаціях він працює швидше, ніж сортування злиттям, а його складність в гіршому випадку рідко досягає O (n ^ 2).

Це сортування складається з трьох етапів:

1. Вибирається один опорний елемент.
2. Всі елементи, які менші за опорний, переміщаються зліва від нього, інші — направо. Це називається операцією розбиття.
3. Рекурсивно 2 попередні кроки повторюються в кожному новому списку, де нові опорні елементи будуть менші та більші за опорний елемент.