Друга значителна разлика между двете е, че сортирането на балон е стабилен алгоритъм, докато сортирането на селекцията е нестабилен алгоритъм. Счита се, че алгоритъмът е стабилен на елементите с един и същ ключ, възникващ в същия ред, в който са се срещали преди сортиране в списъка или масива. Като цяло, повечето стабилни и бързи алгоритми използват допълнителна памет.
Сравнителна таблица
| Основа за сравнение | Балонче | Подбор сортиране |
|---|---|---|
| Основен | Съседният елемент се сравнява и сменя | Най-големият елемент е избран и заменен с последния елемент (в случай на възходящ ред). |
| Най-добрата сложност на времето | О (п) | O (n 2 ) |
| Ефективност | Неефикасен | Подобрена ефективност в сравнение с балонния вид |
| стабилен | да | Не |
| метод | Обмяна | селекция |
| скорост | Бавен | Бързо в сравнение с балонния вид |
Дефиниция на сортиране на мехурчета
Bubble сортирането е най-простият итеративен алгоритъм, който работи чрез сравняване на всеки елемент или елемент с елемента до него и размяната им, ако е необходимо. С прости думи, той сравнява първия и втория елемент от списъка и го разменя, освен ако не са извън конкретния ред. По същия начин, вторият и третият елемент се сравняват и разменят, и това сравняване и размяна преминават към края на списъка. Броят на сравненията в първата итерация е n-1, където n е числовите елементи в масив. Най-големият елемент ще бъде на n-то място след първата итерация. И след всяка итерация броят на сравненията намалява и при последната итерация се извършва само едно сравнение.
Този алгоритъм е най-бавният алгоритъм за сортиране. Най-добрата сложност на случая (Когато списъкът е в ред) на сортирането на Bubble е от порядъка n ( O (n) ), а най-лошия случай е O (n2) . В най-добрия случай, той е от порядъка n, защото той просто сравнява елементите и не ги разменя. Тази техника също изисква допълнително пространство за съхранение на временната променлива.
Определение на сортирането на селекцията
Сортирането на селекцията е постигнало малко по-добра производителност и е ефективно от алгоритъма за сортиране на балончета. Да предположим, че искаме да подредим масив във възходящ ред, след това той функционира, като намерим най-големия елемент и го заменим с последния елемент, и повторим следния процес на под-масивите, докато целият списък се сортира.
Ключови разлики между сортиране и сортиране на балончета
- В сорта на балона всеки елемент и неговият съседен елемент се сравняват и сменят, ако е необходимо. От друга страна, сортирането на подбора работи чрез избиране на елемента и смяна на този елемент с последния елемент. Избраният елемент може да бъде най-голям или най-малък в зависимост от поръчката, т.е. възходящ или низходящ.
- Най-лошата сложност е същата в двата алгоритма, т.е. O (n2), но най-добрата сложност е различна. Балонният сорт отнема ред от време, докато сортирането на селекцията поема поредица от n2 време.
- Балонният сорт е стабилен алгоритъм, за разлика от това, сортирането на селекцията е нестабилно.
- Алгоритъмът за подбор е бърз и ефективен в сравнение с балонния вид, който е много бавен и неефективен.
заключение
Алгоритъмът за сортиране на мехурчета се счита за най-прост и неефективен алгоритъм, но алгоритъмът за подбор на сортиране е ефективен в сравнение с сорта на балончетата. Bubble sort също така консумира допълнително пространство за съхранение на временна променлива и се нуждае от повече суапове.
