Сортування вибором

7.1 Визначення сортування вибором.

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

Принцип роботи:

1. Починаємо з першого елемента масиву.
2. Знаходимо найменший елемент у залишковій невідсортованій частині масиву.
3. Міняємо місцями найменший елемент і перший елемент невідсортованої частини.
4. Повторюємо процес для наступного елемента, поки не буде відсортований весь масив.

Покроковий процес

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

Часова і простірна складність сортування вибором

Часова складність:

• У найгіршому випадку: O(n^2) — відбувається, коли елементи спочатку впорядковані у зворотному порядку або випадковим чином.
• У середньому випадку: O(n^2) — відбувається для випадкового розташування елементів.
• У найкращому випадку: O(n^2) — навіть якщо масив вже відсортований, алгоритм все одно виконує ті ж самі порівняння.

Простірна складність:

O(1) — оскільки алгоритм використовує постійну кількість додаткової пам’яті (лише кілька змінних для зберігання тимчасових значень).

7.2 Реалізація алгоритму сортування вибором.

Реалізація алгоритму дуже проста

Крок 1: знаходимо мінімальний елемент серед усіх елементів і міняємо його місцями із першим.

Крок 2: знаходимо мінімальний елемент серед усіх елементів, окрім першого, і міняємо його місцями з другим

Крок 3: знаходимо мінімальний елемент серед усіх елементів, окрім першого і другого, і міняємо його місцями з третім

Реалізація на Python:

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # Знаходимо мінімальний елемент у залишковій невідсортованій частині масиву min_idx = i for j in range(i + 1, n): if arr[j] < arr[min_idx]: min_idx = j
        # Міняємо знайдений мінімальний елемент із першим елементом невідсортованої частини arr[i], arr[min_idx] = arr[min_idx], arr[i]
        
# Приклад використання:
arr = [64, 25, 12, 22, 11]
selection_sort(arr)
print("Відсортований масив:", arr)
        

1. Перший прохід (i = 0):
   1. Знаходимо мінімальний елемент (11) у невідсортованій частині масиву [64, 25, 12, 22, 11].
   2. Міняємо 11 з 64.
   3. Масив: [11, 25, 12, 22, 64]
2. Другий прохід (i = 1):
   1. Знаходимо мінімальний елемент (12) у невідсортованій частині масиву [25, 12, 22, 64].
   2. Міняємо 12 з 25.
   3. Масив: [11, 12, 25, 22, 64]
3. Третій прохід (i = 2):
   1. Знаходимо мінімальний елемент (22) у невідсортованій частині масиву [25, 22, 64].
   2. Міняємо 22 з 25.
   3. Масив: [11, 12, 22, 25, 64]
4. Четвертий прохід (i = 3):
   1. Знаходимо мінімальний елемент (25) у невідсортованій частині масиву [25, 64].
   2. Міняємо 25 з 25.
   3. Масив: [11, 12, 22, 25, 64]

Алгоритм завершується, так як всі елементи відсортовані.