WEBnSTUDY.com
JavaScript

Sortiranje niza u JavaScriptu

U ovom tekstu ćemo se baviti metodima Array objekta koji utiču na redosled elemenata. Najbitnije je svakako sortiranje niza. Ako se do sada niste sreli sa tim terminom, sortiranje predstavlja "uređivanje" elemenata niza po nekom kriterijumu - najčešće je to ređanje od najmanjeg do najvećeg elementa ili obrnuto.

Druga pogodnost koju nam pruža ovaj objekat je mogućnost da se lako obrnemo redosled elemenata niza. Metodi koje ćemo ovde obraditi su:

a.sort(F) Sortira niz.
a.reverse() Obrće redosled elemenata niza.

Sortiranje niza

Objekat Array u JavaScriptu ima ugrađen zgodan metod koji vrši sortiranje elemenata niza. U pitanju je metod sort(). Ovaj metod ne kreira novi niz već menja postojeći.

Metod sort() će, ako ga zadamo bez ikakvih parametara izvršiti sortiranje elemenata niza u rastućem poretku (od najmanjeg do najvećeg). Treba da znate da se u tom slučaju, svi elementi niza posmatraju kao stringovi. Konverzija elemenata neće biti zaista izvršena (naši elementi se neće zaista promeniti), ali bi dobijeni redosled mogao da nas iznenadi. Ovo se dešava čak iako sortiramo niz brojeva. Evo šta se tada dešava:

Originalan niz: [5, 15, 1, 220, 3] Redosled koji očekujemo: [1, 3, 5, 15, 220] Redosled koji dobijamo: [1, 15, 220, 3, 5]

Šta se desilo? Pa kada smo vršili sortiranje, svi brojevi su posmatrani kao tekstovi, a kada se ređa po "abecedi" (tačnije po ciframa), "220" je "manje" od "3", isto kao što bi "aaa" bilo ispred "c".

U suštini, ovo se dešava da bi svaki niz mogao da se sortira. U praksi se često dešava da elementi niza nisu obični brojevi, već objekti. Da bi takav niz mogao da se sortira, svaki objekat se "interno" pretvara u tekstualni oblik.

Ima još stvari o kojima moramo da vodimo računa. Redosled kojim se uređuju string (tekstualni) podaci ne zavisi zaista od abecednog redosleda, već od pozicije znakova u UNICODE tabeli. Ovaj redosled ne mora da bude zaista po abecedi. Prema standardu, velika slova idu pre malih. Poseban problem je ako stringovi imaju i naša ćirilična ili latinična slova, pošto njihov redosled u UNICODE-u nije po našoj gramatici. Evo npr. redosleda koji važi za latinična slova:

A..Z ... a..z ... Ć ć Č č Đ đ Š š Ž ž

Obično sortiranje niza

Evo dva primere sortiranja - niza stringova i niza brojeva. Niz stringova se, logično, sortira po abecedi, dok se brojevi posmatraju kao stringovi i onda sortiraju po ciframa, a ne po vrednostima.


  var imena = ["Borko", "Anastazija", "Ana", "Joca"];
  imena.sort();
  console.log(imena);  
  // Rezultat: ["Ana", "Anastazija", "Borko", "Joca"]

  var brojevi = [1, 5, 100, 234, 10, 22];
  brojevi.sort();
  console.log(brojevi);
  // Rezultat: [1, 10, 100, 22, 234, 5]
  
  console.log(niz[0]+niz[1]);

Sve o čemu smo pisali, možete isprobati u primeru.

Sortiranje pomoću callback funkcije

Ovde stvari postaju zanimljive! Dakle, sam metod sort() nije previše koristan, međutim, kada naučimo kako da mu prosledimo funkciju za upoređivanje, dobijamo veoma moćno oružje u programiranju.

Metod sort(), tako može imati parametar koji predstavlja callback funkciju, koja se poziva pri svakom upoređivanju. Da se podsetimo: algoritmi sortiranja, bez obzira na kom principu funkcionišu, zasnivaju se na uzastopnom upoređivanju dva elementa niza. Na osnovu tog poređenja, algoritam "zna" da li ta dva elementa treba da zamene mesta ili ne. Uzastopnim poređenjima dva-po-dva elementa i njihovim "obrtanjem", dobijamo sortiran niz.

Ideja je da objekat Array, pruži mogućnost programeru da napravi svoju funkciju za poređenje, na osnovu koje elementi menjaju mesta ili ne. To znači da mi ne treba da pravimo ceo algoritam za sortiranje, već samo deo za poređenje. Ali ovo uopšte nije mala stvar - na taj način možemo pravilno sortirati i brojeve i kompleksne objekte i to i u rastućem i u opadajućem redosledu. Sve to u stvari zavisi od rezultata funkcije za poređenje.

Funkcija prima dva parametra koji predstavljaju dva elementa niza koji se u tom trenutku upoređuju. Imajte u vidu da funkcija "zna" vrednosti elemenata, ali ne i njihove pozicije. Srećom, indeksi elemenata skoro nikada nisu bitni za određivanje redosleda.

function (a,b) { ... return vrednost; }

Kao rezultat vraća jednu numeričku vrednost koja ima sledeće značenje:

negativna vrednost A treba da bude ispred B
0 A i B su isti
pozitivna vrednost B treba da bude ispred A

Da biste se lakše snašli, samo zapamtite sledeće: pozitivna vrednost znači da se elementi obrću, negativna da se ništa ne menja.

Primer korišćenja callback funkcije

JavaScript mogućava da kao callback funkciju prosledimo referencu funkcije (praktično njen naziv) ili samu funkciju koja može biti imenovana ili anonimna. U ovom primeru koristimo funkciju provera() kako bismo obezbedili sortiranje brojeva u opadajućem redosledu.


  function provera(a,b)
  {
    if (a < b) return 1;  // ako je A manje od B, menjamo im mesta
    return -1;               // inače nista
  }

  var brojevi = [1, 5, 100, 234, 10, 22];
  brojevi.sort(provera);
  console.log(brojevi); // Rezultat: [234, 100, 22, 10, 5, 1]

Kada se koristi funkcija za poređenje, njoj se prosleđuju prave vrednosti elemenata niza, a ne njihove string reprezentacije.

Isto tako možemo zadati samu funkciju koja može biti imenovana ili anonimna. Ovaj put ćemo iskoristiti anonimnu funkciju, i pokazaćemo i malo efikasniji način upoređivanja koji izbegava if naredbu.


  var brojevi = [1, 5, 100, 234, 10, 22];
  brojevi.sort(function(a,b) {
    return b-a;  // ako je A manje od B, vraća pozitivan broj, što znači da im menjamo mesta
  });
  console.log(brojevi); // Rezultat: [234, 100, 22, 10, 5, 1]

Ipak - čuvajte se. Ne zaboravite da operacija oduzimanja može vratiti i vrednost 0. Iako će ovaj primer uvek raditi bez greške (ipak su u pitanju obični brojevi), potrudite se da nulu izbegnete.

Evo i zašto. Razmislite o ovakvom primeru sortiranja stringova, ali ne po abecedi, već po dužini.


    var rec = ["O", "ist", "e ", "v", "n so", "se", "i s", "d", "itam.", 
               "rt a", " k", "tab", "ila", "lgor", "or"];
    rec.sort(function(a,b) {
      return a.length-b.length;  // želimo da budemo efikasni, ali čeka nas iznenađenje
    });
    console.log(rec.join(""));
    // Stabilan algoritam:   "Ovde se koristi stabilan sort algoritam."
    // Nestabilan algoritam: "dOve orse kisti stabilan solgorrt aitam." (npr.)

Stabilan algoritam treba da vrati tekst: "Ovde se koristi stabilan sort algoritam.", pošto smo tako namestili stringove da se dobija ovakav tekst ako se NE RAZMENJUJU pozicije stringova iste dužine. Nestabilan algoritam (Google Chrome) vraća nešto kao "dOve orse kisti stabilan solgorrt aitam."

Pogledajte primer u kome demonstriramo sve ovo što smo opisivali, kao i da biste videli kako da rešite sortiranje stringova sa našim slovima i objekata sa više podataka po kojima se može vršiti sortiranje.

Obrtanje redosleda niza

Svaki Array objekat ima i metod reverse() koji obrće redosled elemenata niza. Kao i metod sort(), i metod reverse() ne kreira novi niz već menja postojeći.

Obrtanje redosleda je mnogo jednostavnije od sortiranja. Nema nedoumica, nema posebnih parametara ni callback funkcija.

Obrtanje redosleda niza


  var niz = ['prvi', 'drugi', 'treći'];
  niz.reverse(); 

  console.log(niz) // ['treći', 'drugi', 'prvi']
  1. Mozilla Developer Network, Array.prototype.sort()
  2. Mozilla Developer Network, Array.prototype.reverse()
  3. Rodney Rehm, Sorting - We're Doing It Wrong
Svi elementi sajta Web'n'Study, osim onih za koje je navedeno da su u javnom vlasništvu, vlasništvo su autora i ne smeju se koristiti, u celosti ili delimično bez pismenog odobrenja autora. To uključuje tekstove, slike, ilustracije, animacije, prateći grafički materijal i programski kod.
Ovaj sajt koristi tehnologiju kolačića (cookies) radi vođenja interne statistike u cilju unapređenja korisničkog iskustva. Tako prikupljeni podaci su anonimni i nedostupni trećim licima. Vaša privatnost nije ugrožena ni na koji način.