Vi skal se på noen måter å sortere på. I alle eksemplene arbeider vi med en liste av n tilfeldige heltall i området [0..150]:

var liste;
function setUp(n){
  liste=new Array();
  for(var ix=0;ix < n; ix++)
    liste.push(Math.floor(Math.random() * 150));
}

Når vi skal sortere lista vil vi i alle eksemplene gjøre det "in situ". Det vil si at vi ikke skal lagre data midlertidig i en ny liste. Det betyr at vi må bytte om på plasseringen inne i vår originale liste. Det betyr at vi åpenbart har bruk for en "bytte"-funksjon.

function bytt(ix1,ix2){
  var tmp=liste[ix1];
  liste[ix1]=liste[ix2];
  liste[ix2]=tmp;
}

Den typiske situasjonen der vi ønsker å bytte er hvis to tall ligger galt i forhold til hverandre. Derfor introduserer vi også en sammeligningsfunksjon. F.eks. slik:

function sammenlign(t1,t2){
  if(t1 > t2)
    return 1;
  if(t1 < t2)
    return -1;
  return 0;
}

Vi har da introdusert, og implementert, to funksjoner som er nyttige i alle sorteringsalgoritmer. Kjernen i all sortering er sammenligning og ombytting.

Bobling

Den første metoden vi skal se på er den som oftest betegnes som boblesortering. Navnet fordi algoritmen sørger for at de største tallene "bobler opp" og havner i enden av lista. Det er ikke en veldig effektiv sortering, men den er lett å huske, lett å forstå og grei å kontrollere.

function bubbleSort(){
  // det er nok ikke ferdig sortert
  var ok=false;
  while(!ok){ 
    // nå vil jeg teste en hypotese om at det greitt
    ok=true; 
    for(var ix=1; ix < liste.length; ix++)
      if (sammenlign(liste[ix],liste[ix-1]) < 0)
      {
        bytt(ix,ix-1);
        ok=false;
      }
  }
}

Hvis du ser på koden og en animasjon av denne sorteringen er det to tydelige svakheter

1. Små verdier bruker lang tid på å komme på plass, de flyttes bare ett steg i riktig retning i hver gjennomgang.


2. De største verdiene komme raskere på plass. Den største verdien havner så langt opp som den skal i hver gjennomgang, men den sammenlignes med alle tall hver gang

Den første av observasjonene ovenfor lar seg forbedre ved å gå mot høyre og lete etter den største og å gå mot venstre og lete etter den minste, annen hver gang. En implementasjon av dette kalles ofte "shakersort". Vi forfølger ikke dette her.

Den andre observasjonen kan vi korrigere ved å avgrense vår vandring gjennom listen med 1 verdi til høyre for hver gang vi går gjennom løkka. Da kan algoritmen se slik ut:

function bubbleSort2(){
  var ok=false;
  var siste=liste.length-1;
  while(!ok){
    ok=true;
    for(var ix=1; ix <= siste; ix++)
      if (sammenlign(liste[ix],liste[ix-1]) < 0)
      {
        bytt(ix,ix-1);
        ok=false;
      }
    siste--;
  }
}

Velg ut

Her vil vi gå etter den største verdien i hver gjennomgang. Denne algoritmen kalles som regel "selectionsort". Vi vil altså plassere den største verdien vi finner ved siden av den forrige vi fant i enden av søkeområdet, og hver gang kan vi redusere søkeområdet med 1.

Algoritmen kan implementeres slik:

function selectSort(){
   for(var maxIx=liste.length-1; maxIx >= 0; maxIx-- ){
      // finn største tall som ikke er plassert
      var foundIx=0;
      for(var i=0; i <= maxIx; i++)
         if(sammenlign(liste[foundIx],liste[i])<0)            
            foundIx=i;
      //plasser det
      bytt(maxIx,foundIx);
      draw();
   }
}

Hvis du kjører en animasjon ser du at vi flytter bare den som skal til høyre.

Innebygd metode

Javascript, som de fleste andre språk, har en innebygd sorteringsfunksjon for arrays, sort(). Siden arrays kan inneholde mange forskjellige elementer (tall, tekst, objekter) vil det være umulig å lage denne generell. Vi kan kontrollerer det med å gjøre slik som vi gjorde ovefor: vi angir en sammenligningsfunksjon for å angi når to elementer i arrayen skal bytte plass. Denne funksjonen kan vi i Javascript angi som parameter i kallet på sort-funksjonen. Noen eksempler:

Anta følgende kode:

var tallListe=[1,37,2,3,11,12,56,4];
var ordListe=["ingen","hurtigtog","går","til","Ålesund"]

function enkel(L){
  L.sort();
  show(L);
}

function tallSort(L){
  L.sort(function(a,b){return a-b});
  show(L);
}

function sorterEtterOrdLengde(L){
  L.sort(function(a,b){return a.length-b.length});
  show(L);
}

function show(L){
  ...
}

Du kan teste her:

Ulike nettlesere bruker forskjellige sorteringsalgoritmer, og noen bruker ulike algoritmer avhengig av arrayens lengde for å få best mulig effektivitet. Noen av algoritmene er som rimelig kan være mer sofistikerte og effektive enn de som er vist ovenfor.