Сортиране с мехурчета срещу сортиране на селекция
Сортирането с мехурчета е алгоритъм за сортиране, който работи, като преминава през списъка, за да бъде сортиран многократно, докато сравнява двойки елементи, които са съседни. Ако двойка елементи е в грешен ред, те се разменят, за да бъдат поставени в правилния ред. Това обхождане се повтаря, докато не са необходими допълнителни суапове. Сортирането при избор също е алгоритъм за сортиране, който започва с намиране на минималния елемент в списъка и размяната му с първия елемент. Този процес се повтаря за останалата част от списъка чрез поставяне на разменени елементи в ред.
Какво е Bubble Sort?
Сортирането с мехурчета е алгоритъм за сортиране, който работи, като преминава през списъка, за да бъде сортиран многократно, докато сравнява двойки елементи, които са съседни. Ако двойка елементи е в грешен ред, те се разменят, за да бъдат поставени в правилния ред. Това преминаване се повтаря, докато не са необходими допълнителни размени (което означава, че списъкът е сортиран). Тъй като по-малките елементи в списъка излизат на върха, когато балон излиза на повърхността, той получава името сортиране на мехурчета. Bubble sort е много прост алгоритъм за сортиране, но има средна времева сложност от O(n2) при сортиране на списък с n елемента. Поради това балонното сортиране не е подходящо за сортиране на списъци с голям брой елементи. Но поради своята простота сортирането с мехурчета се преподава по време на въведенията в алгоритмите.
Какво е сортиране при избор?
Сортирането при избор също е друг алгоритъм за сортиране, който започва с намиране на минималния елемент в списъка и размяната му с първия елемент. След това минималният елемент се намира от остатъка от списъка (от втория елемент до последния елемент в списъка) и се разменя с втория елемент. Този процес се повтаря за останалата част от списъка чрез поставяне на разменени елементи по ред. Така че при сортиране при избор, на всяка стъпка от алгоритъма, списъкът е разделен на две части, където едната част съдържа сортирани елементи, а другата част съдържа несортирани елементи. Докато алгоритъмът продължава, сортираният списък нараства отляво надясно. Сортирането при избор също има средна времева сложност на случая от O(n2). Следователно не е подходящ и за сортиране на големи списъци.
Каква е разликата между Bubble Sort и Selection Sort?
Въпреки че както алгоритмите за балонно сортиране, така и за селекционно сортиране имат средна времева сложност на случая от O(n2), балонното сортиране е почти винаги по-добро от сортирането за селекцията. Това се дължи на броя суапове, необходими на двата алгоритъма (балонното сортиране изисква повече суапове). Но поради простотата на балонното сортиране размерът на неговия код е много малък. Стабилността е друга разлика в тези два алгоритъма. Стабилният алгоритъм за сортиране е алгоритъм за сортиране, който запазва реда на записите, ако списъкът съдържа елементи с еднаква стойност. В този смисъл сортирането при избор не е стабилен алгоритъм, докато сортирането с мехурчета е стабилен алгоритъм.
