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

Зміст:

Anonim

Що таке сортування виділення?

SELECTION SORT - це алгоритм сортування порівняння, який використовується для сортування випадкового списку елементів у порядку зростання. Для порівняння не потрібно багато додаткового місця. Для часової змінної потрібен лише один додатковий простір пам’яті.

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

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

У цьому уроці з алгоритму ви дізнаєтесь:

  • Що таке сортування виділення?
  • Як працює сортування підбору?
  • Визначення проблеми
  • Рішення (алгоритм)
  • Візуальне представлення
  • Програма сортування вибору за допомогою Python 3
  • Пояснення коду
  • Складність часу відбору сорту
  • Коли використовувати сортування виділення?
  • Переваги сорту вибору
  • Недоліки сорту вибору

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

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

Приклад:

  • Наприклад, якщо індекс мінімального значення дорівнює 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 = ifor j in range( i + 1, n ):if itemsList[j] < itemsList[minValueIndex] :minValueIndex = jif minValueIndex != i :temp = itemsList[i]itemsList[i] = itemsList[minValueIndex]itemsList[minValueIndex] = tempreturn itemsListel = [21,6,9,33,3]print(selectionSort(el))

Запуск вищевказаного коду дає такі результати

[3, 6, 9, 21, 33]

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

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

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

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

Складність часу відбору сорту

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

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

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

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

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

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

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

Коли використовувати сортування виділення?

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

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

Переваги сорту вибору

Нижче наведено переваги сортування

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

Недоліки сорту вибору

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

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

Короткий зміст:

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