18 Søke og sortere

Når du søker etter en sang eller ser på en resultatliste, er det en algoritme som finner eller ordner. Her lærer du to måter å søke og to måter å sortere på. Lagre alt du lager i dette kapitlet i mappen kap18-sortere.

18.1 Lineært søk

sok/skript.js
let navn = ["Ola", "Sara", "Amira", "Jonas", "Ali", "Ida"];
let finn = "Jonas";
let funnet = -1;
for (let i = 0; i < navn.length; i++) {
  if (navn[i] === finn) {
    funnet = i;
    break;
  }
}
console.log(`${finn} har indeks ${funnet}.`);
Algoritme
Begynn med «ikke funnet»
For hver verdi i lista, fra starten:
    Hvis verdien er den du leter etter:
        Husk indeksen
        Stopp
Skriv indeksen, eller «ikke funnet»

Et lineært søk sjekker verdiene én etter én, fra starten av lista, til det finner det det leter etter. break stopper løkka med en gang. Finner ikke programmet verdien, er funnet fortsatt -1, på samme måte som indexOf gir -1 når verdien ikke finnes.

  1. Les koden ovenfor, og gjett hva som står i konsollen.
  2. Lag mappen sok med index.html og skript.js, slik du gjorde i 14.1. Skriv koden, og sjekk om du gjettet riktig.
  3. Søk etter «Kari». Hva står i konsollen?
  4. Lag variabelen sjekket, og tell hvor mange navn programmet sjekker før det er ferdig. Hvor mange navn sjekker det når du søker etter «Ola», «Ida» og «Kari»?
  5. Fjern break. Gir programmet det samme svaret? Sjekker det like mange navn?

Algoritmen blir lettere å bruke som en funksjon, slik du lærte i kapittel 17.

sok/skript.js
function lineartSok(liste, verdi) {
  for (let i = 0; i < liste.length; i++) {
    if (liste[i] === verdi) {
      return i;
    }
  }
  return -1;
}
  1. Hvorfor trenger funksjonen verken break eller variabelen funnet?
  2. Legg til funksjonen, og test den i konsollen med lineartSok(navn, "Ali").

18.2 Binærsøk

sok/skript.js
function binaerSok(liste, verdi) {
  let lav = 0;
  let hoy = liste.length - 1;
  while (lav <= hoy) {
    let midt = Math.floor((lav + hoy) / 2);
    if (liste[midt] === verdi) {
      return midt;
    } else if (liste[midt] < verdi) {
      lav = midt + 1;
    } else {
      hoy = midt - 1;
    }
  }
  return -1;
}

let tall = [3, 8, 12, 19, 25, 31, 40, 47, 52, 66, 71, 89];
console.log(binaerSok(tall, 47));

Når lista er sortert, kan du søke mye raskere: Se i midten, og se bort fra halvparten av tallene hver gang. Det kalles binærsøk, og du kjenner det kanskje fra Gjett tallet i oppgave 11.7.

  1. Les koden ovenfor. Hva tror du lav og hoy er? Hva er midt første gang løkka går?
  2. Skriv av tabellen nedenfor, og følg søket etter 47 med papir og blyant. Bruk et stoppunkt i kodelinje 6 til å sjekke svarene.
Runde lav hoy midt liste[midt]
1 0 11 5 31
2
3
4
  1. Hvor mange runder trengte binærsøket? Hvor mange tall ville lineært søk ha sjekket?
  2. Søk etter 20, som ikke finnes. Hva skjer med lav og hoy, og hvorfor stopper løkka?
  3. Bytt om to av tallene i lista, slik at den ikke lenger er sortert. Finn et tall som binærsøket nå ikke finner, selv om det står i lista.

Binærsøk virker bare på en sortert liste. Er lista ikke sortert, kan algoritmen se bort fra den halvparten der verdien står.

18.3 Byttesortering

sortere/skript.js
let poeng = [42, 17, 88, 5, 63];
for (let runde = 0; runde < poeng.length - 1; runde++) {
  for (let i = 0; i < poeng.length - 1; i++) {
    if (poeng[i] > poeng[i + 1]) {
      let mellom = poeng[i];
      poeng[i] = poeng[i + 1];
      poeng[i + 1] = mellom;
    }
  }
}
console.log(poeng);
Algoritme
Gjenta én gang mindre enn antall verdier:
    For hvert par av naboer i lista:
        Hvis den venstre er større enn den høyre:
            Bytt dem
Skriv lista

Byttesortering sammenligner to og to naboer, og bytter dem hvis de står i feil rekkefølge. Algoritmen kalles også boblesortering.

  1. Les koden ovenfor. Skriv lista på papir, og gjør den første runden for hånd. Hvordan ser lista ut etter runden?
  2. Lag mappen sortere med index.html og skript.js. Skriv koden, og sjekk at lista blir sortert.
  3. Legg til console.log(runde, poeng.join(" ")); rett under kodelinje 9. Gjett hvordan lista ser ut etter hver runde, før du kjører programmet.
  4. Endre > til < i kodelinje 4. Hva skjer?
  5. Hvorfor tror du algoritmen også kalles boblesortering?

For å bytte to verdier trenger du en tredje variabel, på samme måte som du trenger et tredje glass for å bytte innholdet i to glass. Nedenfor ser du fire måter å bytte poeng[i] og poeng[i + 1] på. Bare én av dem virker.

Kode A
poeng[i] = poeng[i + 1];
poeng[i + 1] = poeng[i];
Kode B
let mellom = poeng[i];
poeng[i] = poeng[i + 1];
poeng[i + 1] = mellom;
Kode C
let mellom = poeng[i];
poeng[i + 1] = mellom;
poeng[i] = poeng[i + 1];
Kode D
let mellom = poeng[i];
poeng[i] = mellom;
poeng[i + 1] = poeng[i];
  1. Finn kodebiten som bytter verdiene. Hva blir poeng[i] og poeng[i + 1] med hver av de tre andre, når de begynner som 42 og 17?
Spør KI

Forklar byttesortering med et eksempel fra hverdagen, for eksempel elever som stiller seg i rekke etter høyde. Still meg deretter tre spørsmål om algoritmen, ett om gangen.

18.4 Sammenligne algoritmer

sammenligne/skript.js
let liste = [];
for (let i = 1; i <= 1000; i++) {
  liste.push(i * 2);
}

let steg = 0;
for (let i = 0; i < liste.length; i++) {
  steg++;
  if (liste[i] === 1998) {
    break;
  }
}
console.log(`Lineært søk: ${steg} steg`);

To algoritmer kan gi det samme svaret, men bruke svært ulik tid. For å sammenligne dem teller vi steg, for eksempel hvor mange verdier søket sjekker. Lista ovenfor har tusen partall.

  1. Les koden ovenfor. Gjett hvor mange steg det lineære søket bruker.
  2. Lag mappen sammenligne, skriv koden, og sjekk om du gjettet riktig.
  3. Kopier binaerSok fra 18.2, og legg til en variabel som teller hvor mange runder løkka går. Hvor mange steg bruker binærsøket for å finne 1998?
  4. Endre lista til 1 000 000 tall. Hvor mange steg bruker hvert av søkene nå?
Antall verdier Lineært søk, verste fall Binærsøk, verste fall Byttesortering
10 10 4 81
100 100 7 9 801
1 000 1 000 10 998 001
1 000 000 1 000 000 20 omtrent 1 000 000 000 000

Tabellen viser hvor mange steg algoritmene bruker i verste fall.

  1. Legg til en teller i byttesorteringen fra 18.3, og sjekk tallet i den første raden av tabellen.
  2. En datamaskin klarer omtrent en milliard enkle steg i sekundet. Omtrent hvor lang tid tar byttesortering av en million verdier?
  3. Hva skjer med antall steg for binærsøk når lista blir dobbelt så lang? Hva skjer med antall steg for byttesortering?

I praksis bruker du sjelden byttesortering. Nettleseren har innebygde sorteringsalgoritmer som er mye raskere. Men når du forstår en enkel algoritme, er det lettere å forstå hvorfor noen programmer går tregt.

18.5 Sortere med sort

highscore/skript.js
let resultater = [
  { navn: "Amira", poeng: 420 },
  { navn: "Jonas", poeng: 1250 },
  { navn: "Sara", poeng: 880 },
  { navn: "Ali", poeng: 95 },
  { navn: "Ida", poeng: 1010 }
];

resultater.sort(function (a, b) {
  return b.poeng - a.poeng;
});

let html = "";
for (let r of resultater.slice(0, 3)) {
  html += `<li>${r.navn}: ${r.poeng} poeng</li>`;
}
lstHighscore.innerHTML = html;

Lister har en innebygd metode, sort. Når du sorterer tall eller objekter, gir du sort en funksjon som sammenligner to verdier, a og b. b.poeng - a.poeng sorterer med flest poeng først.

  1. Les koden ovenfor. Hvem står øverst i highscorelista, og hvem er ikke med?
  2. Lag mappen highscore med en index.html som har en nummerert liste med id="lstHighscore". Skriv koden, og sjekk om du gjettet riktig.
  3. Endre sammenligningsfunksjonen til return a.poeng - b.poeng;. Hva skjer?
  4. Lag et felt for navn, et felt for poeng og en knapp. Nye resultater skal legges til, og highscorelista skal vises på nytt.

sort uten sammenligningsfunksjon sorterer alt som tekst. Det gir rare svar for tall.

highscore/skript.js
let tall = [100, 25, 9, 1000];
tall.sort();
console.log(tall);
  1. Gjett hva som står i konsollen. Hvorfor kommer 1000 før 25?
  2. Sorter tallene riktig med en sammenligningsfunksjon.
  3. Sorter lista ["Øyvind", "Anne", "Åse", "Ella"] med sort(). Står navnene i riktig norsk rekkefølge? Undersøk a.localeCompare(b, "nb").

Oppsummering

I dette kapitlet har du søkt i lister med lineært søk og binærsøk, og sortert lister med byttesortering og med sort. Du har talt steg for å sammenligne algoritmer, og laget en highscoreliste.

Søke og sortere

highscore/index.html
<ol id="lstHighscore"></ol>

<script>
  let resultater = [
    { navn: "Amira", poeng: 420 },
    { navn: "Jonas", poeng: 1250 },
    { navn: "Sara", poeng: 880 },
    { navn: "Ida", poeng: 1010 }
  ];
  resultater.sort(function (a, b) {
    return b.poeng - a.poeng;
  });
  let html = "";
  for (let r of resultater.slice(0, 3)) {
    html += `<li>${r.navn}: ${r.poeng} poeng</li>`;
  }
  lstHighscore.innerHTML = html;
</script>
Nettleser

Merk deg følgende:

  • Lineært søk virker på alle lister, men må i verste fall sjekke alle verdiene.
  • Binærsøk er mye raskere, men virker bare når lista er sortert.
  • For å bytte to verdier trenger du en tredje variabel.
  • sort() sorterer som tekst. Bruk en sammenligningsfunksjon for tall og objekter.
Kode Betyr
break; stopper løkka med en gang
liste.sort() sorterer som tekst
liste.sort(function (a, b) { return a - b; }) sorterer tall fra minst til størst
liste.sort(function (a, b) { return b.poeng - a.poeng; }) sorterer objekter med flest poeng først
a.localeCompare(b, "nb") sammenligner tekst etter norsk alfabet
liste.slice(0, 3) en ny liste med de tre første verdiene
Algoritme Steg i verste fall for n verdier
Lineært søk omtrent n
Binærsøk omtrent så mange ganger du kan halvere n
Byttesortering omtrent n · n

Oppgaver

Oppgave 18.1

oppg1-rett-feil/skript.js
let tall = [5, 3, 8, 1];
for (let runde = 0; runde < tall.length - 2; runde++) {
  for (let i = 0; i < tall.length - 1; i++) {
    if (tall[i] > tall[i + 1]) {
      tall[i] = tall[i + 1];
      tall[i + 1] = tall[i];
    }
  }
}
console.log(tall);

Byttesorteringen ovenfor har to feil. Finn og rett dem. Bruk console.log inne i løkka for å finne ut hva som skjer.

Oppgave 18.2

  • return -1;
  • }
  • return i;
  • function finnIndeks(liste, verdi) {
  • if (liste[i] === verdi) {
  • }
  • for (let i = 0; i < liste.length; i++) {
  • }

Sett sammen kodelinjene til en funksjon for lineært søk.

Oppgave 18.3

Følg binærsøket etter 8 i lista [3, 8, 12, 19, 25, 31, 40, 47, 52, 66, 71, 89] med papir og blyant. Lag en tabell som i 18.2. Hvor mange runder trengs?

Oppgave 18.4

Lag mappen oppg4-klasseliste med en liste over navnene i klassen din. Vis navnene sortert etter norsk alfabet på siden. Lag også et søkefelt som sier om et navn står på lista.

Oppgave 18.5

Forklar hvorfor binærsøk ikke virker på en liste som ikke er sortert. Lag et eksempel med fem tall.

B-oppgaver

Oppgave 18.6

Byttesorteringen i 18.3 går alltid like mange runder, også når lista blir sortert tidlig. Lag mappen oppg6-raskere, og endre algoritmen slik at den stopper når en hel runde går uten bytter. Tell steg før og etter endringen for en liste som er nesten sortert.

Oppgave 18.7

Lag mappen oppg7-highscore med en highscoreliste som bare viser de ti beste resultatene. Når brukeren legger inn et resultat, skal siden si hvilken plass resultatet fikk, eller at det ikke kom på lista.

Oppgave 18.8

Lag mappen oppg8-biblioteksok med bøkene fra kapittel 16. Brukeren skal kunne sortere tabellen etter tittel, forfatter eller antall sider ved å trykke på en knapp over hver kolonne.

Oppgave 18.9

Undersøk utvalgssortering og performance.now(). Lag mappen oppg9-tidtaking, og mål hvor lang tid byttesortering, utvalgssortering og sort bruker på å sortere 10 000 tilfeldige tall. Vis resultatene i en tabell, og forklar forskjellen.