Сортування вибору: алгоритм пояснюється за допомогою Python Приклад коду

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

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

Це відомо як на місці сортування. Сортування вибору має часову складність 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]

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

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

Ось пояснення коду:

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

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

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

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

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

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

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

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

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

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

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

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

Переваги Selection Sort

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

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

Недоліки Selection Sort

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

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

Підсумки

Сортування вибором — це алгоритм порівняння на місці, який використовується для сортування випадкового списку в упорядкований список. Він має часову складність O(n²)
Список поділено на два розділи: відсортований і невідсортований. Мінімальне значення вибирається з невідсортованого розділу та поміщається в відсортований розділ.
Це повторюється, доки всі елементи не будуть відсортовані.
Реалізація псевдокоду в Python 3 передбачає використання двох циклів for і if для перевірки необхідності заміни
Часова складність вимірює кількість кроків, необхідних для сортування списку.
Найгірша часова складність виникає, коли список у порядку спадання. Він має часову складність [Big-O] O(n²)
У найкращому випадку часова складність виникає, коли список уже в порядку зростання. Він має часову складність [Big-Omega] ?(n²)
Середня часова складність виникає, коли список у випадковому порядку. Він має часову складність [Big-theta] ?(n²)
Сортування за вибором найкраще використовувати, коли у вас є невеликий список елементів для сортування, вартість заміни значень не має значення, а перевірка всіх значень є обов’язковою.
Сортування вибору погано працює у великих списках
Інші алгоритми сортування, такі як швидке сортування, мають кращу продуктивність порівняно з сортуванням за вибором.

Вам може сподобатися: