Алгоритми сортування

1 Навіщо сортувати дані?

Ми вже знаємо, що бінарний пошук працює лише у відсортованих списках. Але сортування потрібне всюди: від списку контактів у телефоні до рейтингу гравців у грі або сортування товарів за ціною в інтернет-магазині.

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

Це один із найпростіших алгоритмів. Ідея така: ми порівнюємо сусідні елементи, і якщо вони стоять у неправильному порядку — міняємо їх місцями. Найбільші елементи поступово "спливають" у кінець списку, як бульбашки повітря у воді.

def bubble_sort(nums):
    n = len(nums)
    for i in range(n):
        for j in range(0, n - i - 1):
            if nums[j] > nums[j + 1]:
                # Міняємо місцями
                nums[j], nums[j + 1] = nums[j + 1], nums[j]

numbers = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(numbers)
print(numbers)  # [11, 12, 22, 25, 34, 64, 90]

3 Алгоритм "Камінця" (Selection Sort)

Якщо у "бульбашці" легкі елементи поступово піднімаються вгору, то в алгоритмі камінця (або сортуванні вибором) ми шукаємо "найважчий" камінець (максимум) і одразу переносимо його в самий кінець. Або шукаємо "найлегший" (мінімум) і ставимо на початок.

def stone_sort(nums):
    n = len(nums)
    for i in range(n):
        # Шукаємо індекс мінімального елемента в залишку списку
        min_idx = i
        for j in range(i + 1, n):
            if nums[j] < nums[min_idx]:
                min_idx = j
        
        # Ставимо знайдений мінімум на його місце (одна заміна за прохід)
        nums[i], nums[min_idx] = nums[min_idx], nums[i]

numbers = [22, 11, 90, 64, 34]
stone_sort(numbers)
print(numbers) # [11, 22, 34, 64, 90]

4 Різниця: Бульбашка vs Камінець

5 Вбудовані методи Python

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

nums = [5, 2, 8]
nums.sort()
print(nums)  # [2, 5, 8]

nums = [5, 2, 8]
new_nums = sorted(nums)
print(nums)      # [5, 2, 8]
print(new_nums)  # [2, 5, 8]

4 Сортування у зворотному порядку

Щоб відсортувати список від більшого до меншого, використовуйте параметр reverse=True:

nums = [10, 50, 20, 40]
nums.sort(reverse=True)
print(nums)  # [50, 40, 20, 10]

# Або з функцією sorted
res = sorted(nums, reverse=True)