✅ Прости алгоритми за сортиране на JavaScript

Съдържание

Алгоритъмът по дефиниция е подредено множество (Това е много важно) на системни операции, което ни позволява да направим изчисление, за да намерим решението на всички проблеми от същия тип. С други думи, това е набор от инструкции, които винаги следват следния модел:

Точност: Трябва да обясните еднозначно и недвусмислено всяка стъпка или инструкция.
Окончателно: Броят на инструкциите за изпълнение трябва да бъде ограничен.
Определение: Същите входни данни винаги трябва да предоставят една и съща изходна информация.
Вход: Броят на входните елементи може да бъде нула или повече.
Резолюция: Той винаги трябва да дава резултат, който ще бъде изходните данни.

Когато алгоритъмът е внедрен в определен език за програмиране, той се превръща в програма, която може да бъде изпълнена на компютър, следователно можем да кажем, че програмата е алгоритъм или набор от алгоритми, написани на определен език, за да може компютърът да ги интерпретира. В този случай тази програма се нарича изчислителен алгоритъм. От друга страна, ако не се нуждае от компютър, за да работи, говорим за не-изчислителни алгоритми.

В нашия случай ще говорим за изчислителни алгоритми.

Знаейки какво е алгоритъм, ще се съсредоточим върху алгоритмите за сортиране или какво е същото, алгоритъмът, който служи за сортиране и връщане на списък, който първоначално е бил снабден с произволно разположени елементи, вече подредени.
The 3 алгоритма за сортиране най -известните са Сортиране на балончета или сортиране по балонче, Сортиране на селекция или сортиране по избор и Вмъкване сортиране или сортиране чрез вмъкване. Всички те се считат за прости алгоритми или методи, тъй като се решават чрез итерация или повторение до брой n пъти.

1. Сортиране на балончета или сортиране по балонВземайки за пример масив с четири стойности, в този случай за простота четири числа ще видим как работи алгоритъмът.

Масив = (4, 7, 8, 5, 9);

Искаме да го върнете подредено от най -високо до най -ниско например, тоест (9, 8, 7, 5, 4).

За да направите това, първото нещо, което трябва да направим, е да попитаме първите две стойности коя е най -голямата. В случай, че втората стойност е по -голяма от първата, както е в случая, те трябва да бъдат разменени, от друга страна, ако вече са поръчани, ги оставяме такива, каквито са.
Тогава същият процес трябва да се повтори с втората и третата стойност. В този случай третата стойност е по -голяма, така че ще я заменим, оставяйки нашия масив = (7, 8, 4, 5, 9).
След това повтаряме предишната стъпка с третата и четвъртата стойност и отново ги обменяме. (7, 8, 5, 4, 9).
И накрая след първата итерация ще бъде: (7, 8, 5, 9, 4).
Все още не е подредено, но е постигнато последният елемент, този отдясно на цялото, 4, ако е подреден като най -малкия брой от всички.
В следващия кръг, за да подредим нашия масив, вече не е необходимо да вземаме предвид последния, защото вече знаем, че е подреден, така че бихме сравнили първия и втория елемент, след това втория и третия елемент и накрая трети и четвърти елемент и масивът ще останат: (8, 7, 9, 5, 4).
Сега последният и предпоследният елемент са сортирани.
Правим още един кръг, сравнявайки първата и втората стойности, а след това втората и третата и масивът изглежда така: (8, 9, 7, 5, 4).
Последните три елемента вече са подредени, така че отнема само още един завой, за да оставите масива напълно подреден: (9, 8, 7, 5, 4).

Ето как алгоритъм на бурбуджа, който се нарича така, защото при всеки завой последният елемент се издига като балон и се подрежда.

Сега се прилага към JavaScript Много е просто:

балон с функция (myArray) {var tam = myArray.length; for (var temp = 1; temp <size; temp ++) {for (var left = 0; left <(size - temp); left ++) {var right = left +1; if (myArray [вляво] <myArray [вдясно] {сортиране (myArray, наляво, надясно);}}} върне myArray;}

Предаваме масив на нашата функция и в него първото нещо, което правим, е да изчислим неговия размер, да изчислим броя на елементите в масива.
След това създаваме външен цикъл, който преминава през нашия масив толкова пъти, колкото елементите имат минус едно (тъй като те са времето, необходимо за пълното му поръчване).
Вътрешно ние създаваме друг цикъл, който преминава през стойностите, сравнявайки всеки един със следващия и ако този вляво е по -малък от този вдясно, той ги обменя с функцията за сортиране, която ще видим по -нататък.
Накрая връща подредения масив.

функция сортиране (myArray, value1, value2) {var temp = myArray [value1]; myArray [стойност1] = myArray [стойност2]; myArray [стойност2] = темп; върни myArray;}

където value1 е индексът на първия елемент за обмен и value2 е индексът на втория елемент за обмен.

2. Сортиране на селекциятаАлгоритъмът, който ще видим по -долу, не премества елементите един по един, както в балонния, а първо преминава през пълния масив и след това избира правилния елемент за поставяне според критериите, които следваме (например от най -високото до най -ниското) и го поставя директно в позицията си и по този начин алгоритъмът получава името си, избирайки, вземайки елемент и го премества с едно движение до правилното му положение.

В същия пример, както преди Array = (4, 7, 8, 5, 9), ако искаме да го подредим например от най -високо до най -ниско, първо бихме избрали 9 и го поставихме на първо място и 4 ще заеме последното позиция (9, 7, 8, 5, 4). Във втория кръг той щеше да избере 8 и да го замени със 7, за да остане в правилната позиция. В следващите кръгове не бих променил нищо, тъй като вече е поръчано.

Кодът на този алгоритъм ще бъде следният:

избор на функция (myArray) {var tam = myArray.length; for (var temp = 0; temp <размер -1; temp ++) {major = temp; for (var check = temp +1; check <size; check ++) {if (myArray [check] <myArray [major] {major = check;}} сортиране (myArray, major, check);} връщане на myArray;}

Кодът работи подобно на този на балона, но външният цикъл for преминава през стойностите от 0 до N-2 (те са същия брой стъпки като между 1 и N-1 като в балона, но операцията е различна ) действа директно върху елементите, за да ги доведе до правилното положение при всеки завой.
Броят на завоите, необходими за подреждането на всички елементи, е същият като в балона N-1, тъй като след всяка итерация оставяме елемент, поставен на мястото му, и този, който можем да пренебрегнем в следващите завои.

Ние обаче леко променяме функцията за сортиране, за да си спестим стъпките, когато установим, че някой елемент вече е подреден:

функция сортиране (myArray, value1, value2) {if (value1 == value2) {return myArray; } var temp = myArray [стойност1]; myArray [стойност1] = myArray [стойност2]; myArray [стойност2] = темп; върни myArray;}

За да постигнем това, включихме цикъл if, в който проверява дали стойностите съвпадат, тоест дали вече са подредени.

3. Сортиране на вмъкванеНакрая ще видим най-ефективния алгоритъм от трите, тъй като не винаги ще се нуждаем от N-1 итерации, за да поставим нашия масив, както ще видим по-долу.

Този алгоритъм за вмъкване работи подобно на поставянето на ръка от карти в покер игра при раздаването на картите.
Обикновено подреждаме картите по костюми, а в тях по възходящ ред, както следва:
Първо се раздава карта, единичен елемент, който се подрежда (за това, че е уникален). Тогава, когато има „j“ елементи, подредени от най -малкото до най -голямото, ние вземаме елемента j + 1 и го сравняваме с всички вече подредени елементи. Ако намери по -малък, тъй като по -големите ще са се изместили надясно, този елемент (j + 1) се вмъква, измествайки се към останалата част.

The алгоритъм за вмъкване преведено на JavaScript език е както следва:

функция insert (myArray) {var tam = myArray.length, temp, place; for (var obj = 0; obj = 0 && myArray [място]> temp; място--) {myArray [място + 1] = myArray [място]; } myArray [място + 1] = temp; } връщане на myArray;}