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.

Introduksjon til grafer

Når vi ønsker på løse et problem er et av de viktigste spørsmålene en kan stille seg hvilken informasjon som er relevant for å løse nettopp dette problemet. Ved å fjerne informasjon man ikke trenger er det ofte lettere å komme til kjernen, den informasjonen som er relevant. I denne posten skal vi se nærmere på en modell som er veldig utbredt, nemlig grafer. En graf består av en mendge noder og en mengde kanter. Nodene blir ofte visualisert som prikker og kantene som streker mellom nodene.

Rendered by QuickLaTeX.com

Grafer kan brukes til å representere alt fra veinett til vennskap. Kanskje har du på et tidspunkt fått tegnet vennskapsgrafen din på et sosialt media? Da vil nodene representere personer og kantene vennskap mellom disse. I noen tilfeller ønsker vi å legge mer informasjon på grafen enn bare hvem som er koblet sammen, for eksempel vil en kant som representerer en vei mellom to kryss være mer interessant for en GPS om den også oppgir lengden på veien, fartsgrenser osv. Og hva med enveiskjørte gater? Dette ordner vi med rettede kanter, kanter som har en startende og en sluttende. I denne posten vil vi dog konsentrere oss om urettede og uvektede grafer; Altså de av typen på figuren ovenfor. Dersom to noder har en kant mellom seg sier vi at de er naboer.

Representasjon på datamaskiner

De to mest brukte representasjonene av en graf på en datamaskin er kalt nabomatrise og naboliste. En nabomatrise er en tabell der hvert element forteller om et spesifikt par med noder har en kant mellom seg eller ikke, mens en naboliste lister alle naboene til hver node i grafen. De har begge sine fordeler og ulemper.

Nabomatrise

Om grafen har n noder vil en nabomatriserepresentasjon være en tabell av størrelse n*n der elementet i rad 0 og kolonne 2 forteller om det er en kant mellom node 0 og node 2 i grafen. Om vi tar en ny titt på eksempelgrafen vår, men gir hver node et nummer kan vi prøve å lage tabellen.

Rendered by QuickLaTeX.com

Nabomatrisen for denne grafen er under. Vi har brukt T (True) for å merke at en kant eksisterer og F (False) for at den ikke er der. Sjekk selv at bare dersom node i og j har en kant mellom seg, så er posisjon i, j (og j, i) T i tabellen.

-  0  1  2  3  4  5
0  F  T  T  T  T  T
1  T  F  T  F  T  T
2  T  T  F  T  T  T
3  T  F  T  F  T  F
4  T  T  T  T  F  F
5  T  T  T  F  F  F

Lese grafen og lagre den i en nabomatrise

Dersom input er en graf er den ofte gitt på følgende format:

n m (to heltall hvor n er antall noder i grafen og m er antall kanter)
m linjer på formen i j (som betyr at det er en kant mellom i og j)

Å lese denne typen input og lagre den i en nabomatrise kan gjøres på følgende måte:

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;

    vector< vector<bool> > graph(n, vector<bool>(n, false));
    for(int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        graph[a][b] = true;
        graph[b][a] = true;
    }

    // Do your stuff

    return 0;
}

Fordeler og ulemper

Fordelen med en nabomatrise er at du på konstant tid (ta en titt på O-notasjon om dette var et ukjent begrep) kan sjekke om to noder er naboer eller ikke. Ufordelen kommer frem om man for eksempel ønsker å liste alle naboene til en node i en graf med “få” kanter. Tenk deg at en node bare har 2 naboer, man må forsatt sjekke hele raden for å finne alle naboene, som tar O(n) tid.

Naboliste

En naboliste er rett og slett en liste over alle nodene, hvor hvert element igjen er en liste med alle naboene til denne noden. På denne måten kan man enkelt iterere over alle naboene til en spesifikk node. Eksempelgrafen vår ville blitt representert på følgende måte:

0: 1, 2, 3, 4, 5
1: 0, 2, 4, 5
2: 0, 1, 3, 4, 5
3: 0, 2, 4
4: 0, 1, 2, 3
5: 0, 1, 2

Lese grafen og lagre den i en naboliste

Gitt input på samme form som for nabomatrisen kan dette gjøres på følgende måte:

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;

    vector< vector<int> > graph(n);
    for(int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    // Do your stuff

    return 0;
}

Fordeler og ulemper

Når vi ønsker å se på alle d naboene til en node kan vi gjøre dette i O(d) tid i stedet for O(n). Dette vil spille en stor rolle angående kjøretid når vi skal se på bredde-først-søk og dybde-først-søk. Ufordelen er at vi også bruker O(d) tid på å sjekke om to noder er naboer.

Nå har du lært litt om hvordan man kan lagre en graf på en datamaskin. I de neste postene skal vi ta for oss bredde-først-søk og dybde-først-søk, to algoritmer som du kan anvende på grafer for forskjellige formål.

Komme i gang med C++, del 1: Installasjon av utviklingsmiljø

Også tilgjengelig på NIOs hovedside.

Windows

Vi anbefaler at du installerer Microsoft Visual C++ 2010 Express. Klikk på “Visual C++ 2010 Express”-linjen og deretter på “Install now” – da får du laste ned en liten fil som heter vc_web.exe. Kjør denne filen når den er lastet ned, og svar “Ja” eller “Fortsett” hvis du blir spurt om programmet får lov til å gjøre endringer på datamaskinen. For at du skal få installert Visual Studio må Windows-brukeren din være administrator eller du må ha et administratorpassord. Hvis du har en skolemaskin som du ikke er administrator på, spør systemansvarlig på skolen om de kan installere det for deg. Merk at du må være koblet til internett mens du installerer.

  • Hvorvidt du krysser av for “Yes, send information about my setup experiences to Microsoft Corporation” når installasjonsprogrammet starter er ikke viktig.
  • Velg “I have read and accept the license terms” (du kan lese hele betingelsesteksten hvis du vil, men den inneholder ikke noe skummelt).
  • Ikke velg å installere SQL Server 2008 Express (med mindre du har lyst til å lære deg å programmere mot databaser, noe som er kult, men ikke nyttig for NIO).
  • Behold den foreslåtte installasjonsmappen (C:\Program Files\Microsoft Visual Studio 10.0\), trykk Install, og finn på noe annet mens nedlastingen og installasjonen pågår. Trykk på Exit når installasjonen er ferdig.

Når installasjonen er ferdig, gå til Start-menyen og velg “Microsoft Visual Studio 2010 Express” -> “Microsoft Visual C++ 2010 Express” (dette ligger under “Programmer”/”Programs” hvis du har Windows XP). Første oppstart tar lengre tid enn vanlig. Klikk på “New Project…”, velg “Win32 Console Application”, og fjern krysset for “Create directory for solution”. Velg en (ny) mappe hvor du vil putte koden din, f.eks. E:\Programmer.

Når du klikker OK dukker “Win32 Application Wizard” opp. Velg “Application Settings” ute til venstre, la det stå på “Console application” og kryss av for “Empty project”. Klikk Finish.

Nå skal det se sånn ut:

Vi må nå legge til en kildekodefil. Høyreklikk på “Source Files”-mappen i “Solution Explorer”-vinduet ute til venstre og velg “Add” -> “New Item…”, velg “C++ File (.cpp)” og kall filen f.eks. main.cpp:

Skriv inn koden nedenfor eksakt slik den står her:

#include <iostream>

using namespace std;

int main() {
    cout << "Hello world!" << endl;
    cin.get();
    return 0;
}

Trykk enten F5 på tastaturet eller klikk på knappen med den grønne pilen for å starte programmet. Første gang du gjør dette vil du bli spurt om “This project is out of date. Would you like to build it?” Kryss av for “Do not show this dialog again” og klikk “Yes”. Nå burde et såkalt konsollvindu dukke opp og vise teksten “Hello world!”:

Gratulerer; du har skrevet og kjørt ditt første C++-program! Trykk Enter, så forsvinner vinduet og programmet avslutter. Det var litt strevsomt å komme i gang, men når Visual Studio og prosjektet først er oppe, kan man konsentrere seg om kodingen. Hvis du ikke har programmert før, skal vi snart publisere en kom i gang-guide for det også.

Hvis du skriver feil i koden, vil det sannsynligvis dukke opp en rød strek i nærheten, og når du prøver å kjøre programmet, vil du første gang få en melding om “There were build errors. Would you like to continue and run the last successful build?” Kryss av for “Do not show this dialog again” og klikk “No”. Gå til “View”-menyen og velg “Other Windows” -> “Error List” og klikk på “Errors”-knappen i vinduet som dukker opp, så får du en liste over feil.

Hvis du vil lage et nytt program, går det an å starte en ny utgave av Visual Studio og lage et nytt prosjekt med et annet navn. Men dette er litt strevsomt, så det kan være enklere å bruke det samme prosjektet, og bare sette inn en annen kildekodefil i stedet. Høyreklikk på main.cpp i Solution Explorer-vinduet og velg “Exclude From Project”. (Filen blir ikke slettet; den vil forsvinne fra prosjektet, men vil fortsatt ligge på E:\Programs\HelloWorld\main.cpp.) Nå kan du legge til en ny kildekodefil med et annet navn (kildekodefilene kan hete hva som helst, men det skal alltid stå int main() i koden). Hvis du vil ha main.cpp tilbake, kan du høyreklikke på “Source Files” og velge “Add” -> “Existing Item”. Men det går ikke an å ha flere kildekodefiler med main() i prosjektet samtidig.

Mac

På Mac anbefaler vi å laste ned “Command Line Tools for XCode” herfra: https://developer.apple.com/downloads/ (man må registrere seg for å få tilgang). Når du har registrert deg, søker du etter “command line tools” og velger nyeste utgave for din versjon av OS X som vist på bildet.

Når den er lastet ned åpner du .dmg-filen og starter installasjonsprogrammet.

Du trenger ikke endre noe i prosessen.

For å prøve om installasjonen var vellykket åpner du Terminal (CMD+SHIFT og skriv inn “Terminal”) og så skriver du kommandoen:

g++ --version

Resultatet bør se omtrent slik ut:

Nå er du klar for å kompilere kode! Åpne en ren tekst editor, f.eks GEdit (om du ikke allerede har en favoritteditor, er dette et godt valg, siden den er lett å lære og er tilgjengelig under finalen i Bergen og i de internasjonale rundene).

Du kan nå kopiere koden fra http://www.cplusplus.com/doc/tutorial/program_structure/ inn i filen, lagre den som f.eks helloworld.cpp og kompilere:

g++ helloworld.cpp -o helloworld

Hvis alt gikk bra, fikk du ingen feilmeldinger.

Da kan du også kjøre programmet med kommandoen

./helloworld

Nå ser du at programmet har skrevet ut teksten “Hello World!” på kommandolinjen. Da er alt satt opp!

Linux

All programvaren du trenger følger sannsynligvis med din Linux-distribusjon og er allerede installert. Følg instruksjonen for Mac fra stedet med kommandoen:

g++ --version