Алгоритми за търсене и сортиране в Javascript — Част 3 (Сортиране при избор)
Друг много често срещан алгоритъм за сортиране, за който трябва да знаете, е алгоритъмът за Сортиране при избор. Също така е много лесен за изпълнение. Без да ви отнема много време, нека разберем как работи това.
Даден е масив от числа — [10, 8, 11, 1, 3, 80, 2, 7, 9], нашата функция за сортиране при избор ще вземе този масив и ще върне следното — [1, 2, 3, 7, 8, 9, 10, 11, 80]. Целта е да сортирате масива от най-ниското до най-високото, така че нека да разгледаме включените стъпки:
- Преминаваме през масива от числа от началото до края (ще наречем това L1)
- Във всеки цикъл вземаме числото при текущия индекс i и го записваме някъде.
- Ще започнем друг цикъл в нашия първоначален цикъл (L1), който ще премине през нашия масив от числа от i+1 до края на масива. Нека наречем този цикъл L2.
- След това ще сравним нашето текущо число в L1 с всяко число в L2. Ще търсим всички числа, по-малки от нашето текущо число в L1, ще вземем най-малкото от тези числа (най-малкото от най-малкото) и ще го разменим с нашето текущо число в оригиналния масив. Това ще постави текущия номер в L1 на правилната позиция. Това означава, че в края на всяко преминаване в L1 всички числа отляво се сортират.
- Повторете това за всички числа в L1. Докато стигнем до края на цикъла в L1, всички числа ще бъдат сортирани.
Разбирам, че това може да звучи безсмислено в момента, но нека видим това в код. Защо не??
С какво това е по-добро от Bubble Sort?
Основната разлика между балонно сортиране и сортиране по избор е, чебалонното сортиране работи чрез многократно разместване на съседните елементи, ако са в грешен ред, докато сортирането по селекцията подрежда елемента от масив чрез многократно намиране на минималния елемент от несортирания част и поставянето й в началото на несортираната част.
Друга основна разлика е, че сортирането при избор обикновено е по-бързо и по-ефективно от сортирането с балончета. Въпреки че и двете имат най-лош случай времева сложност от O(n^2),сортирането на селекцията все още изглежда по-бързо в повечето случаи. Това се дължи на броя на суаповете, извършени при сортиране по избор в сравнение с балонно сортиране.
Лично аз за малки масиви ( _вмъкнете вашата дефиниция за „малки масиви“_), ще избера сортиране по избор вместо сортиране с мехурчета.
Надявам се, че това обяснява вида на избора за вас. Ако все още се нуждаете от повече пояснения, вижте това визуално представяне на сортиране на селекцията във Visualgo — https://visualgo.net/en/sorting.
Ще се видим на следващия!
