Sortering og binærsøk

Sortering og søk er nært knyttet til hverandre. Om bøkene i bokhyllen din er plassert i helt tilfeldig rekkefølge, er det vanskelig å finne akkurat den boken du leter etter, spesielt hvis du har mange bøker. Om bøkene derimot er sortert alfabetisk etter tittel, er jobben enkel. Men er det verdt arbeidet å sortere hele bokhyllen for lett å finne bøker? Svaret avhenger av hvor ofte du trenger å finne en bestemt bok.

 Sortering

Hvor mye arbeid er det egentlig å sortere en samling med N elementer? Det kommer an på hvordan vi utfører jobben, altså hvilken sorteringsalgoritme vi bruker. Vi skal se på to sorteringsalgoritmer, der den ene er svært mye mer effektiv enn den andre når antallet elementer er høyt.

Insertion sort

En intuitiv måte å sortere bokhylla på er å ta alle bøkene ut av hylla og legge dem i en stabel på gulvet. Så tar vi den boka som ligger øverst i stabelen og setter inn i hylla på riktig sted. Siden det ikke er noen bøker i hylla, setter vi den første boka lengst til venstre på hylla. Den neste boka i stabelen må vi finne riktig plass til, så vi sammenligner tittelen med boka som allerede står i hylla. Er den tidligere i alfabetet, setter vi den til venstre. Er den senere i alfabetet, setter vi den til høyre.

Slik fortsetter vi så lenge det er bøker i stabelen: Vi tar boka som ligger øverst i stabelen, sammenligner med boka lengst til høyre i bokhylla. Hvis tittelen på boka fra stabelen er senere i alfabetet enn tittelen på boka fra hylla, setter vi boka til høyre. Hvis ikke, flytter vi boka vi sammenlignet med en plass til høyre og gjør samme sammenligning med boka ett steg lenger til venstre i hylla.

Du kjenner kanskje igjen denne algoritmen fra oppgave 15 i innledende runde 2012/2013.

Hvis vi har N bøker, må vi i verste fall gjøre N * (N – 1) / 2 sammenligninger. Dette inntreffer hvis stabelen tilfeldigvis er sortert i omvendt rekkefølge av den vi ønsker. Vi sier at algoritmen har asymptotisk tidskompleksitet O(N^2) (ta en titt på O-notasjon om dette var et ukjent begrep).

Du tenker kanskje at det er unødvendig å sammenligne med alle bøkene i hylla en etter en, og vil heller bruke binærsøk for å hoppe raskt til stedet der boka fra stabelen skal settes inn. I dette tilfellet tjener vi ikke noe på den asymptotiske tidskompleksiteten, siden vi fortsatt er nødt til å flytte alle bøkene til høyre for der den nye boka skal settes inn.

Merge sort

Det er ikke nødvending å kunne detaljene i denne algoritmen, men siden tankegangen går igjen mange steder anbefaler vi likevel at du prøver å sette deg inn i den. Det er dog svært nyttig å vite at det finnes sorteringsalgoritmer med tidskompleksitet O(N lg N) og hvordan du benytter disse i C++.

Når antallet elementer N blir stort, er N^2 et problem. Tenk om vi f.eks skal sortere en million elementer. Da vil selv en maskin som kan gjøre ca. 1 milliard operasjoner i sekundet holde på i 1000 sekunder. Og ofte vil vi sortere enda mange flere elementer.

Merge sort er et eksempel på en divide and conquer algoritme. Slike algoritmer deler opp problemet man ønsker å løse i mindre delproblemer som er enklere å løse. I tilfellet med merge sort deles arrayet man ønsker å sortere i to, og man sitter igjen med to sorteringsproblemer med mindre størrelse. Dette kan man gjøre rekursivt, helt til man sitter igjen med sorteringsproblemer med kun ett element. Et array med ett element er jo uansett sortert.

Så gjenstår bare å sette sammen løsningene fra delproblemene til en løsning for det større problemet. Vi må ta to sorterte arrays fra hvert delproblem og sette dem sammen til et sortert array. Dette kan gjøres med et antall operasjoner som er proporsjonalt med antallet elementer i de to arrayene, ved hele tiden å holde styr på hvilket element fra hver av de to arrayene som er det minste som ikke har blitt satt inn i det nye felles-arrayet.

Kompleksiteten til merge sort er O(N lg N). Dette kommer av at det er lg N (toerlogaritmen til N) “nivåer” i rekursjonen, og på hvert nivå er det N elementer som skal prosesseres. Analysen og mer om merge sort finner du her. Skal vi sortere en million elementer trenger vi altså et antall sammenligninger som er i størrelsesorden N lg N, altså ca. 20 millioner. Dette er trivielt sammenlignet med de 1000 milliarder operasjonene den forrige algoritmen bruker.

Det finnes mange flere sorteringsalgoritmer! Her finner du en liste over noen av de mest populære.

Sorteringsbiblioteket i C++

Du får tilgang til sorteringsbiblioteket i C++ ved å inkludere algorithm:

#include <algorithm>

Hvis du vil sortere en array (vi anbefaler at du alltid bruker vector i stedet for array), kan du gjøre som i dette korte programmet:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> tall(n);
  for (int i = 0; i < n; ++i) {
    cin >> tall[i];
  }

  sort(tall.begin(), tall.end());  // Sorter tallene stigende

  for (int i = 0; i < n; ++i) {
    cout << tall[i] << " ";
  }
  cout << endl;

  return 0;
}

Den sorteringsalgoritmen som C++ benytter har kompleksitet O(N lg N).

Binærsøk

I første runde spurte vi hvor mange gjetninger du trenger for å finne et tall mellom 1 og 100 (inklusive) når du hver gang får vite om du gjettet for høyt, lavt eller riktig. Dette er et eksempel på binærsøk, som er en svært viktig algoritme.

Hvis vi kommer til en bokhylle med N bøker som allerede er sortert på tittel, kan vi finne den bestemte tittelen vi er ute etter med O(lg N) operasjoner (et antall som er proporsjonalt med toerlogaritmen til N). Vi gjør dette på samme måte som i oppgaven med å gjette riktig tall, nemlig ved å hele tiden gjette midt i intervallet. Når vi gjetter for høyt (eller alfabetisk etter det vi søker etter), søker vi videre i det lavere intervallet, og omvendt om vi gjetter for lavt.

Et typisk binærsøk i en mengde kan se slik ut:

int find_binary(vector<int> N, int x) {
  int a = 0, b = N.size();  // Nedre og oevre grense for det vi leter etter
  while (b - a > 1) {
    int g = (b+a)/2;
    if (N[g] > x) {
      b = g;
    } else {
      a = g;
    }
  }
  if (N[a] == x) return a;
  else return N.size();
}

Denne koden finner en indeks til verdien x i et sortert array. Hvis verdien x ikke finnes, returneres en ugyldig indeks (en mer enn bakerste element).

Tilsvarende kode kan brukes til å søke i arrays med andre typer verdier, f.eks strings, eller til å søke etter reelle tall (uten at disse nødvendigvis befinner seg i et array). Et eksempel på bruk av binærsøk til å finne et reelt tall uten array, er oppgave 2 fra inntaksrunden i 2011/2012.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>