Алгоритм сортування вибору з Python Code Приклад

Що таке сортування вибору?

ВИБІР СОРТ це порівняльний алгоритм сортування, який використовується для сортування випадкового списку елементів у порядку зростання. Порівняння не вимагає багато додаткового місця. Це вимагає лише одного додаткового простору пам’яті для тимчасової змінної.

Це відомо як на місці сортування. Сортування вибору має часову складність O(n²), де n – загальна кількість елементів у списку. Часова складність вимірює кількість ітерацій, необхідних для сортування списку. Список поділено на дві частини: перша частина містить відсортовані елементи, а друга містить невідсортовані елементи.

За замовчуванням відсортований список порожній, а невідсортований список містить усі елементи. Невідсортований список потім сканується на мінімальне значення, яке потім поміщається в відсортований список. Цей процес повторюється, доки всі значення не будуть порівняні та відсортовані.

Як працює вибіркове сортування?

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

Приклад

• Наприклад, якщо індекс мінімального значення дорівнює 3, тоді значення елемента з індексом 3 розміщується в індексі 0, тоді як значення, яке було в індексі 0, розміщується в індексі 3. Якщо перший елемент у невідсортованому розділі є мінімальне значення, потім він повертає свої позиції.
• Елемент, який було визначено як мінімальне значення, потім переміщується до розділу ліворуч, який є відсортованим списком.
• Розділена сторона тепер має один елемент, тоді як нерозділена сторона має (n – 1) елементів, де n – загальна кількість елементів у списку. Цей процес повторюється знову і знову, доки всі елементи не будуть порівняні та відсортовані на основі їхніх значень.

Визначення проблеми

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

[21,6,9,33,3]

Наведений вище список слід відсортувати, щоб отримати наступні результати

[3,6,9,21,33]

Рішення (Алгоритм)

Крок 1) Отримайте значення n, яке є загальним розміром масиву

Крок 2) Розбийте список на відсортовані та невідсортовані розділи. Відсортований розділ спочатку порожній, тоді як невідсортований розділ містить увесь список

Крок 3) Виберіть мінімальне значення з нерозділеного розділу та помістіть його в відсортований розділ.

Крок 4) Повторюйте процес (n – 1) разів, доки всі елементи в списку не будуть відсортовані.

Візуальне уявлення

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

На наступному зображенні показано несортований список

Крок 1)

Перше значення 21 порівнюється з рештою значень, щоб перевірити, чи є воно мінімальним значенням.

3 є мінімальним значенням, тому позиції 21 і 3 поміняні місцями. Значення із зеленим фоном представляють відсортований розділ списку.

Крок 2)

Значення 6, яке є першим елементом у несортованому розділі, порівнюється з рештою значень, щоб дізнатися, чи існує нижче значення

Значення 6 є мінімальним значенням, тому воно зберігає свою позицію.

Крок 3)

Перший елемент невідсортованого списку зі значенням 9 порівнюється з рештою значень, щоб перевірити, чи є це мінімальним значенням.

Значення 9 є мінімальним значенням, тому воно зберігає свою позицію в сортованому розділі.

Крок 4)

Значення 33 порівнюється з рештою значень.

Значення 21 менше за 33, тому позиції міняються місцями, щоб отримати наведений вище новий список.

Крок 5)

У нас залишилося лише одне значення в нерозділеному списку. Тому вже розсортовано.

Остаточний список схожий на той, що показаний на зображенні вище.

Використання програми сортування вибору Python 3

Наступний код показує реалізацію сортування вибору за допомогою Python 3

def selectionSort( itemsList ):
    n = len( itemsList )
    for i in range( n - 1 ):
        minValueIndex = i

        for j in range( i + 1, n ):
            if itemsList[j] < itemsList[minValueIndex] :
                minValueIndex = j

        if minValueIndex != i :
            temp = itemsList[i]
            itemsList[i] = itemsList[minValueIndex]
            itemsList[minValueIndex] = temp

    return itemsList


el = [21,6,9,33,3]

print(selectionSort(el))

Виконання наведеного вище коду дає такі результати

[3, 6, 9, 21, 33]

Code Пояснення

Пояснення до коду таке

Ось Code пояснення:

1. Визначає функцію з назвою selectionSort
2. Отримує загальну кількість елементів у списку. Це нам потрібно, щоб визначити кількість проходів, які потрібно зробити під час порівняння значень.
3. Зовнішня петля. Використовує цикл для перебору значень списку. Кількість ітерацій дорівнює (n – 1). Значення n дорівнює 5, тому (5 – 1) дає нам 4. Це означає, що зовнішні ітерації будуть виконані 4 рази. У кожній ітерації значення змінної i присвоюється змінній minValueIndex
4. Внутрішня петля. Використовує цикл для порівняння крайнього лівого значення з іншими значеннями в правій частині. Однак значення j не починається з індексу 0. Воно починається з (i + 1). Це виключає значення, які вже відсортовано, тому ми зосереджуємося на елементах, які ще не відсортовано.
5. Знаходить мінімальне значення в несортованому списку та розміщує його на належному місці
6. Оновлює значення minValueIndex під час заміниping умова вірна
7. Порівнює значення індексів minValueIndex та i, щоб побачити, чи вони не рівні
8. Крайнє ліве значення зберігається в часовій змінній
9. Нижнє значення з правого боку займає першу позицію
10. Значення, яке було збережено в часовому значенні, зберігається в позиції, яку раніше займало мінімальне значення
11. Повертає відсортований список як результат функції
12. Створює список el із випадковими числами
13. Надрукувати відсортований список після виклику функції сортування вибору, передаючи el як параметр.

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

Складність сортування використовується для вираження кількості разів виконання, необхідних для сортування списку. Реалізація має два цикли.

Зовнішній цикл, який вибирає значення одне за одним зі списку, виконується n разів, де n — загальна кількість значень у списку.

Внутрішній цикл, який порівнює значення із зовнішнього циклу з рештою значень, також виконується n разів, де n — загальна кількість елементів у списку.

Отже, кількість виконань дорівнює (n * n), що також можна виразити як O(n²).

Сортування вибору має три категорії складності, а саме;

• Найгірший випадок – тут представлений список у порядку спадання. Алгоритм виконує максимальну кількість виконань, яка виражається як [Big-O] O(n²)
• Найкращий випадок – це відбувається, коли наданий список вже відсортовано. Алгоритм виконує мінімальну кількість виконань, яка виражається як [Big-Omega] Ω(n²)
• Середній випадок – це відбувається, коли список розташований у випадковому порядку. Середня складність виражається як [Big-theta] Θ(n²)

Сортування вибором має просторову складність O(1), оскільки воно вимагає однієї часової змінної, яка використовується для обміну.ping значень.

Коли використовувати сортування вибором?

Сортування вибору найкраще використовувати, коли потрібно:

• Ви повинні відсортувати невеликий список елементів у порядку зростання
• Коли вартість обмінуping значення незначні
• Він також використовується, коли потрібно переконатися, що всі значення в списку перевірено.

Переваги Selection Sort

Нижче перераховані переваги селекційного сорту

• Він дуже добре працює на невеликих списках
• Це алгоритм на місці. Для сортування не потрібно багато місця. Для зберігання тимчасової змінної потрібен лише один додатковий простір.
• Він добре працює з елементами, які вже були відсортовані.

Недоліки Selection Sort

Нижче наведено недоліки селекційного сортування.

• Він погано працює під час роботи з великими списками.
• Кількість ітерацій, зроблених під час сортування, дорівнює n-квадрату, де n – загальна кількість елементів у списку.
• Інші алгоритми, такі як швидке сортування, мають кращу продуктивність порівняно з сортуванням вибору.

Поширені запитання