✅ Paprasti „JavaScript“ rūšiavimo algoritmai

Turinys

Algoritmas pagal apibrėžimą yra užsakytas rinkinys (Tai labai svarbu) sistemingas operacijas, kurios leidžia atlikti skaičiavimus, kad rastume visų to paties tipo problemų sprendimą. Kitaip tariant, tai yra instrukcijų rinkinys, kuris visada atitinka šį modelį:

Tikslumas: Jūs turite unikaliai ir nedviprasmiškai paaiškinti kiekvieną žingsnį ar nurodymą.
Baigtinis: Vykdytinų nurodymų skaičius turi būti ribotas.
Apibrėžimas: Tie patys įvesties duomenys visada turi pateikti tą pačią išvesties informaciją.
Įėjimas: Įvesties elementų skaičius gali būti lygus nuliui ar daugiau.
Rezoliucija: Jis visada turėtų duoti rezultatą, kuris bus išvesties duomenys.

Kai algoritmas įgyvendinamas tam tikra programavimo kalba, jis tampa programa, kurią galima vykdyti kompiuteryje, todėl galime sakyti, kad programa yra tam tikra kalba parašytas algoritmas arba algoritmų rinkinys, kurį kompiuteris gali naudoti. Šiuo atveju ši programa vadinama skaičiavimo algoritmu. Kita vertus, jei jam paleisti nereikia kompiuterio, kalbame apie ne skaičiavimo algoritmus.

Mūsų atveju mes kalbėsime apie skaičiavimo algoritmai.

Žinodami, kas yra algoritmas, mes sutelksime dėmesį į rūšiavimo algoritmus arba tą patį algoritmą, kuris naudojamas rūšiuoti ir grąžinti sąrašą, kuris iš pradžių buvo pateiktas su jau užsakytais atsitiktinai išdėstytais elementais.
The 3 rūšiavimo algoritmai geriausiai žinomi yra Rūšiuoti burbuliukus arba rūšiuoti pagal burbulus, Atrankos rūšiuoti arba rūšiuoti pagal pasirinkimą ir Įterpimo rūšiuoti arba rūšiuoti pagal įterpimą. Visi jie laikomi paprastais algoritmais ar metodais, nes jie išsprendžiami kartojant arba kartojant iki n kartų.

1. Rūšiuoti burbulus arba rūšiuoti pagal burbuląPaimdami pavyzdį masyvą su keturiomis reikšmėmis, šiuo atveju, norėdami supaprastinti keturis skaičius, pamatysime, kaip veikia algoritmas.

Masyvas = (4, 7, 8, 5, 9);

Mes norime, kad grąžintumėte jį, pavyzdžiui, nuo aukščiausio iki žemiausio, ty (9, 8, 7, 5, 4).

Norėdami tai padaryti, pirmiausia turime paklausti pirmųjų dviejų verčių, kurios yra didžiausios. Tuo atveju, jei antroji vertė yra didesnė už pirmąją, kaip yra, jie turėtų būti keičiami, kita vertus, jei jie jau užsakyti, mes paliekame juos tokius, kokie jie yra.
Tada tą patį procesą reikėtų pakartoti su antrąja ir trečiąja reikšmėmis. Šiuo atveju trečioji vertė yra didesnė, todėl mes ją keistume, palikdami masyvą = (7, 8, 4, 5, 9).
Tada pakartojame ankstesnį veiksmą su trečia ir ketvirta reikšmėmis ir vėl jas keičiame. (7, 8, 5, 4, 9).
Ir pagaliau po pirmosios kartojimo tai būtų: (7, 8, 5, 9, 4).
Jis vis dar nėra užsakytas, tačiau buvo pasiekta, kad paskutinis elementas, esantis dešinėje visumos pusėje, yra 4, jei jis užsakomas kaip mažiausias skaičius.
Kitame etape, norint užsisakyti mūsų masyvą, nebereikia atsižvelgti į paskutinį, nes mes jau žinome, kad jis yra užsakytas, todėl palygintume pirmąjį ir antrąjį, tada antrąjį ir trečiąjį elementus, ir galiausiai trečias ir ketvirtas elementas ir masyvas liktų: (8, 7, 9, 5, 4).
Dabar surūšiuotas paskutinis ir priešpaskutinis elementas.
Mes darome kitą raundą, lygindami pirmąją ir antrąją reikšmes, tada antrąją ir trečiąją, o masyvas atrodo taip: (8, 9, 7, 5, 4).
Paskutiniai trys elementai jau yra užsakyti, todėl reikia tik dar vieno posūkio, kad masyvas būtų visiškai sutvarkytas: (9, 8, 7, 5, 4).

Štai kaip burburjos algoritmas, kuris vadinamas taip, nes kiekviename posūkyje paskutinis elementas kyla kaip burbulas ir yra užsakomas.

Dabar įgyvendinta iki „JavaScript“ Tai labai paprasta:

funkcijos burbulas (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 [kairė] <myArray [dešinė] {rūšiuoti (myArray, kairė, dešinė);}}} grąžinti myArray;}

Mes perduodame masyvą savo funkcijai ir pirmiausia jame apskaičiuojame jo dydį, apskaičiuojame masyvo elementų skaičių.
Tada mes sukuriame išorinę kilpą, kuri eina per mūsų masyvą tiek kartų, kiek elementų yra minus vienas (nes tai yra laikas, kurio reikia, kad jis būtų visiškai užsakytas).
Viduje mes sukuriame kitą kilpą, kuris eina per vertes, lygindamas kiekvieną su kita, ir jei kairėje esanti yra mažesnė už dešinę, ji keičia jas su rūšiavimo funkcija, kurią matysime toliau.
Galiausiai jis grąžina užsakytą masyvą.

funkcija rūšiuoti (myArray, value1, value2) {var temp = myArray [value1]; myArray [vertė1] = myArray [vertė2]; myArray [vertė2] = temperatūra; grąžinti myArray;}

kur vertė1 yra pirmojo keičiamo elemento indeksas, o vertė2 - antrojo keičiamo elemento indeksas.

2. Atrankos rūšiavimasAlgoritmas, kurį matysime žemiau, nejudina elementų po vieną kaip burbulas, bet pirmiausia eina per visą masyvą ir tada pasirenka tinkamą elementą, skirtą išdėstymui pagal kriterijus, kurių laikomės (pvz. iki žemiausio) ir jis įdeda jį tiesiai į savo vietą, ir taip algoritmas gauna pavadinimą, pasirinkdamas, paimdamas elementą ir vienu judesiu perkeldamas į teisingą padėtį.

Tame pačiame pavyzdyje, kaip ir anksčiau, masyvas = (4, 7, 8, 5, 9), jei norime jį užsisakyti nuo aukščiausio iki žemiausio, pavyzdžiui, pirmiausia pasirinktume 9 ir padėtume į pirmą vietą, o 4 užimtų paskutinę padėtis (9, 7, 8, 5, 4). Antrame raunde jis pasirinko 8 ir iškeitė jį į 7, kad liktų teisingoje padėtyje. Kituose etapuose aš nieko nekeisčiau, nes jis jau buvo užsakytas.

Šio algoritmo kodas būtų toks:

funkcijos pasirinkimas (myArray) {var tam = myArray.length; for (var temp = 0; temp <size -1; temp ++) {major = temp; for (var check = temp +1; check <size; check ++) {if (myArray [check] <myArray [major] {major = check;}} sort (myArray, major, check);} return myArray;}

Kodas veikia panašiai kaip ir burbulas, bet išorinis kilpai eina per reikšmes nuo 0 iki N-2 (jie yra toks pat žingsnių skaičius kaip nuo 1 iki N-1, kaip ir burbuliuke, tačiau operacija skiriasi ) veikiant tiesiai ant elementų, kad jie būtų teisingi kiekviename posūkyje.
Apsisukimų, reikalingų visiems užsakomiems elementams, skaičius yra toks pat, kaip ir N-1 burbule, nes po kiekvienos kartojimo mes paliekame elementą, esantį jo vietoje, ir tą, kurio negalime ignoruoti sekančiuose posūkiuose.

Tačiau šiek tiek pakeičiame rūšiavimo funkciją, kad išvengtume veiksmų, kai nustatome, kad kai kurie elementai jau yra užsakyti:

funkcija rūšiuoti (myArray, value1, value2) {if (value1 == value2) {return myArray; } var temp = myArray [vertė1]; myArray [vertė1] = myArray [vertė2]; myArray [vertė2] = temperatūra; grąžinti myArray;}

Norėdami tai pasiekti, įtraukėme ciklą „if“, kuriame jis tikrina, ar vertės sutampa, tai yra, ar jos jau užsakytos.

3. Įterpimo rūšiavimasGaliausiai pamatysime efektyviausią algoritmą iš trijų, nes mums ne visada reikės N-1 iteracijų, kad išdėstytume savo masyvą, kaip matysime žemiau.

Šis įterpimo algoritmas veikia panašiai kaip įdėjus kortas į pokerio žaidimą, kai kortos yra dalijamos.
Paprastai mes užsakome korteles pagal kostiumus, o jose didėjančia tvarka:
Pirmiausia išdalijama kortelė - vienas elementas, kuris yra užsakomas (dėl unikalumo). Tada, kai „j“ elementai yra užsakyti nuo mažiausio iki didžiausio, imame elementą j + 1 ir palyginame jį su visais jau užsakytais elementais. Jei jis randa mažesnį, nes didesni bus pasislinkę į dešinę, šis elementas (j + 1) įterpiamas, pereinant prie likusio.

The įterpti algoritmą išverstas į „JavaScript“ kalba yra tokia:

funkcijos intarpas (myArray) {var tam = myArray.length, temp, place; for (var obj = 0; obj = 0 && myArray [vieta]> temp; vieta--) {myArray [vieta + 1] = myArray [vieta]; } myArray [vieta + 1] = temp; } grąžinti myArray;}