Сортування - це основна операція, в якій елементи масиву розташовані в певному порядку, щоб підвищити можливість пошуку. Простими словами, дані сортуються так, щоб їх можна було легко шукати.
Діаграма порівняння
| Основа для порівняння | Сортування вставки | Сортування вибору |
|---|---|---|
| Основний | Дані сортуються, вставляючи дані в існуючий відсортований файл. | Дані сортуються шляхом вибору та розміщення послідовних елементів у відсортованому місці. |
| Природа | Стабільний | Нестабільний |
| Процес, який слід дотримуватися | Елементи відомі заздалегідь, поки шукається місце їх розташування. | Розташування раніше відомо, в той час як елементи шукаються. |
| Негайні дані | Вставка сортування - це техніка сортування, яка може працювати з негайними даними. | Вона не може мати справу з безпосередніми даними, вона повинна бути присутнім на початку. |
| Краща складність справи | O (n) | O (n 2 ) |
Визначення сортування вставки
Вставка сортування працює, вставляючи набір значень у існуючий відсортований файл. Він створює сортований масив, вставляючи один елемент за один раз. Цей процес триває до тих пір, поки весь масив не буде відсортовано в певному порядку. Основною концепцією сортування вставки є вставлення кожного елемента у відповідне місце у кінцевому списку. Метод сортування вставки зберігає ефективну кількість пам'яті.
Робота сортування Insertion
- Він використовує два набори масивів, в яких зберігаються відсортовані дані та інші на несортовані дані.
- Алгоритм сортування працює до тих пір, поки не буде знайдено елементів у несортированном наборі.
- Припустимо, що в масиві є елементи 'n'. Спочатку елемент з індексом 0 (LB = 0) існує в відсортованому наборі. Залишилися елементи знаходяться в несортированном розділі списку.
- Перший елемент несортированной частини має індекс масиву 1 (якщо LB = 0).
- Після кожної ітерації він вибирає перший елемент несортированного розділу і вставляє його в потрібне місце в відсортованому наборі.
Переваги сортування Insertion
- Легко реалізований і дуже ефективний при використанні невеликих наборів даних.
- Додаткова потреба у вільному просторі пам'яті від сортування менше (тобто O (1)).
- Це вважається технікою сортування в реальному часі, оскільки список може бути відсортований, як отримані нові елементи.
- Це швидше, ніж інші алгоритми сортування.
Приклад:
Визначення сортування вибору
Виділення сортування здійснюється сортуванням шляхом пошуку мінімального значення та розміщення його у першій або останній позиції відповідно до порядку (за зростанням або спаданням). Процес пошуку мінімального ключа і розміщення його в належному положенні продовжується, поки всі елементи не будуть розміщені в правильному положенні.
Робота сортування вибору
- Припустимо масив ARR з N елементами в пам'яті.
- При першому проході найменший ключ шукається разом з його положенням, після чого ARR [POS] міняється місцями з ARR [0]. Отже, ARR [0] сортується.
- У другому проході знову визначається положення найменшого значення в подмассиве елементів N-1. Обміняйте ARR [POS] з ARR [1].
- У проході N-1 виконується той самий процес для сортування N числа елементів.
Приклад:
Ключові відмінності між сортуванням сортування та сортуванням вибору
- Сортування вставки зазвичай виконує операцію вставки. Навпаки, вибір сортування здійснює вибір і позиціонування необхідних елементів.
- Сорт вставки вважається стабільним, а сортування не є стабільним алгоритмом.
- У алгоритмі сортування вставок відомі раніше елементи. На відміну від цього, сортування вибору містить попереднє розташування.
- Сортування вставки є технікою сортування в реальному часі, де приходять елементи відразу сортуються в списку, тоді як сортування вибору не може добре працювати з негайними даними.
- У найкращому випадку сортування вставки має час O (n). На відміну від кращого випадку виконання вибіркової складності сортування вибору є O (n2).
Складність сортування вставки
Найкраща складність випадку сортування вставки - це O (n) разів, тобто коли раніше масив сортувався. Так само, коли масив сортується в зворотному порядку, перший елемент несортированного масиву слід порівнювати з кожним елементом у відсортованому наборі. Отже, у найгіршому випадку час роботи сортування вставки є квадратичним, тобто O (n2) . У середньому випадку також необхідно зробити мінімальне (k-1) / 2 порівняння. Отже, середній випадок також має квадратичне час виконання O (n2).
Складність сортування сортування
Як робота відбору, сортування не залежить від початкового порядку елементів в масиві, тому не існує великої різниці між найкращим і найгіршим випадком вибору сортування.
Виділення сортування вибирає елемент мінімального значення, у процесі вибору сканується все 'n' кількість елементів; тому n-1 порівняння зроблено в першому проході. Потім елементи змінюються. Аналогічно і в другому проході, щоб знайти другий найменший елемент, який вимагає сканування інших n-1 елементів, і процес продовжується до впорядкування всього масиву.
Таким чином, складність вибіркового сортування є O (n2) .
= (n-1) + (n-2) + ……… .. + 2 + 1
= n (n-1) / 2 = O (n2)
Висновок
Серед алгоритму сортування, сортування вставки є швидким, ефективним, стабільним, в той час як сортування вибору працює ефективно тільки тоді, коли задіяний невеликий набір елементів, або список частково попередньо відсортований. Кількість порівнянь, виконаних за допомогою сортування вибору, більше, ніж переміщення, що виконуються, тоді як при сортуванні вставки кількість разів переміщення або заміни елемента більше, ніж зроблені порівняння.
