Іншою істотною відмінністю між ними є те, що сортування міхура є стабільним алгоритмом, а сортування вибору є нестабільним алгоритмом. Алгоритм вважається стійким елементам з тим же ключем, що відбуваються в тому ж порядку, в якому вони відбувалися перед сортуванням у списку або масиві. Як правило, найбільш стабільні і швидкі алгоритми використовують додаткову пам'ять.
Діаграма порівняння
| Основа для порівняння | Сортування бульбашок | Виділення сортування |
|---|---|---|
| Основний | Суміжний елемент порівнюється і міняється місцями | Найбільший елемент вибирається і міняється місцями з останнім елементом (у випадку зростання порядку). |
| Найкращий час складності | O (n) | O (n 2 ) |
| Ефективність | Неефективно | Покращена ефективність порівняно з сортуванням міхура |
| Стабільний | Так | Ні |
| Метод | Обмін | Вибір |
| Швидкість | Повільно | Швидкий у порівнянні з сортом міхура |
Визначення сортування міхура
Сортування бульбашок є найпростішим ітераційним алгоритмом, який діє шляхом порівняння кожного елемента або елемента з елементом, розташованим поруч з ним, і, за потреби, міняє їх. Простими словами, він порівнює перший і другий елемент списку і заміняє його, якщо вони не знаходяться поза певним порядком. Аналогічно, другий та третій елементи порівнюються та обмінюються місцями, і це порівняння та обмін переходять до кінця списку. Кількість порівнянь в першій ітерації n-1, де n - числові елементи в масиві. Найбільший елемент буде на n-й позиції після першої ітерації. І після кожної ітерації кількість порівнянь зменшується, а на останній ітерації має місце лише одне порівняння.
Цей алгоритм є найповільнішим алгоритмом сортування. Найкраща складність випадку (коли список в порядку) сортування Bubble має порядок n ( O (n) ), а найгірша - O (n2) . У кращому випадку, це має порядок n, тому що він просто порівнює елементи і не міняє їх. Цей метод також вимагає додаткового простору для зберігання тимчасової змінної.
Визначення сортування вибору
Виділення сортування досягло трохи кращої продуктивності і є ефективним, ніж алгоритм сортування міхура. Припустимо, що ми хочемо організувати масив у порядку зростання, тоді він функціонує, знайшовши найбільший елемент і обміняючи його з останнім елементом, і повторіть наступний процес на під-масивах до впорядкування всього списку.
Основні відмінності між сортуванням та сортуванням пузир
- У сорту міхура кожен елемент і його суміжний елемент порівнюються і обмінюються, якщо потрібно. З іншого боку, сортування вибору виконується шляхом вибору елемента і заміни цього елемента на останній елемент. Вибраний елемент може бути найбільшим або найменшим, залежно від порядку, тобто висхідним або низхідним.
- Найгірший випадок складності є однаковим в обох алгоритмах, тобто O (n2), але краща складність відрізняється. Сортування бульбашок займає порядок n раз, тоді як сортування вибору споживає порядок n2 часу.
- Сорт Bubble - це стабільний алгоритм, на відміну від якого сортування вибору є нестабільним.
- Алгоритм вибору сортування є швидким і ефективним порівняно з сортом міхура, який є дуже повільним і неефективним.
Висновок
Алгоритм сортування міхура вважається найпростішим і неефективним алгоритмом, але алгоритм вибору сортування є ефективним порівняно з сортуванням міхура. Bubble sort також споживає додатковий простір для зберігання тимчасової змінної і потребує більше свопів.
