Разлика между сортиране на балончета и сортиране на селекция

Сортиране на балон срещу сортиране на селекция

Bubble Sort е алгоритъм за сортиране, който работи, като преминава през списъка, който се сортира многократно, като се сравняват двойки елементи, които са съседни. Ако чифт елементи са в неправилен ред, те се разменят, за да ги поставят в правилния ред. Това преминаване се повтаря, докато не се изискват допълнителни размени. Сортирането на селекция е също алгоритъм за сортиране, който започва с намирането на минималния елемент в списъка и замяната му с първия елемент. Този процес се повтаря в останалата част от списъка, като се поставят подредени елементи в ред.

Какво е Bubble Sort?

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

Какво е сортиране на селекцията?

Сортирането на селекция е също друг алгоритъм за сортиране, който започва с намирането на минималния елемент в списъка и замяната му с първия елемент. Тогава минималният елемент се намира от остатъка от списъка (от втория елемент до последния елемент в списъка) и се заменя с втория елемент. Този процес се повтаря в останалата част от списъка, като се поставят подредени елементи в ред. Така при сортиране на селекцията, на всеки етап от алгоритъма, списъкът е разделен на две части, където едната част съдържа сортирани елементи, а другата част съдържа несортирани елементи. Докато алгоритъмът продължава, сортираният списък расте отляво надясно. Сортирането за избор също има средна сложност на времето за случай на O (n2). Поради това той също не е подходящ за сортиране на големи списъци.

Каква е разликата между Bubble Sort и Sort Selection?

Въпреки че и алгоритмите за сортиране на балончета и сортиране на селекция имат средни сложни времена на случай на O (n2), сортирането на балонче почти през цялото време превъзхожда сорта за избор. Това се дължи на броя суапове, необходими на двата алгоритъма (сортирането на балони се нуждае от повече суапове). Но поради простотата на сортирането на балончетата, размерът на кода му е много малък. Стабилността е друга разлика в тези два алгоритма. Стабилен алгоритъм за сортиране е алгоритъм за сортиране, който запазва реда на записите, ако списъкът съдържа елементи с еднаква стойност. В този смисъл сортирането на селекция не е стабилен алгоритъм, докато сортирането на балон е стабилен алгоритъм.