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

Сортиране на балони срещу сортиране на вмъкване

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

Какво е Bubble Sort?

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

Какво е сортиране на вмъкване?

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

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

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