✅ Jednostavni JavaScript algoritmi za sortiranje

Sadržaj

Algoritam je po definiciji uređen skup (Ovo je veoma važno) sustavnih operacija koje nam omogućuju izračun kako bismo pronašli rješenje za sve probleme istog tipa. Drugim riječima, to je skup uputa koje uvijek slijede sljedeći obrazac:

Preciznost: Morate jedinstveno i nedvosmisleno objasniti svaki korak ili uputu.
Konačno: Broj instrukcija za izvršavanje mora biti ograničen.
Definicija: Isti ulazni podaci moraju uvijek pružati iste izlazne podatke.
Ulaz: Broj ulaznih elemenata može biti nula ili više.
Rezolucija: Uvijek bi trebao proizvesti rezultat koji će biti izlazni podaci.

Kada se algoritam implementira u određeni programski jezik, on postaje program koji se može izvesti na računalu, stoga možemo reći da je program algoritam ili skup algoritama napisanih na određenom jeziku koje računalo može koristiti. U ovom slučaju ovaj program se naziva računski algoritam. S druge strane, ako za rad ne treba računalo, govorimo o neračunarskim algoritmima.

U našem slučaju ćemo govoriti o računski algoritmi.

Znajući što je algoritam, usredotočit ćemo se na algoritme za sortiranje, ili na ono što je isto, algoritam koji služi za sortiranje i vraćanje popisa koji je u početku bio opremljen nasumično postavljenim elementima koji su već naručeni.
The 3 algoritma sortiranja najpoznatiji su Sortiranje mjehurića ili sortiranje po mjehurićima, Odabir sortiranje ili sortiranje odabirom i Umetanje sortiranje ili sortiranje umetanjem. Svi se oni smatraju jednostavnim algoritmima ili metodama jer se rješavaju iteracijom ili ponavljanjem do broja n puta.

1. Sortiranje mjehurića ili sortiranje po mjehurićimaUzimajući kao primjer niz s četiri vrijednosti, u ovom slučaju radi jednostavnosti četiri broja vidjet ćemo kako algoritam radi.

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

Želimo da ga vratite, na primjer, od najvišeg do najnižeg, to jest (9, 8, 7, 5, 4).

Da bismo to učinili, prvo što moramo učiniti je pitati prve dvije vrijednosti koja je najveća. U slučaju da je druga vrijednost veća od prve, kao što je slučaj, treba ih zamijeniti, s druge strane, ako su već naručene, ostavljamo ih kakve jesu.
Tada bi se isti postupak morao ponoviti s drugom i trećom vrijednošću. U ovom slučaju treća vrijednost je veća pa bismo je zamijenili, ostavljajući naš niz = (7, 8, 4, 5, 9).
Zatim ponovimo prethodni korak s trećom i četvrtom vrijednošću, pa ih opet zamijenimo. (7, 8, 5, 4, 9).
I konačno nakon prve iteracije bilo bi: (7, 8, 5, 9, 4).
Još uvijek nije uređen, međutim postignuto je da posljednji element, onaj s desne strane cjeline, 4, ako je poredan kao najmanji broj od svih.
U sljedećem krugu za naručivanje našeg niza više nije potrebno uzimati u obzir posljednji jer već znamo da je uređen pa bismo usporedili prvi i drugi element, zatim drugi i treći element i na kraju treći i četvrti element i niz bi ostali: (8, 7, 9, 5, 4).
Sada je zadnji i pretposljednji element razvrstan.
Radimo još jedan krug uspoređujući prvu i drugu vrijednost, a zatim drugu i treću, a niz izgleda ovako: (8, 9, 7, 5, 4).
Posljednja tri elementa već su uređena, pa je potrebno još samo jedno okretanje da bi se niz ostavio potpuno uređen: (9, 8, 7, 5, 4).

Ovako je algoritam burburja, koji se tako naziva jer se u svakom zavoju posljednji element diže poput mjehurića i uređen je.

Sada implementirano u JavaScript Vrlo je jednostavno:

mjehurić funkcija (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 [lijevo] <myArray [desno] {sort (myArray, lijevo, desno);}}} vrati myArray;}

Prosljeđujemo niz našoj funkciji i unutar njega prvo što radimo je izračunati njegovu veličinu, izračunati broj elemenata u nizu.
Zatim stvaramo vanjsku petlju koja prolazi kroz naš niz onoliko puta koliko elementi imaju minus jedan (budući da su to vremena potrebna za potpuno naručivanje).
Interno stvaramo drugu petlju koja prolazi kroz vrijednosti uspoređujući svaku sa sljedećom, a ako je ona s lijeve strane manja od one s desne strane, razmjenjuje ih s funkcijom sortiranja koju ćemo vidjeti sljedeće.
Na kraju vraća uređeni niz.

sortiranje funkcija (myArray, value1, value2) {var temp = myArray [value1]; myArray [value1] = mojArray [value2]; myArray [value2] = temp; vrati myArray;}

gdje je value1 indeks prve stavke koju je potrebno zamijeniti, a value2 indeks druge stavke koju je potrebno zamijeniti.

2. Razvrstavanje odabiraAlgoritam koji ćemo vidjeti u nastavku ne pomiče elemente jedan po jedan kao u oblačiću, već prvo prolazi kroz cijeli niz, a zatim odabire ispravan element za postavljanje prema kriterijima koje slijedimo (na primjer, od najvišeg do najnižeg) i postavlja ga izravno u svoj položaj, pa tako i algoritam dobiva ime, odabirom, uzimanjem elementa i premještanjem jednim pokretom u ispravan položaj.

U istom primjeru kao i prije Array = (4, 7, 8, 5, 9) ako ga želimo, na primjer, poredati od najvišeg do najnižeg, prvo bismo odabrali 9 i stavili ga na prvo mjesto, a 4 bi zauzeli posljednje položaj (9, 7, 8, 5, 4). U drugom krugu odabrao bi 8 i zamijenio ih sa 7 kako bi ostao na ispravnom mjestu. U sljedećim rundama ne bih ništa mijenjao jer je već naručeno.

Kod ovog algoritma bio bi sljedeći:

odabir funkcije (myArray) {var tam = myArray.length; for (var temp = 0; temp <veličina -1; temp ++) {major = temp; for (var check = temp +1; check <size; check ++) {if (myArray [check] <myArray [major] {major = check;}} sortiraj (myArray, major, check);} vrati myArray;}

Kôd radi slično kao mjehurić, ali vanjska for petlja prolazi kroz vrijednosti od 0 do N-2 (isti su broj koraka između 1 i N-1 kao u oblačiću, ali je operacija drugačija ) izravno djelujući na elemente kako bi ih pri svakom zavoju doveli u ispravan položaj.
Broj zavoja neophodnih da bi se svi elementi naručili isti je kao u mjehuriću N-1, jer nakon svake iteracije ostavljamo element postavljen na njegovo mjesto i onaj koji možemo zanemariti u sljedećim zavojima.

Međutim, malo smo izmijenili funkciju sortiranja kako bismo uštedjeli korake kada otkrijemo da je neki element već naručen:

funkcija sortiranja (myArray, value1, value2) {if (value1 == value2) {return myArray; } var temp = myArray [vrijednost1]; myArray [value1] = mojArray [value2]; myArray [value2] = temp; vrati myArray;}

Da bismo to postigli, uključili smo petlju if u kojoj provjerava podudaraju li se vrijednosti, odnosno jesu li već naručene.

3. Razvrstavanje umetanjaKonačno ćemo vidjeti najučinkovitiji algoritam od tri jer nećemo uvijek trebati N-1 iteracije za postavljanje našeg niza kao što ćemo vidjeti u nastavku.

Ovaj algoritam za umetanje djeluje slično kao stavljanje karte u poker dok se karte dijele.
Karte obično naručujemo prema odijelima, a unutar njih prema uzlaznom redoslijedu na sljedeći način:
Prvo se dijeli karta, jedan element koji se naručuje (zbog jedinstvenosti). Zatim, kada postoje "j" elementi poredani od najmanjeg do najvećeg, uzimamo element j + 1 i uspoređujemo ga sa svim već uređenim elementima. Ako pronađe manji, budući da će se veći pomaknuti udesno, ovaj element (j + 1) se umetne, pomaknuvši se na ostatak.

The algoritam za umetanje prevedeno na JavaScript jezik je kako slijedi:

funkcija insert (myArray) {var tam = myArray.length, temp, place; for (var obj = 0; obj = 0 && myArray [mjesto]> temp; mjesto--) {myArray [mjesto + 1] = myArray [mjesto]; } myArray [mjesto + 1] = temp; } vrati myArray;}