Сортиране с балончета срещу сортиране чрез вмъкване
Сортирането с мехурчета е алгоритъм за сортиране, който работи, като преминава през списъка, за да бъде сортиран многократно, докато сравнява двойки елементи, които са съседни. Ако двойка елементи е в грешен ред, те се разменят, за да бъдат поставени в правилния ред. Това обхождане се повтаря, докато не са необходими допълнителни суапове. Сортирането чрез вмъкване също е алгоритъм за сортиране, който работи чрез вмъкване на елемент във входния списък на правилната позиция в списък, който вече е сортиран. Този процес се прилага многократно, докато списъкът бъде сортиран.
Какво е Bubble Sort?
Сортирането с мехурчета е алгоритъм за сортиране, който работи, като преминава през списъка, за да бъде сортиран многократно, докато сравнява двойки елементи, които са съседни. Ако двойка елементи е в грешен ред, те се разменят, за да бъдат поставени в правилния ред. Това преминаване се повтаря, докато не са необходими допълнителни размени (което означава, че списъкът е сортиран). Тъй като по-малките елементи в списъка излизат на върха, когато балон излиза на повърхността, той получава името сортиране на мехурчета. Bubble sort е много прост алгоритъм за сортиране, но има средна времева сложност от O(n2) при сортиране на списък с n елемента. Поради това балонното сортиране не е подходящо за сортиране на списъци с голям брой елементи. Но поради своята простота сортирането с мехурчета се преподава по време на въведенията в алгоритмите.
Какво е сортиране чрез вмъкване?
Сортиране чрез вмъкване е друг алгоритъм за сортиране, който работи чрез вмъкване на елемент във входния списък на правилната позиция в списък (който вече е сортиран). Този процес се прилага многократно, докато списъкът бъде сортиран. При сортиране чрез вмъкване сортирането се извършва на място. Следователно след i-тата итерация на алгоритъма, първите i+1 записи в списъка ще бъдат сортирани, а останалата част от списъка няма да бъде сортирана. При всяка итерация първият елемент в несортираната част на списъка ще бъде взет и вмъкнат на правилното място в сортираната секция на списъка. Сортирането при вмъкване има средна времева сложност на случая O(n2). Поради това сортирането чрез вмъкване също не е подходящо за сортиране на големи списъци.
Каква е разликата между Bubble Sort и Insertion Sort?
Въпреки че както алгоритмите за балонно сортиране, така и за сортиране чрез вмъкване имат средна времева сложност на случая от O(n2), балонното сортиране почти през цялото време се превъзхожда от сортирането с вмъкване. Това се дължи на броя суапове, необходими на двата алгоритъма (балонното сортиране изисква повече суапове). Но поради простотата на балонното сортиране размерът на неговия код е много малък. Също така има вариант на сортиране чрез вмъкване, наречен shell sort, който има времева сложност O(n3/2), което би позволило практическото му използване. Освен това сортирането чрез вмъкване е много ефективно за сортиране на „почти сортирани“списъци в сравнение със сортирането с балончета.
