1.3.1  Permutasjoner
En samling verdier kan settes opp i en rekkefølge. Hver slik rekkefølge utgjør en permutasjon av verdiene. En samling på n ulike verdier kan permuteres på n! (n fakultet) ulike måter. Det betyr at antallet forskjellige permutasjoner vokser svært fort når n vokser:

             2!  =  2
             3!  =  6
             4!  =  24
             5!  =  120
             6!  =  720
            10!  =  3.628.800
            20!  =  2.432.902.008.176.640.000

I Avsnitt 1.1.8 så vi på teknikker for å lage tilfeldige permutasjoner av tallene fra 1 til n. De er nyttige i forbindelse med testing av algoritmer. Men det vil også være situasjoner der det er ønskelig å få tilgang til alle permutasjonene. Vi skal her se på en teknikk som genererer samtlige permutasjoner i leksikografisk (eng: lexicographic) rekkefølge.

Definisjon 1.3.1   Gitt to permutasjoner p og q av tallene fra 1 til n

Eksempel 1.3.1: Gitt flg. to permutasjoner p og q av tallene fra 1 til 10:

      p  =  3 1 4 9 5 2 6 8 7 10       q  =  3 1 4 9 7 10 8 6 5 2

De fire første tallene er like i p og q. Det femte tallet i p (dvs. 5) er mindre enn det femte i q (dvs. 7). Dermed er p mindre enn q leksikografisk. Spesielt får vi at 1 2 3 4 5 6 7 8 9 10 er leksikografisk sett den første (minste) og at 10 9 8 7 6 5 4 3 2 1 er den siste (største) blant permutasjonene av tallene fra 1 til 10.

Spørsmål: Hvis en permutasjon er gitt, hva blir da den neste leksikografisk sett? Vi ser først på noen enkle tilfeller og deretter på et som er mer generelt. Vi starter med flg. permutasjon av tallene fra 1 til 10:

Hvis det siste tallet er større enn det nest siste (tallene 6 og 2 i Figur 1 over), får vi den neste i leksikografisk rekkefølge ved å bytte om de to. Med andre ord denne permutasjonen:

I Figur 2 er nå det siste tallet mindre enn det nest siste. Da nytter det ikke å bytte om dem. Vi må isteden trekke inn de tre siste tallene. De kan permuteres i leksikografisk rekkefølge på flg. seks måter: 2 5 6 ,  2 6 5 ,  5 2 6 ,  5 6 2 ,  6 2 5  og  6 5 2. Her ser vi at det er 6 2 5 som kommer etter 5 6 2. Dermed blir dette neste permutasjon:

I Figur 3 har vi igjen den situasjonen at det siste tallet er større enn det nest siste. Dermed får vi neste permutasjon ved å bytte om de to:

Figur 4 viser et mer generelt tilfelle. Der er de fem siste tallene sortert avtagende. Generelt gjør vi slik for å finne den neste: Start bakerst og gå mot venstre så lenge som det er sortert. Dvs. vi skal stoppe på første tall som bryter sorteringen. I Figur 4 er det tallet 7 (markert med en x). Neste skritt er: Bytt dette tallet med det minste av de til høyre som er større. I Figur 4 er tallet 8 det minste av de til høyre for 7 som er større enn 7. Snu så alle tallene til høyre for posisjon x. Dermed blir flg. permutasjon den som leksikografisk kommer etter den i Figur 4:

Beskrivelsen over sier at to tall skal bytte plass. Vi har tidligere laget metoden bytt() for det. Den må du ha i samleklassen Tabell. Det er også nødvendig å kunne snu rekkefølgen på et intervall av verdier. Det er noe som det også vil være behov for andre steder. Vi lager derfor hjelpemetoder. De må legges i samleklassen Tabell:

  public static void snu(int[] a, int v, int h)  // snur intervallet a[v:h]
  {
    while (v < h) bytt(a, v++, h--);
  }

  public static void snu(int[] a, int v)  // snur fra og med v og ut tabellen
  {
    snu(a, v, a.length - 1);
  }

  public static void snu(int[] a)  // snur hele tabellen
  {
    snu(a, 0, a.length - 1);
  }
              Programkode 1.3.1 a)

Beskrivelsen i tilknytning til Figur 4 og Figur 5 over kan oversettes til følgende metode. Den skal ligge i samleklassen Tabell:

  public static boolean nestePermutasjon(int[] a)
  {
    int i = a.length - 2;                    // i starter nest bakerst
    while (i >= 0 && a[i] > a[i + 1]) i--;   // går mot venstre
    if (i < 0) return false;                 // a = {n, n-1, . . . , 2, 1}

    int j = a.length - 1;                    // j starter bakerst
    while (a[j] < a[i]) j--;                 // stopper når a[j] > a[i] 
    bytt(a,i,j); snu(a,i + 1);               // bytter og snur

    return true;                             // en ny permutasjon
  }
              Programkode 1.3.1 b)

Algoritmen i Programkode 1.3.3 b) er ineffektiv hvis n er stor. Fordelen er imidlertid at vi får generert én og én permutasjon. Vi ser på andre og mer effektive teknikker i Avsnitt 1.5.5.

Flg. eksempel viser hvordan metoden nestePermutasjon kan brukes:

  int[] a = {3,1,4,9,7,10,8,6,5,2};        // permutasjon av tallene fra 1 til 10
  Tabell.nestePermutasjon(a);              // lager neste permutasjon
  System.out.println(Arrays.toString(a));  // [3, 1, 4, 9, 8, 2, 5, 6, 7, 10]

              Programkode 1.3.1 c)

En anvendelse  Setning 1.1.6 a) i Avsnitt 1.1.6 sier at i en tilfeldig permutasjon av tallene fra 1 til n, vil det gjennomsnittlig være 1/2 + 1/3 + . . + 1/n = H_n − 1 av dem som er større enn det største av tallene foran. Oppgave 1 i det avsnittet gikk ut på å verifisere dette for n = 5. Vi har at 1/2 + . . + 1/5 = 154/120. Hvis vi for hver av de 5! = 120 permutasjonene teller opp de tallene i permutasjonen som er større enn det største av de foran, skal vi sammenlagt få 154. Dette kan sjekkes ved å la metoden nestePermutasjon generere alle permutasjonene og så la metoden antallMaks telle opp. Se også Oppgave 4.

  int[] a = {1,2,3,4,5};                // første permutasjon
  int sum = 0;                          // hjelpevariabel

  do { sum += antallMaks(a); }          // se Programkode 1.1.9 a)
  while (Tabell.nestePermutasjon(a));   // lager neste permutasjon

  System.out.println(sum);              // Utskrift: 154

                Programkode 1.3.1 d)

  Oppgaver til Avsnitt 1.3.1

  1.3.2  Inversjoner og sortering
Gitt flg. permutasjon av tallene fra 1 til 10:

      1  2  4  3  6  7  9  5  8  10

Vi ser øyeblikkelig at tallene ikke er sortert. F.eks. er tallparene (4,3) og (6,5) i utakt. Et annet navn på det å være i utakt er en inversjon. Det gir oss flg. definisjon:

Definisjon 1.3.2 a)  Inversjoner

Spørsmål: Hvor mange inversjoner er det i permutasjonen 1  2  4  3  6  7  9  5  8  10 ? Dette kan vi finne ut slik: Gå for hvert tall x, videre mot høyre og se om det kommer et (eller flere) tall y som er mindre enn x. Det gir flg. inversjoner: (4 , 3), (6 , 5), (7 , 5), (9 , 5) og (9 , 8). Med andre ord fem inversjoner.

Vi kan bruke idéen over til å lage en metode som teller opp inversjonene (en mer effektiv teknikk tas opp i Avsnitt 1.3.12). Den skal ligge i samleklassen Tabell:

  public static int inversjoner(int[] a)
  {
    int antall = 0;  // antall inversjoner
    for (int i = 0; i < a.length - 1; i++)
    {
      for (int j = i + 1; j < a.length; j++)
      {
        if (a[i] > a[j]) antall++;  // en inversjon siden i < j
      }
    }
    return antall;
  }
                Programkode 1.3.2 a)

Flg. eksempel viser hvordan metoden kan brukes:

  int[] a = {1,2,4,3,6,7,9,5,8,10};
  System.out.println(Tabell.inversjoner(a));  // Utskrift: 5

                Programkode 1.3.2 b)

Nå ser vi generelt på permutasjoner av tallene fra 1 til n. Hvis en permutasjon er sortert stigende, vil det være null inversjoner. Også det omvendte gjelder. Hvis en permutasjon av tallene fra 1 til n ikke inneholder noen inversjoner, så er tallene sortert stigende. Dette gir oss flg. generelle definisjon:

Definisjon 1.3.2 b)  Sortering

Det er heldigvis enklere å avgjøre om en rekkefølge av verdier er sortert enn å bruke definisjonen over. Det holder å sjekke naboverdier. Den er sortert hvis ingen par (x , y) av naboverdier utgjør en inversjon. Hvis verdiene ligger i en tabell, får vi flg. enkle metode:

  public static boolean erSortert(int[] a)  // legges i samleklassen Tabell
  {
    for (int i = 1; i < a.length; i++)      // starter med i = 1
      if (a[i-1] > a[i]) return false;      // en inversjon

    return true;
  }
                Programkode 1.3.2 c)

Legg merke til at metoden erSortert() er av orden n. Det er det beste vi kan oppnå for den oppgaven. Flg. eksempel viser hvordan den kan brukes:

  int[] a = {}, b = {5}, c = {1,2,4,3,6,7,9,5,8,10};  // heltallstabeller
  int[] d = {1,2,3,4,5,6,7,8,9,10};                   // heltallstabell

  boolean x = Tabell.erSortert(a), y = Tabell.erSortert(b);
  boolean z = Tabell.erSortert(c), u = Tabell.erSortert(d);

  System.out.println(x + " " + y + " " + z + " " + u);

  // Utskrift: true true false true   

                Programkode 1.3.2 d)

Legg merke til at vi får true både for en tom tabell og for en med kun ett element. Det er slik det skal være. Det er vanlig å si at en rekkefølge med ingen verdier eller én verdi, er sortert.

Antall inversjoner kan brukes til å si noe om hvor sortert eller eventuelt hvor usortert en permutasjon av tallene fra 1 til n er. Hvis det ikke er noen inversjoner, så er den sortert (stigende). Men når er det flest mulig inversjoner? Det er når permutasjonen er sortert motsatt vei, dvs. avtagende. Med n = 10 får vi 10 9 8 7 6 5 4 3 2 1. Det er 9 par med 10 først, dvs. (10,9), (10,8), . . , (10,1), så 8 par med 9 først, osv. Alle de 45 parene utgjør da inversjoner. Generelt blir det n(n − 1)/2 stykker hvis tallene fra 1 til n er sortert avtagende.

Men hvor mange inversjoner er det i gjennomsnitt i en permutasjon av tallene fra 1 til n ? Ytterpunktene er 0 og n(n − 1)/2. Det er mange tilfeller der et gjennomsnitt ikke er midt mellom ytterpunktene, men her er det slik. Hvis vi tar en vilkårlig permutasjon, vil den ha k inversjoner. I den omvendte permutasjonen vil alle ikke inversjoner bli inversjoner og omvendt. Det betyr at den omvendte permutasjonen har n(n − 1)/2 − k inversjoner og dermed n(n − 1)/4 som gjennomsnitt for de to. Slik blir det for enhver permutasjon. Dermed blir gjennomsnittet over alle permutasjonene lik n(n − 1)/4.

Observasjon 1.3.2  Antall inversjoner

En anvendelse: Hvis en skal tippe resultatet i en konkurranse med mange deltagere, kan en si at den som kommer «nærmest» det korrekte, har det beste tipset. Men hva er «nærmest»? Det kan f.eks. være færrest inversjoner i tippingen. Mer om det i Avsnitt 1.3.12.

  Oppgaver til Avsnitt 1.3.2

  1.3.3  Boblesortering
Gitt at vi har en tabell a som inneholder en permutasjon av tallene fra 1 til n. Den vil (hvis den ikke er sortert stigende) inneholde et antall inversjoner. I flg. metode sammenlignes to og to naboverdier og de bytter plass hvis de danner en inversjon. Til slutt returneres antallet ombyttinger. Hvis vi tenker oss at tabellen står vertikalt, vil store verdier «bobles» oppover (bobler som i en vannkjele som koker). Derav navnet. Metoden bytt(), som inngår i koden, har vi laget tidligere.

  public static int boble(int[] a)      // legges i samleklassen Tabell
  {
    int antall = 0;                     // antall ombyttinger i tabellen
    for (int i = 1; i < a.length; i++)  // starter med i = 1 
    {
      if (a[i - 1] > a[i])              // sammenligner to naboverdier
      {
        bytt(a, i - 1, i);              // bytter om to naboverdier
        antall++;                       // teller opp ombyttingene
      }
    }
    return antall;                      // returnerer
  }
                Programkode 1.3.3 a)

Hvis Programkode 1.3.3 a) (og metoden bytt()) ligger i samleklassen Tabell, vil flg. kodebit kunne kjøres:

  int[] a = {5, 9, 6, 10, 2, 7, 3, 8, 4, 1};          // en heltallstabell
  System.out.println(Arrays.toString(a));             // skriver ut tabellen

  int antInv = Tabell.inversjoner(a);                 // Programkode 1.3.2 a)
  System.out.println("Inversjoner: " + antInv);       // skriver ut

  int antOmb = Tabell.boble(a);                       // ombyttinger
  antInv = Tabell.inversjoner(a);                     // Programkode 1.3.2 a)

  System.out.println(Arrays.toString(a));             // skriver ut tabellen
  System.out.print("Ombyttinger: " + antOmb + "  ");  // ombyttinger
  System.out.println("Inversjoner: " + antInv);       // inversjoner

  // Utskrift:
  // [5, 9, 6, 10, 2, 7, 3, 8, 4, 1]
  // Inversjoner: 29
  // [5, 6, 9, 2, 7, 3, 8, 4, 1, 10] 
  // Ombyttinger: 7  Inversjoner: 22

                Programkode 1.3.3 b)

Utskriften over viser at tabellen a i utgangspunktet har 29 inversjoner. I metoden boble() blir det utført 7 ombyttinger og siden hver ombytting fjerner en inversjon, vil tabellen etterpå ha 29 - 7 = 22 inversjoner. Tabellen a er fortsatt langt fra å være sortert, men det går den rette veien. Vi ser også at den største verdien (dvs. 10) har kommet bakerst. Slik vil det alltid bli. Hvis den største ikke hadde kommet bakerst, ville den hatt en nabo til høyre for seg som var mindre. Men det er umulig. De to ville i så fall ha byttet plass i løpet av boble-prosessen.

I flg. kode starter vi med samme tabell (permutasjon) som i Programkode 1.3.3 b). Men nå kaller vi boble() flere ganger. Poenget er å få redusert antallet inversjoner ytterligere:

  int[] a = {5, 9, 6, 10, 2, 7, 3, 8, 4, 1};

  for (int i = 1; i < a.length; i++)
  {
    int antall = Tabell.boble(a);  // antall ombyttinger
    System.out.println(i + ". " + Arrays.toString(a) + " " + antall);
  }
  // Utskrift:
  1. [5, 6, 9, 2, 7, 3, 8, 4, 1, 10] 7
  2. [5, 6, 2, 7, 3, 8, 4, 1, 9, 10] 6
  2. [5, 2, 6, 3, 7, 4, 1, 8, 9, 10] 4
  4. [2, 5, 3, 6, 4, 1, 7, 8, 9, 10] 4
  5. [2, 3, 5, 4, 1, 6, 7, 8, 9, 10] 3
  6. [2, 3, 4, 1, 5, 6, 7, 8, 9, 10] 2
  7. [2, 3, 1, 4, 5, 6, 7, 8, 9, 10] 1
  8. [2, 1, 3, 4, 5, 6, 7, 8, 9, 10] 1
  9. [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 1

                Programkode 1.3.3 c)

Det å gå gjennom tabellen kalles en gjennomgang (eng: pass). I koden over det det 9 stykker. Utskriften viser at det startet med 7 ombyttinger, så 6, osv. Tilsammen 7 + 6 + 4 + 4 + 3 + 2 + 1 + 1 + 1 og det blir som forventet 29. Den siste utskriften viser at det er sortert. Denne teknikken kalles boblesortering (eng: bubble sort). Vi kunne ha kodet den slik:

  public static void boblesortering(int[] a)
  {
    for (int i = 1; i < a.length; i++) boble(a);
  }
                Programkode 1.3.3 d)

Dette vil virke, men er unødvendig ineffektivt. F.eks. vil boble() gå gjennom hele tabellen hver gang. Men det er nødvendig kun første gang. Da kommer den største verdien bakerst. Neste gang kan vi stoppe én før. Det vil føre til at den nest største verdien komme nest bakerst, osv. I flg. versjon gjøres sammenligningene direkte i koden og kun bytt() brukes som hjelpemetode. Dette kalles standardversjonen av boblesortering:

  public static void boblesortering(int[] a)     // hører til klassen Tabell
  {
    for (int n = a.length; n > 1; n--)           // n reduseres med 1 hver gang
    {
      for (int i = 1; i < n; i++)                // går fra 1 til n
      {
        if (a[i - 1] > a[i]) bytt(a, i - 1, i);  // sammenligner/bytter
      }
    }
  }             Programkode 1.3.3 e)

Algoritmeanalyse: La a inneholde en permutasjon av tallene fra 1 til n. Vi må finne ut hvor mange sammenligninger av typen a[i - 1] > a[i] som utføres og så hvor mange kall på bytt() (dvs. ombyttinger) det er. I første gjennomgang blir det n − 1 sammenligninger. Så reduseres n. Det betyr at i neste gjennomgang blir det n − 2 stykker, osv. til 1 i siste. Summen blir (den aritmetiske rekken 1 + 2 + . . . + n − 1) lik n(n − 1)/2. Dette er helt uavhengig av hva tabellen inneholder. Med andre er denne versjonen av boblesortering av kvadratisk orden. I algoritmeanalyse skiller vi normalt mellom hvilken orden en metode har i det verste tilfellet og i gjennomsnitt. Noen ganger ser vi også på det beste tilfellet. Men her blir det kvadratisk orden i alle tilfellene siden det alltid blir n(n − 1)/2 sammenligninger.

Det utføres nøyaktig like mange ombyttinger som det er inversjoner. Det betyr at i det beste tilfellet (sortert stigende) blir det ingen ombyttinger. I det verste tilfellet (sortert avtagende) blir det n(n − 1)/2 og i gjennomsnitt n(n − 1)/4 stykker. Se Avsnitt 1.3.2.

Programkode 1.3.3 c) viser hva som skjer med permutasjonen 5, 9, 6, 10, 2, 7, 3, 8, 4, 1 når boble() kalles gjentatte ganger. Det blir flest ombyttinger i første gjennomgang (7 stykker). Men hvor mange det blir i gjennomsnitt i hver gjennomgang? Vi starter med den første. Hvis det er sortert stigende, blir det ingen ombyttinger. I boble() blir en «stor» verdi, ved hjelp av ombyttinger, flyttet mot høyre. Men hvis det så kommer en verdi som er enda større, blir det ingen ombytting. Da er det isteden den som flyttes videre mot høyre. Med andre ord blir det ingen ombytting når det kommer en verdi som er større enn verdiene foran (til venstre for den). I Avsnitt 1.1.6 fant vi at med n forskjellige verdier, vil i gjennomsnitt H_n − 1 av dem være større enn de foran. Det maksimale antallet er n − 1. Trekker vi fra de tilfellene det ikke blir ombyttinger, får vi n − H_n som gjennomsnitt. Med n = 10 blir det 7,07.

Det kan videre vises at i gjennomgang nr. k der k går fra 1 til n − 1, blir det i gjennomsnitt utført n + k (H_k − H_n − 1) ombyttinger. Etter alle gjennomgangene vil alle inversjoner ha blitt fjernet. Med n forskjellige verdier er det i gjennomsnitt n(n − 1)/4 inversjoner. Dermed:

Formel 1.3.3 a)

Mulige forbedringer: Tall etter siste ombytting i en gjennomgang vil ligge på rett plass og være sortert. Ta 4, 3, 1, 2, 7, 5, 6, 8, 9, 10 som eksempel. Her vil først 4 og 3 bytte plass, så 4 og 1 og så 4 og 2. Deretter 7 og 5 og så 7 og 6. Men ingen etter det. Det gir dette: 3, 1, 2, 4, 5, 6, 7, 8, 9, 10. Dvs. sortert fra og med 4. Dette oppdages i neste gjennomgang. Vi gjør flg. endringer i Programkode 1.3.3 e):

  public static void boblesortering(int[] a)
  {
    for (int n = a.length; n > 1; )            // n er intervallgrense
    {
      int byttindeks = 0;                      // hjelpevariabel
      for (int i = 1; i < n; i++)              // går fra 1 til n 
      {
        if (a[i - 1] > a[i])                   // sammenligner
        {
          bytt(a, i - 1, i);                   // bytter  
          byttindeks = i;                      // høyre indeks i ombyttingen
        }
      }
      n = byttindeks;                          // ny intervallgrense
    }
  }             Programkode 1.3.3 f)

Ulempen med koden over er at det er introdusert en ekstra kostnad knyttet til en ombytting (dvs. en oppdatering av byttindeks). Det kan hende den delvis oppveier fordelen med færre gjennomganger. Se Oppgave 2. Men en fordel er at hvis tabellen er sortert, vil algoritmen stoppe etter første gjennomgang. Dermed får den lineær orden (orden n) i dette tilfellet. Men den har fortsatt kvadratisk orden (orden n²) både i gjennomsnitt og i det verste tilfellet.

Hvor mange gjennomganger trengs i gjennomsnitt? La tabellen inneholde en permutasjon av tallene fra 1 til n. Hvis den er sortert stigende, trengs ingen gjennomgang (bortsett fra den som avgjør at den er sortert). Hvis den er sortert avtagende, blir det n − 1 gjennomganger. I gjennomsnitt er det mer komplisert. Formelen a(k,n) = k!kn-k (se [S & F]) gir antall som blir sortert etter maks k − 1 gjennomganger. Vi får f.eks. a(1,10) = 1, a(2,10) = 512 og a(3,10) = 13122. Dermed 512 - 1 = 511 permutasjoner der det trengs nøyaktig én gjennomgang. Videre 13122 - 512 = 12610 der det trengs nøyaktig to gjennomganger. Det er flest av de som blir sortert etter nøyaktig 7 gjennomganger, dvs. 851 760 stykker. F.eks. er 1, 2, 4, 5, 6, 7, 8, 9, 10, 3 en av dem. Sjekk det! Tabellen under viser hele fordelingen:

Tallene over gir 6,5 som gjennomsnitt. Dvs. det trengs i gjennomsnitt 6,5 gjennomganger av en tabell med 10 forskjellige verdier for at den skal bli sortert vha. denne teknikken. For store n blir gjennomsnittet tilnærmet lik n − √(Π·n/2). Se [S & F]. Med n = 100 blir det 87,5. Men det er ikke så mye vi sparer siden gjennomgangene på slutten er langt mindre kostbare enn i begynnelsen. Intervallet som som undersøkes blir kortere for hver gjennomgang. Vi kan bruke testkjøringer til å avgjøre om vi tjener på dette. Se Oppgave 2.

Oppsummering - boblesortering:

• Navn: I en «loddrett» tabell, vil ombyttinger føre til at store verdier flytter seg oppover og den største havner øverst. Navnet boble er hentet fra det som skjer når vannet i en vannkjele koker. Da går det bobler oppover fra bunnen av kjelen.
• Effektivitet: Den «forbedrede» versjonen av boblesortering (Programkode 1.3.3 f ) er (mhp. sammenligninger) av lineær orden (orden n) i det beste (en sortert tabell) og av kvadratisk orden (orden n²) i gjennomsnitt og i det verste tilfellet.
• Ombyttinger: Antallet vil variere fra 0 (en sortert tabell) til n(n − 1)/2 (sortert motsatt vei). I gjennomsnitt blir det n(n − 1)/4 ombyttinger.
• Konklusjon: Av de mest kjente sorteringsmetodene er boblesortering den som er minst effektiv. Den brukes normalt ikke. I hvert fall ikke på store tabeller.

  Oppgaver til Avsnitt 1.3.3

  1.3.4  Utvalgssortering
Det er enkelt å finne den minste (eller den største) verdien i en tabell. Utvalgssortering (eng: selection sort) går ut på å gjøre det gjentatte ganger. Gitt flg. (usorterte) tabell:

Første oppgave er å finne den minste verdien. Vi ser at den (tallet 3) ligger i posisjon 10. Den byttes med verdien i posisjon 0 slik at den minste verdien kommer først i tabellen:

Vi gjør dette en gang til. Men nå finner vi den minste i resten av tabellen, dvs. i den delen av tabellen som starter i posisjon 1. Da får vi tallet 4 i posisjon 14. Den byttes med verdien i posisjon 1 slik at den nest minste verdien kommer nest først i tabellen:

Da er det bare å fortsette. Den minste verdien fra og med posisjon 2 og utover er tallet 5 som har posisjon 4. En ombytting gir dette resultatet:

Tabellens første del (den «grå» delen) er sortert og resten (den «hvite» delen) er usortert. For hver runde «velger» vi ut den minste i den «hvite» delen. Den byttes med den første i den «hvite» delen. Det fortsetter til tabellen er sortert. Navnet utvalgssortering kommer av at vi forløpende «velger» den minste av de resterende. Vi kunne ha gjort det motsatte. Dvs. vi kunne fortløpende ha valgt den største verdien og så plassert den bakerst. Se Oppgave 2.

Vi kan kode utvalgssortering direkte eller med hjelpemetoder. I Oppgave 1 i Avsnitt 1.2.1 ble du bedt om å lage en metode som finner posisjonen til minste verdi i et tabellintervall. Bruker vi den, får vi flg. korte kode for utvalgssortering:

  public static void utvalgssortering(int[] a)
  {
    for (int i = 0; i < a.length - 1; i++)
      bytt(a, i, min(a, i, a.length));  // to hjelpemetoder
  }
                Programkode 1.3.4 a)

I Oppgave 5 blir du bedt om å kode utvalgssortering uten bruk av hjelpemetoder.

Programkode 1.3.4 a) sorterer stigende. Hvis vi ønsker å sortere avtagende, kan vi lage en separat algoritme. Se Oppgave 8. Men det vil imidlertid være dumt om vi alltid måtte lage to versjoner av hver sorteringsmetode - en stigende og en avtagende. Senere, når vi skal lage generiske sorteringsmetoder, vil vi lage kun én versjon av hver metode. Ordningen kan da styres ved hjelp parameterverdier.

Men hvis en tabell allerede er sortert, er det lite arbeid som skal til for å få den sortert omvendt vei. Vi kan «snu» tabellen, dvs. rotere den om midten slik at første verdi kommer sist og siste verdi først, osv. Programkode 1.3.1 a) inneholder en slik metode. Hvis alle aktuelle metoder ligger i samleklassen Tabell, vil flg. kode være kjørbar:

  int[] a = {7,5,9,2,10,4,1,8,6,3};     // en usortert heltallstabell
  Tabell.utvalgssortering(a);           // stigende sortering
  Tabell.snu(a);                        // tabellen snus
  Tabell.skriv(a);                      // 10 9 8 7 6 5 4 3 2 1

                Programkode 1.3.4 b)

Effektivitet: Hvor effektiv er utvalgssortering? La n være antall verdier. Det trengs n − 1 sammenligninger for å finne den minste verdien. Deretter leter vi etter den minste blant resten. Til det trengs n − 2 sammenligninger. Osv. Til sammen blir det:

     n – 1  +  n – 2 + · · · · + 3 + 2 + 1   =  n(n – 1)/2

Resultatet n(n – 1)/2 er summen av en aritmetisk rekke. Hvis f.eks. n = 1000, blir det totalt 499.500 sammenligninger. Antallet kan også skrives som  n²/2 – n/2, dvs. et kvadratisk uttrykk i n. Algoritmen er derfor av kvadratisk orden eller av orden n². Det betyr at hvis vi dobler antall verdier, vil antall sammenligninger bli fire ganger så stort. Legg merke til at utvalgssortering er av kvadratisk orden i alle tilfeller - også om tabellen allerede er sortert.

Utvalgssortering er ineffektiv – i hvert fall hvis det er mange verdier. Se Oppgave 4. En fordel er imidlertid at algoritmen har en klar idé og har enkel kode. Vi forstår umiddelbart at den gir korrekt resultat. Den har også få ombyttinger. Dette er faktisk den sorteringsmetoden som har færrest ombyttinger, dvs. n − 1 stykker i alle tilfeller. Dette er gunstig sammenlignet f.eks. med boblesortering som i gjennomsnitt har n(n − 1)/4 ombyttinger.

Oppsummering - utvalgssortering:

• Navn: Algoritmen kalles utvalgssortering fordi det fortløpende «velges ut» en verdi som så blir plassert på rett sortert plass. I den vanlige versjonen av utvalgssortering blir fortløpende den minste blant de usorterte «valgt ut» og så plassert først blant dem.
• Effektivitet: Det trengs n − 1 sammenligninger for å finne den minste, så n − 2 stykker for å finne den nest minste (den minste av de øvrige), osv. Til sammen blir det n(n − 1)/2 = n2/2 − n/2 sammenligninger og det uansett fordelingen av verdiene. Det betyr at algoritmen har kvadratisk orden i alle tilfeller (verst, gjennomsnittlig og best).
• Ombyttinger: Det gjøres én ombytting i hver iterasjon og dermed n − 1 til sammen. Dette kan reduseres noe. Se Oppgave 11.
• Konklusjon: Utvalgssortering er som alle sorteringsalgoritmer av kvadratisk orden, ikke egnet til å sortere store tabeller. Den er imidlertid bedre enn boblesortering. Se Oppgave 4. I noen situasjoner kan det være ekstra kostbart å bytte om verdier (gjelder ikke i Java). I slike tilfeller kan denne algoritmen brukes for tabeller av moderat størrelse. Dette er den algoritmen som har færrest ombyttinger.

  Oppgaver til Avsnitt 1.3.4

  1.3.5  Søking
Usortert tabell Det å finne en verdi i en samling verdier er en av de mest grunnleggende oppgavene i databehandling. Her skal vi se på det tilfellet at verdiene ligger i en tabell. Hvis tabellen er usortert, er det ingen annen måte å gjøre det på enn å se på én og én verdi. Da vil vi, hvis tabellen inneholder den vi leter etter, før eller senere finne den. Hvis vi har sett på alle verdiene uten å finne den, kan vi konkludere med at den ikke er der.

Flg. metode returnerer posisjonen til søkeverdien hvis den ligger i tabellen, og returnerer –1 hvis den ikke er der. Hvis det er flere forekomster av søkeverdien, returneres posisjonen til den første av dem (fra venstre). Tabellen og søkeverdien inngår som parametere:

  public static int usortertsøk(int[] a, int verdi)  // tabell og søkeverdi
  {
    for (int i = 0; i < a.length; i++)  // går gjennom tabellen
      if (verdi == a[i]) return i;      // verdi funnet - har indeks i

    return -1;                          // verdi ikke funnet
  }
               Programkode 1.3.5 a)

Koden kan optimaliseres. Sammenligningen i < a.length i for-løkken kan (som vi har sett tidligere) fjernes hvis vi bruker søkeverdien som vaktpost. Det vil nok kun gi marginal effekt, men kan være en morsom øvelse i kodeteknikk. Se Oppgave 1.

Det finnes ingen mer effektiv teknikk enn den i Programkode 1.3.5 a) for å søke i en usortert tabell. La n være tabellengden. Hvis verdien ikke er der, vil if (verdi == a[i]) utføres n ganger. Men hva hvis den er der? Vi antar at alle verdiene er forskjellige og har samme sannsynlighet for å bli etterspurt. Hvis verdi ligger først, trengs én sammenligning, to hvis den ligger nest først, osv. Tilsammen 1 + 2 + · · · + n = n(n + 1)/2 stykker og dermed blir det n(n + 1)/2n = (n + 1)/2 som gjennomsnitt. Søkemetoden er derfor av orden n.

Sortert tabell Hvis tabellen er sortert (f.eks. stigende), kan vi forbedre søkealgoritmen. Den mest optimale teknikken kalles binærsøk. Den ser vi nærmere på i Avsnitt 1.3.6. Her skal vi isteden innføre en liten forbedring av idéen i Programkode 1.3.5 a) over. Det gir oss muligheten til å innføre begrepet innsettingspunkt.

Vi kan slik som i Programkde 1.3.5 a), se på én og én tabellverdi og returnere posisjonen så fort vi finner den vi leter etter. Hvis ikke, kan vi, siden tabellen er sortert, avbryte letingen så fort vi kommer til en verdi som er for stor. Ta som eksempel at vi leter etter 31 i flg. tabell:

Her stopper vi på 32. Vi kunne nå returnere –1 som et signal om at vi ikke fant 31. Men her er det mulig å slå «to fluer i en smekk». En negativ returverdi kan signalisere at verdien ikke er der. Men det vil også være fordelaktig å kunne rapportere hvilken posisjon/indeks verdien ville ha hatt dersom den hadde ligget der, dvs. verdiens innsettingspunkt. Det er der den måtte ha blitt satt inn for å få bevart sorteringen. Her er det posisjon eller indeks 10.

Definisjon 1.3.5 - Innsettingspunkt  En verdi som ikke ligger i en (stigende) sortert tabell, ville hvis den hadde ligget der, hatt en bestemt posisjon p. Denne posisjonen kalles verdiens innsettingspunkt (eng: insertion point).

Gitt en verdi som ikke er i tabellen. Hvis den er mindre enn den minste, dvs. mindre enn den som ligger lengst til venstre, blir dens innsettingspunktet p lik 0. Dermed kan vi ikke bruke –p som returverdi siden –0 og 0 er det samme. Returverdien skal alltid være negativ for verdier som ikke ligger i tabellen. Vi returnerer isteden –(p + 1). Den blir alltid negativ (også når p er 0). La videre k = –(p + 1). Da vil p = –(k + 1). Med andre ord kan vi, hvis søkeverdien ikke ligger i tabellen, beregne innsettingspunktet ved hjelp av returverdien.

Flg. metode, som vi kaller lineærsøk fordi vi ser på én og én tabellverdi, gjør som beskrevet over. Her vil tabellens siste (og dermed største) verdi fungere som en vaktpost. En verdi som er større enn den, vil ha p = a.length som innsettingspunkt. For alle andre søkeverdier vil den bli en stoppverdi. Legg metoden i samleklassen Tabell.

  public static int lineærsøk(int[] a, int verdi) // legges i class Tabell
  {
    if (a.length == 0 || verdi > a[a.length-1])
      return -(a.length + 1);  // verdi er større enn den største

    int i = 0; for( ; a[i] < verdi; i++);  // siste verdi er vaktpost

    return verdi == a[i] ? i : -(i + 1);   // sjekker innholdet i a[i]
  }
                Programkode 1.3.5 b)

Flg. eksempel viser hvordan metoden lineærsøk kan brukes:

  int[] a = {3,8,10,12,14,16,21,24,27,30,32,33,34,37,40};  // Figur 1.3.5 a)
  System.out.println(Tabell.lineærsøk(a,32));              // utskrift: 10
  System.out.println(Tabell.lineærsøk(a,31));              // utskrift: -11

               Programkode 1.3.5 c)

I Programkode 1.3.5 c) returnerer metoden 10 når det søkes etter 32. Det stemmer siden 32 har indeks/posisjon 10. Returverdien blir –11 når det søkes etter 31. En negativ returverdi forteller at den søkte verdien ikke ligger i tabellen. Tallet 31 hører hjemme mellom 30 og 32. Innsettingspunktet blir derfor lik posisjonen til 32, dvs. 10. Men vi kan beregne oss frem til det ved hjelp av returverdien. Generelt gjelder at hvis k er en negativ returverdi, blir innsettingspunktet lik –(k + 1). I eksemplet: –(–11 + 1) = 10. Se også Oppgave 2.

Med tanke på effektivitet er lineærsøk litt bedre enn usortertsøk for verdier som ikke ligger i tabellen. Den går i gjennomsnitt kun halvveis gjennom tabellen for å komme til første verdi som er for stor. Det er andre teknikker som er vesentlig mer effektive, men lineærsøk er likevel viktig. Den er god nok for små tabeller. Men det er selve idéen som er viktig siden den også vil virke for datastrukturer som kan «leses» kun én vei (f.eks. en pekerkjede).

Det er også mulig å forbedre lineærsøk, f.eks. ved å gjøre en serie «hopp» under søkingen. La tabellen a inneholde 100 verdier. Da kan vi f.eks. se på hver 10-ende verdi. Når vi passerer stedet der søkeverdien hører hjemme, vet vi at den vil måtte befinne seg blant de 10 siste vi hoppet over. Dermed kan vi lete etter søkeverdien blant dem. Bruker vi en «hopplengde» lik kvadratroten av tabellens lengde, vil algoritmen bli av orden kvadratrot. Da kalles algoritmen for kvadratrotsøk. Se Oppgave 5.

Metoden lineærsøk Programkode 1.3.5 b) er lite fleksibel. Det burde være mulig å kunne søke i et intervall og ikke kun i en hel tabell. Den gitte metoden blir da et spesialtilfelle av public static int lineærsøk(int[] a, int fra, int til, int verdi). Se Oppgave 4.

  Oppgaver til Avsnitt 1.3.5

  int[] a = {3,8,10,12,14,16,21,24,27,30,32,33,34,37,40};
  int[] b = Tabell.lineærIntervallsøk(a, 10, 20);
  System.out.println(Arrays.toString(b));  // [10, 12, 14, 16]

  1.3.6  Binærsøk

Keiser Augustus

I maktpolitikk og krig brukes begrepet splitt og hersk (eng: divide and conquer). Det har romersk opprinnelse og på latin: divide et impera. Det går ut på å gjøre motstanderne innbyrdes uenige for så å overvinne dem enkeltvis. Den idéen kan vi bruke. Hvis et problem skal løses, kan det ofte lønne seg å dele problemet i to eller flere mindre problemer, løse hver av dem for seg og så sette dette sammen til en løsning for hele problemet. Idéen er at det er enklere å løse en del av et problem enn å løse hele problemet.

Vi prøver flg. idé: Det går raskere å søke i halvparten enn i hele tabellen. Vi kan hoppe inn midt i en tabell. Hvis verdien ikke er der, vil sorteringen avgjøre på hvilken side vi skal lete videre. Da får vi halvert søkeområdet. Idéen kalles binærsøk. Den omtales ofte som en splitt og hersk-idé, men et bedre navn er forminsk og hersk (eng: decrease and conquer).

Vi skal generelt søke etter en verdi i et lukket intervall a[v:h] der v står for venstre og h for høyre endepunkt. I tillegg har vi midten m = (v + h)/2. Vi kan tenke på én av to måter:

1. Verdien ligger enten på midten eller på en av sidene a[v:m–1] eller a[m+1:h]. Søkeområdet blir dermed delt i tre - ett element og to lukkede delintervaller.
2. Alternativt kan vi nøye oss med å dele søkeområdet i to deler. Dvs. vi avgjør om den søkte verdien ligger i a[v:m] eller i a[m+1:h].

Vi starter med 1. måte. Flg. tabellintervall a[v:h] med 15 verdier er gitt. Anta at vi skal finne verdien 30. Fra starten av er hele søkeområdet markert med grå bakgrunn:

Midten er gitt ved m = (v + h)/2. Figuren viser at a[m] er lik 24. Vår søkeverdi 30 er større. Den må da, hvis den er der, ligge til høyre for m. Vi setter v = m + 1 og fortsetter:

På nytt er m = (v + h)/2. Søkeverdien 30 er heller ikke nå lik a[m] (dvs. 33), men derimot mindre. Dermed må den ligge til venstre for m. Nå settes h = m – 1:

Nå ser vi at søkeverdien 30 er lik a[m]. Vi kan avslutte søkingen og returnere posisjonen.

Vi får flg. algoritme:

1. Start med tabellintervallet a[v:h] og søkeverdien verdi.
2. Finn midten m = (v + h)/2.
3. Hvis verdi == a[m] , er vi ferdige!
4. Hvis verdi > a[m] , settes v = m + 1 og hvis ikke, settes h = m – 1.
5. Hvis v <= h, gå til 2. Hvis v > h, er a[v:h] tom og verdi er ikke i tabellen.

Med v > h blir intervallet a[v:h] tomt. Det betyr at verdi ikke er i tabellen. Men da blir v innsettingspunktet (se Definisjon 1.3.5) til verdi. Flg. metode har fra - til parametere siden det er det normale. Men inne i metoden gjøres det om til v og h:

  public static int binærsøk(int[] a, int fra, int til, int verdi)
  {
    Tabell.fratilKontroll(a.length,fra,til);  // se Programkode 1.2.3 a)
    int v = fra, h = til - 1;  // v og h er intervallets endepunkter

    while (v <= h)    // fortsetter så lenge som a[v:h] ikke er tom
    {
      int m = (v + h)/2;      // heltallsdivisjon - finner midten
      int midtverdi = a[m];   // hjelpevariabel for midtverdien

      if (verdi == midtverdi) return m;          // funnet
      else if (verdi > midtverdi) v = m + 1;     // verdi i a[m+1:h]
      else  h = m - 1;                           // verdi i a[v:m-1]
    }

    return -(v + 1);    // ikke funnet, v er relativt innsettingspunkt
  }

  public static int binærsøk(int[] a, int verdi)  // søker i hele a
  {
    return binærsøk(a,0,a.length,verdi);  // bruker metoden over
  }
                Programkode 1.3.6 a)

Obs. Hvis verdi ligger utenfor intervallet a[v:h], vil metoden gi et innsettingspunkt relativt til intervallet a[v:h]. Se Oppgave 2.

Inne i while-løkken i Programkode 1.3.6 a) har vi først: verdi == midtverdi. Er det lurest? Kunne vi isteden starte med: verdi > midtverdi ? Når flere tester skal utføres, er det ofte at rekkefølgen har betydning:

I mange situasjoner med flere utfall, kan det være vanskelig å vite hvilken sannsynlighet de forskjellige utfallene har. I while-løkken i Programkode 1.3.6 a) er det imidlertid enkelt. Det er tre muligheter eller utfall: 1) den søkte verdien ligger på midten, 2) den ligger til høyre for midten eller 3) den ligger til venstre for midten. Det er bare én verdi på midten, men normalt mange på hver side. Det betyr at det er langt mer sannsynlig at den søkte verdien ligger på en av sidene enn at den ligger på midten. Hvis a[v:h] inneholder et odde antall verdier, vil høyre og venstre side av midten ha nøyaktig like mange verdier. Men hvis a[v:h] har et like antall verdier, vil det til høyre for midten m = (v + h)/2 være én mer enn til venstre.

Vi burde derfor få en mer effektiv implementasjon av binærsøk hvis vi endrer på rekkefølgen av sammenligningene. Endringene i forhold til Programkode 1.3.6 a) er med uthevet rødt:

  // 2. versjon av binærsøk - returverdier som for Programkode 1.3.6 a)
  public static int binærsøk(int[] a, int fra, int til, int verdi)
  {
    Tabell.fratilKontroll(a.length,fra,til);  // se Programkode 1.2.3 a)
    int v = fra, h = til - 1;    // v og h er intervallets endepunkter

    while (v <= h)  // fortsetter så lenge som a[v:h] ikke er tom
    {
      int m = (v + h)/2;     // heltallsdivisjon - finner midten
      int midtverdi = a[m];  // hjelpevariabel for  midtverdien

      if (verdi > midtverdi) v = m + 1;        // verdi i a[m+1:h]
      else if (verdi < midtverdi) h = m - 1;   // verdi i a[v:m-1]
      else return m;                           // funnet
    }

    return -(v + 1);   // ikke funnet, v er relativt innsettingspunkt
  }
                Programkode 1.3.6 b)

Sammenligningene i while-løkken i Programkode 1.3.6 a) starter med verdi == midtverdi. Men det vil sjelden gi sann. Det er langt mer sannynlig at verdi ligger på én av sidene. Det betyr at det nesten alltid må utføres enda en sammenligning. Dvs. i gjennomsnitt ca. 2 av dem i hver iterasjon. I Programkode 1.3.6 b) starter det med verdi > midtverdi. Det er sant ca. annenhver gang. Dermed blir det i gjennomsnitt omtrent 1,5 sammenligninger i hver iterasjon. En forbedring på 25 prosent! Vi ser nærmere på dette i Avsnitt 1.3.7.

Den tredje versjonen av binærsøk tar utgangspunkt i alternativ 2. Søkeområdet deles kun i de to delene a[v:m] og a[m+1:h]. Dermed er det nok å utføre én sammenligning i hver runde. Det må imidlertid sjekkes helt til slutt om den verdien som algoritmen stopper på, er den søkte verdien eller ikke. Koden blir slik:

  // 3. versjon av binærsøk - returverdier som for Programkode 1.3.6 a)
  public static int binærsøk(int[] a, int fra, int til, int verdi)
  {
    Tabell.fratilKontroll(a.length,fra,til);  // se Programkode 1.2.3 a)
    int v = fra, h = til - 1;  // v og h er intervallets endepunkter

    while (v < h)  // obs. må ha v < h her og ikke v <= h
    {
      int m = (v + h)/2;  // heltallsdivisjon - finner midten

      if (verdi > a[m]) v = m + 1;   // verdi må ligge i a[m+1:h]
      else  h = m;                   // verdi må ligge i a[v:m]
    }
    if (h < v || verdi < a[v]) return -(v + 1);  // ikke funnet
    else if (verdi == a[v]) return v;            // funnet
    else  return -(v + 2);                       // ikke funnet
  }
                Programkode 1.3.6 c)

Denne 3. versjonen av binærsøk har, i tillegg til å være litt mer effektiv enn de to andre, også en fordel når tabellintervallet har like verdier. Anta at verdi forekommer to eller flere ganger. Da vil vi ikke kunne vite hvem av dem som versjon 1 (eller versjon 2) finner. Men med 3. versjon av binærsøk er det annerledes. Gitt flg. tabell:

Vi skal finne 19. While-løkken i Programkode 1.3.6 c) starter med intervallet a[0:14]. Vi får m = (0 + 14)/2 = 7 og a[7] = 17. Dermed v = m + 1 = 8 siden 19 er større enn 17. Nytt søkeområde blir a[8:14]:

Midten i søkeområdet (grå bakgrunn) er nå lik (8 + 14)/2 = 11 og a[11] = 19. Men 19 er ikke større enn 19. Dermed settes h = 11. Nytt søkeområde blir a[8:11]:

Nå består søkeområdet av de fire forekomstene av 19, men algoritmen fortsetter likevel inntil søkeområdet består av kun én verdi, dvs. til v er lik h. Først blir området lik a[8:9] siden midten er (8 + 11)/2 = 9. Til slutt blir søkeområdet lik a[8:8]:

Vi ser at v (her = 8) stopper på den første av de fire forekomstene av 19. Det er ikke tilfeldig! Det er kun setningen if (verdi > a[m]) v = m + 1; som «flytter» på v. Det betyr at når while-løkken stopper, er enten v uforandret eller så er verdien rett til venstre for v mindre enn verdi. Dermed må a[v] inneholde første forekomst fra venstre av verdi.

Hvis a ikke inneholder søkeverdien, vil v (med ett unntak) stoppe på innsettingspunktet (se Definisjon 1.3.5). Med en søkeverdi som er større enn alle, vil v stoppe på siste indeks. Men innsettingspunktet er én videre til høyre. Eksempel: Vi skal finne 26 i Figur 1.3.6 d). Det gir flg. sekvens av intervaller: a[0:14], a[8:14], a[12:14] og a[14:14]. Men det er 15 som er innsettingspunkt. Derfor må metoden returnere –(v + 2) i dette tilfellet.

Konklusjon:   Det finnes mange søkealgoritmer for sorterte tabeller. En kan, ved å gjøre noen forutsetninger, finne formler for tilnærmet gjennomsnittlig antall sammenligninger. F.eks. at alle verdiene er forskjellige. Det gir oss algoritmenes orden:

Det liten forskjell når det er få verdier. Lineærsøk ser litt dårligere ut for n = 10, men er minst like god fordi den har færre omkostninger knyttet til hver sammenligning. Men når n blir stor, ser vi at binærsøk er overlegent best.

Alle de tre binærsøk-versjonene er svært effektive. En ekstra fordel med 3. versjon er at hvis søkeverdien forekommer flere ganger, vil den alltid returnere indeksen til den første av dem fra venstre. Det kan være en nyttig. Derfor er det 3. versjon vi kommer til å bruke senerer (den legges i samleklassen Tabell). De som har laget klassebiblioteket java.util har valgt 2. versjon. Se kildekoden til int binarySearch(int[] a, int key) i i klassen Arrays.

  Oppgaver til Avsnitt 1.3.6

  1.3.7  Matematisk analyse av binærsøk
Tabell 1.3.6 har formler for gjennomsnittlig antall sammenligninger i de tre versjonene av binærsøk. Vi kan finne dem ved hjelp av beslutningstrær (eng: decision tree). Gitt flg. tabell:

Vi ser på 1. versjon av binærsøk. I Figur 1.3.7 a) over vil v = 0 og h = 12. I while-løkken settes m = (v + h)/2 = (0 + 12)/2 = 6 og midtverdien a[6] = 15. Hvis den er lik søkeverdien, avslutter vi etter kun én sammenligning. Hvis ikke, avgjør vi hvilken side av midten vi skal inn på. Til det trengs én sammenligning til. I neste runde går vi inn på midten av en av sidene, dvs. til m = (0 + 5)/2 = 2 eller m = (7 + 12)/2 = 9 med tilhørende verdier lik 6 eller 22. Hvis det er en av disse to vi søker etter, kan vi avslutte etter å ha gjort tilsammen 3 sammenligninger. Hvis ikke må vi halvere igjen og kommer til m = 0, 4, 7 eller 11. Osv.

Dette kan tegnes i et beslutningstre med like mange noder som tabellen har verdier. Midtverdien a[6] = 15 legges i rotnoden, midtverdiene på hver side (a[2] = 6 og a[9] = 22) legges i de to nodene på nivået under, osv.

Figur 1.3.7 b) : Et beslutningstre

Treet er verken perfekt eller komplett, men alle nivåene i treet, bortsett fra det siste, er fulle av noder. Treet er ordnet. For hver node gjelder at dens verdi ligger mellom verdiene i dens to subtrær. Et ordnet binærtre eller binært søketre som det kalles, er en viktig datastruktur og vi vil arbeide med slike trær i flere kapitler utover.

I Figur 1.3.7 b) er det et heltall ved hver node. Det angir hvor mange sammenligninger som skal til i while-løkken i 1. versjon av binærsøk for å finne nodens verdi. Hvis vi søker rotverdien (nivå 0) holder det med 1 sammenligning. Hvis det er en av de to verdiene i neste rad (nivå 1) holder det med 3 sammenligninger, for de fire i neste rad (nivå 2) 5 sammenligninger, osv. Med andre ord trengs det 2k + 1 stykker for å finne en verdi som ligger på nivå k i beslutningstreet.

Anta at alle de 13 verdiene har samme sannsynlighet for å bli etterspurt og at den vi leter etter finnes i tabellen. Det gjennomsnittlige antallet sammenligninger blir da

Treet i Figur 1.3.7 b) mangler to noder på nederste rad for å kunne være perfekt. Med andre ord må vi ha en tabell med 15 verdier for å få 8 noder på nederste rad. Et beslutningstre blir derfor perfekt hvis tabellen har en lengde på 1, 3, 7, 15, 31, 63, osv, eller generelt en lengde på 2^k – 1 med k > 0. Formen på et beslutningstre er kun bestemt av antall verdier i tabellen.

Som et nytt eksempel tar vi en tabell med lengde 2⁵ - 1 = 31:

Figur 1.3.7 d) : Et beslutningstre for 31 verdier basert på Programkode 1.3.6 a)

Midtverdien a[15] = 42 havner i rotnoden (nivå 0), midtverdiene på hver side (a[7] = 19 og a[23] = 62) havner i rotnodens to barn (venstre og høyre barn) på nivå 1, osv. Ved siden av hver node står antall sammenligninger som trengs i while-løkken i Programkode 1.3.6 a) for å finne verdien i noden. Vi antar at alle verdiene er forskjellige og har like stor sannsynlighet for å bli etterspurt. Det gjennomsnittlige antallet sammenligninger blir da:

Summen kan også skrives ved hjelp av potenser:

La antall verdier være n = 2^k − 1 istedenfor 31 (dvs. k = 5) og la A_k være summen

Summen av denne potensrekken (se Formel G.1.12 i Vedlegg G.1 ) blir:

Eksempel: k = 5 gir A₅ = (2 · 5 – 3) · 2⁵ + 3 = 7 · 32 + 3 = 227. Det passer med tegningen.

Når n = 2^k – 1 blir 2^k = n + 1 og k = log₂(n+1), og gjennomsnittet for de n verdiene:

For store n (1/n liten) blir dette tilnærmet lik  2 · log₂(n+1) – 3. Hvis n ikke er lik 2^k – 1, vil formelen gi (for n stor) en god tilnærming for det gjennomsnittlige antallet sammenligninger.

Treet i Figur 1.3.7 d) viser at det mest ugunstige tilfellet (søkeverdien ligger nederst) trengs 2 · log₂(32) − 1 = 9 eller generelt 2 · log₂(n+1) − 1 sammenligninger. Hvis søkeverdien ikke finnes, går algoritmen til bunns i treet og et hakk videre. Dvs. 2 · log₂(32) = 10 eller generelt 2 · log₂(n+1) sammenligninger.

Konklusjon: I 1. versjon av binærsøk trengs kun én sammenligning i det mest gunstige tilfellet (verdien ligger midt i tabellen), 2 · log₂(n+1) – 3 i gjennomsnitt, 2 · log₂(n+1) − 1 i det mest ugunstige tilfellet og 2 · log₂(n+1) stykker for å avgjøre at en verdi ikke finnes. Den er av orden log₂(n+1) (logaritmisk orden) både i gjennomsnitt og i de mest ugunstige tilfellene.

I 2. versjon av binærsøk ble sammenligningenes rekkefølge endret i forhold til 1. versjon:

  if (verdi > midtverdi)
    v = m + 1;                    // verdi må ligge i a[m+1:h]
  else if (verdi < midtverdi)
    h = m - 1;                    // verdi må ligge i a[v:m-1]
  else  return m;                 // funnet

Endringen gir faktisk en forbedring. Se på Figur 1.3.7 c). Nå trengs to sammenligninger for å finne midtverdien 42, dvs. én for å avgjøre at vi ikke skal til høyre og én til for å avgjøre at vi ikke skal til venstre. Vi trenger 3 stykker for å finne 62, dvs. én sammenligning for å avgjøre at 62 er til høyre for 42 og så to til for å avgjøre at vi verken skal til høyre eller til venstre for 62. Vi må imidlertid ha 4 stykker for å finne 19. Vi trenger to for å avgjøre at 19 ligger til venstre for 42 og så to til for å avgjøre at vi verken skal til høyre eller venstre for 19. Osv. I Figur 1.3.7 e) under står det ved siden av hver node antallet sammenligninger i while-løkken i 2. versjon av binærsøk for å finne den verdien:

Figur 1.3.7 e) : Et beslutningstre for 31 verdier basert på Programkode 1.3.6 b

Vi summerer tallene og deler med 31. Gjenomsnittlig antall sammenligninger blir 209/31 = 6,7. Treet i Figur 1.3.7 d) gav resultatet 7,3. Dermed har vi fått en liten forbedring.

La antall verdier være på formen n = 2^k – 1 og la A_k være det sammenlagte antallet sammenligninger. Kan vi finne en formel for A_k? Det er lett å finne et gjennomsnitt for hver rad i treet i Figur 1.3.7 e). Ta f.eks. 4. rad (nivå 3). Der er summen av tallene ved første og siste node lik 8 + 5 = 13. Den samme summen får vi for andre og nest siste node, dvs. 7 + 6 = 13. Osv. Gjennomsnittet for nodene på raden blir dermed 13/2 = 6,5. På samme måte ser vi at rad 5 har et gjennomsnitt på 8 og rad 3 et gjennomsnitt på 5. Dermed får vi:

Med k = 5 blir siste ledd (1,5 · 5 + 0,5) · 2⁴ = 8 · 2⁴. A_k blir (se Avsnitt 1.3.16):

Eksempel: Hvis k = 5 blir A₅ = (1,2 · 5 - 1) · 2⁵ + 1 = 6,5 · 32 + 1 = 209. Dette stemmer med treet i Figur 1.3.7 e). Obs: A_k kan finnes på flere måter. Se Avsnitt 1.3.16.

Når n = 2^k − 1 blir k = log₂(n + 1). Gjennomsnittet for de n verdiene blir:

For store n (dvs. når 1/n er liten) blir dette tilnærmet lik  1,5 · log₂(n + 1) – 1.  Hvis n ikke er på formen 2^k - 1, gir likevel formelen en god tilnærmingsverdi.

Det trengs  1,5 · log₂(n + 1)  sammenligninger i gjennomsnitt for å avgjøre at en verdi ikke er der. Det kreves flest hvis verdien er lik tabellens minste verdi, dvs.  2 · log₂(n + 1) stykker.

Konklusjon: I 2. versjon av binærsøk trengs to sammenligninger i det mest gunstige tilfellet (søkeverdien ligger på midten av tabellen), 1,5 · log₂(n + 1) – 1 sammenligninger i gjennomsnitt, 2 · log₂(n + 1) i det mest ugunstige tilfellet og gjennomsnittlig 1,5 · log₂(n + 1) stykker for å avgjøre at en verdi ikke finnes. Det betyr at 1. og 2. versjon er av samme orden, men 2. versjon er i gjennomsnitt 25% mer effektiv enn 1. versjon.

I 3. versjon av binærsøk er analysen mye enklere. Anta at tabellen har en lengde n på formen 2^k, dvs. n = 2, 4, 8, 16, 32, 64, osv. I denne versjonen ser while-løkken slik ut:

  while (v < h)
  {
    int m = (v + h)/2;
    if (verdi > a[m]) v = m + 1;
    else  h = m;
  }

Hvis antall verdier i tabellintervallet a[v:h] er på formen 2^k vil divisjonen m = (v + h)/2 gjøre at intervallene a[v:m] og a[m+1:h] blir eksakt like store, begge med 2^k–1 verdier. Dvs. at for hver sammenligning if (verdi > a[m]) i while-løkken blir søkeområdet a[v:h] nøyaktig halvert.

Vi ser på et eksempel med bare 8 verdier. Gangen i algoritmen kan illustreres på flg. måte:

Figur 1.3.7 f) : Tabellintervallene halveres hver gang

While-løkken går så lenge som v < h. Vi starter med 8 = 2³ verdier og kommer til v = h etter 3 iterasjoner. Generelt, hvis vi starter med n = 2^k verdier, trengs k iterasjoner. I tilegg trengs en sammenligning (se Programkode 1.3.6 c ) for å avgjøre om verdien ligger på denne plassen. Til sammen k + 1 sammenligninger. Men vi kan, siden n = 2^k, sette k = log₂(n). Dermed blir det log₂(n) + 1 sammenligninger enten den verdien ligger i tabellen eller ikke.

Hvis n ikke er på formen 2^k, så må det finnes en k slik at 2^k < n < 2^k+1. Dermed vil det gjennomsnittlige antallet sammenligninger ligge mellom log₂(n) og log₂(n) + 2.

Konklusjon: Alle de tre versjonene av binærsøk er av logaritmisk orden. Den 3. versjonen er noe bedre (33%) enn 2. versjon, og 2. versjon er noe bedre (25%) enn 1. versjon. Dermed er det 3. versjon som bør inngå i vårt arsenal av søkemetoder for sorterte tabeller, dvs. ligge i samleklassen Tabell.

  Oppgaver til Avsnitt 1.3.7

  1.3.8  Ordnet innsetting, innsettings- og shellsortering
Hvis en tabell skal holdes sortert, kan vi ikke legge inn nye verdier på vilkårlige plasser. De må legges inn på rett sortert plass. Hvis en verdi ikke er der fra før, har den et veldefinert innsettingspunkt. Hvis verdien allerede er der, kan den settes inn foran, bak eller eventuelt mellom dem som er der fra før. Det må også være plass i tabellen til en ny eller nye verdier.

I flg. eksempel har tabellen plass til 15 verdier, men det er foreløpig lagt inn kun 10 stykker.

Hvis vi skal legge inn en ny verdi i tabellen over, må vi først forvisse oss om at det er plass. Dernest må vi finne hvor den skal ligge, forskyve verdier mot høyre for å få plass og så legge den inn. For å finne plassen kan vi bruke en søkemetode, f.eks. binærsøk fra Avsnitt 1.3.6. Alt dette gjøres i flg. kodebit (metoden skrivln() er fra Oppgave 4 og 5 i Avsnitt 1.2.2 ):

  int[] a = {3,5,6,10,10,11,13,14,16,20,0,0,0,0,0};  // en tabell
  int antall = 10;                                   // antall verdier

  if (antall >= a.length) throw new IllegalStateException("Tabellen er full");

  int nyverdi = 10;                                  // ny verdi 
  int k = Tabell.binærsøk(a, 0, antall, nyverdi);    // søker i a[0:antall>
  if (k < 0) k = -(k + 1);                           // innsettingspunkt

  for (int i = antall; i > k; i--) a[i] = a[i-1];    // forskyver

  a[k] = nyverdi;                                    // legger inn
  antall++;                                          // øker antallet

  Tabell.skrivln(a, 0, antall);  // Se Oppgave 4 og 5 i Avsnitt 1.2.2

                Programkode 1.3.8 a)

Programsetningen: if (k < 0) k = -(k + 1); sørger for at k blir innsettingspunktet i det tilfellet nyverdi ikke finnes fra før. Her er den lik 10 og siden den finnes fra før, vil k være positiv. Den eksakte verdien til k er avhengig av hvilken versjon av binærsøk() som brukes. Er det 3. versjon, vil k = 3. Se Oppgave 1.

Hvis det ikke er plass i tabellen, kastes et unntak. Et alternativ er å «utvide» tabellen. Det betyr at det opprettes en ny og større tabell og så kopieres innholdet av den gamle over i den nye. Det kan f.eks. gjøres slik (se Oppgave 2):

  if (antall >= a.length) a = Arrays.copyOf(a,2*a.length);  // dobbelt størrelse

                Programkode 1.3.8 b)

I koden over brukes metoden copyOf() fra klassen Arrays. Se Oppgave 3.

Innsettingssortering (eng: insertion sort) er en sorteringsteknikk som gjentar det samme som i Programkode 1.3.8 a). Vi tenker oss nå at tabellen i Figur 1.3.8 a) også har verdier på de fem siste plassene, men at de er usortert når vi ser på hele tabellen:

I innsettingssortering er tabellen todelt. Første del inneholder sorterte og andre del (med grå bakgrunn) usorterte verdier. Fortsettelsen går ut på at den første verdien i den usorterte delen settes inn på rett plass i den sorterte delen. Vi legger den (her 12) midlertidig til side i en hjelpevariabel. Dermed får den «hvite» delen en ledig plass (indeks 10):

Neste skritt er å finne hvor verdien 12 skal inn. Én og én verdi forskyves mot høyre inntil vi finner rett plass. Først flyttes 20 én mot høyre, så 16, osv. inntil indeks 6 der 12 skal inn:

Dette fortsetter: Den første av de usorterte (dvs. 4) legges til side og dens plass blir ledig:

Så forskyves én og én verdi. Vi ser at rett plass er nest først (indeks 1). Dermed:

Vi er ferdige når hele tabellen har blitt «hvit». I utgangspunktet er hele tabellen usortert. Men vi kan se på det første elementet som sortert. Det betyr at når innsettingssorteringen starter, utgjør første element den «hvite» delen og resten den «grå» delen.

I Programkode 1.3.8 a) inngår binærsøk, men det er mest vanlig å sammenligne og forskyve én og én verdi ved hjelp av en indeks j. Den må sjekkes i tilfellet verdi skal legges helt først:

  public static void innsettingssortering(int[] a)
  {
    for (int i = 1; i < a.length; i++)  // starter med i = 1
    {
      int verdi = a[i], j = i - 1;      // verdi er et tabellelemnet, j er en indeks
      for (; j >= 0 && verdi < a[j]; j--) a[j+1] = a[j];  // sammenligner og flytter
      a[j + 1] = verdi;                 // j + 1 er rett sortert plass
    }
  }           Programkode 1.3.8 c)

Flg. eksempel viser hvordan metoden kan brukes:

  int[] a = {13,11,10,20,15,5,3,2,14,10,12,6,7,4,16};
  Tabell.innsettingssortering(a);
  System.out.println(Arrays.toString(a));
  // Utskrift: [2, 3, 4, 5, 6, 7, 10, 10, 11, 12, 13, 14, 15, 16, 20]

              Programkode 1.3.8 d)

Algoritmeanalyse: Vi skal finne ut hvor mange ganger sammenligningen verdi < a[j] utføres i en tabell med n verdier der alle er forskjellige. Anta at de i første verdiene er sortert, dvs. a[0], a[1], · · · a[i - 1]. Tallet verdi skal inn på rett plass blant dem. Det er i + 1 forskjellige muligheter: foran a[0], mellom a[0] og a[1], mellom a[1] og a[2], osv. eller etter a[i - 1]. Alle er like sannsynlige siden verdiene er forskjellige.

Vi trenger én sammenligning for å avgjøre om verdi skal bak a[i - 1], to for å avgjøre om den skal mellom a[i – 1] og a[i – 2], osv. Til slutt trengs i stykker både for å avgjøre om verdi skal mellom a[0] og a[1] eller foran a[0]. Sum: 1 + 2 + · · · + i + i = i(i+1)/2 + i. Gjennomsnittet får vi ved å dele med i + 1, dvs. lik i/2 + 1 - 1/(i + 1) Vi summerer fra 1 til n - 1 og får det gjennomsnittlige antallet ganger verdi < a[j] utføres:

Det verste tilfellet er en sortert avtagende tabell. Da er verdi < a[j] sann for hver j. Dermed i sammenligninger i indre løkke, og totalt 1 + 2 + · · · + i = n (n − 1)/2 sammenligninger. Det beste tilfellet er når tabellen er sortert stigende. Da er verdi < a[j] aldri sann og antallet blir 1 + 1 + · · · + 1 = n − 1.

Det er tre algoritmer av kvadratisk orden som vanligvis diskuteres i et fag som «Algoritmer og datastrukturer». Flg. tabell viser deres effektivtet med tanke på sammenligninger:

Det er antall sammenligninger det legges mest vekt på i algoritmeanalyse. Men også antall ombyttinger er av interesse. Nå er det egentlig ingen ombyttinger i innsettingssortering slik den er satt opp i Programkode 1.3.8 c) - kun tilordninger. F.eks. a[j+1] = a[j]. Men det er fullt mulig å kode metoden ved å bruke ombyttinger. Men en ombytting er litt mer kostbar enn en enkel tilordning. Ta utgangspunkt i tabellen i Figur 1.3.8 b). Der skal den første i den «grå» delen (tallet 12) inn på rett plass i den «hvite» delen. Det får vi til ved å bytte om 12 og 20, så bytte om 12 og 16, så 12 og 14 og til slutt 12 og 13. Da vil 12 komme mellom 11 og 13. Bruker vi bytt-metoden fra samleklassen Tabell, vil flg. kode virke:

  public static void innsettingssortering(int[] a)
  {
    for (int i = 1; i < a.length; i++)  // starter med i = 1
    {
      int temp = a[i];  // hjelpevariabel
      for (int j = i - 1; j >= 0 && temp < a[j]; j--) Tabell.bytt(a, j, j + 1);
    }
  }           Programkode 1.3.8 e)

Hvis de i første verdiene er sortert, kreves ingen ombytting hvis a[i] ligger riktig, én ombytting hvis a[i] skal foran a[i - 1], osv. til i ombyttinger hvis a[i] hører hjemme lengst til venstre. Dermed tilsammen 1 + 2 + · · · + i = i(i + 1)/2 stykker. Gjennomsnittet får vi ved å dele på (i + 1) og det blir i/2. Summerer vi dette fra 1 til n - 1 får vi at gjennomsnittlig antall ombyttinger er: n(n - 1)/4.

Oppsummering - innsettingssortering:

• Navn: Det kalles innsettingssortering fordi tabellen underveis er todelt. Venstre del er sortert. Én og én verdi fra høyre del settes inn på rett sortert plass i venstre del. Ved start består venstre del av det første elementet og høyre del av resten. Når algoritmen slutter, består venstre del av hele tabellen (og høyre del er tom).
• Effektivitet: Det kan vises (se algoritmeanalyse) at det i gjennomsnitt (hvis alle verdiene er forskjellige) utføres n(n + 3)/4 − Hn sammenligninger. Det betyr at den er av kvadratisk orden i gjennomsnitt. Hvis tabellen allerede er sortert, utføres det n − 1 sammenligninger. Dermed er den av lineær orden i det beste tilfellet.
• Ombyttinger: Det er ingen ombyttinger slik som innsettingssortering er kodet i Programkode 1.3.8 c). Det er isteden forskyvninger (tilordninger) som er litt mindre kostbare, og av dem er det i gjennomsnitt n(n − 1)/4 stykker.
• Konklusjon: Av de tre av kvadratisk orden som vi har sett på, er innsettingssortering best. Vi skal se på algoritmer av orden n log(n) og de er langt bedre for store tabeller. Men innsettingssortering er best hvis tabellen er liten eller stor, men delvis sortert. Det er kvikksortering som er best av de «avanserte». Den arbeider på intervaller og når de har blitt små nok, er det der vanlig å skifte over til innsettingssortering.

Mulige forbedringer En enkel forbedringsidé er å ta to verdier om gangen fra den høyre delen. Først settes den største av dem inn på rett sortert plass i venstre del. Deretter kan letingen etter plassen til den minste fortsette derfra. Dermed blir det færre sammenligninger. I gjennomsnitt vil den minste av de to havne i 1/3-dels avstand fra starten av venstre del og den andre i 2/3-dels avstand. Det gir ca. n²/6 sammenligninger i gjennomsnitt mot ca. n²/4 stykker for vanlig innsettingssortering. Dvs. ca. 30% mer effektiv. Se Oppgave 11 - 13.

Shellsortering En annen mulig (og vesentlig) forbedring har som idé at tabellen fortløpende deles opp i mindre og mindre grupper av verdier og de sorteres hver for seg ved hjelp av innsettingssortering. Det kalles shellsortering etter Donald Shell. Ta utgangspunkt i flg. tabell:

Vi deler opp i 10 grupper à to verdier. Første gruppe består av a[0] og a[10], andre gruppe av a[1] og a[11], tredje gruppe a[2] og a[12], osv. til a[9] og a[19] som tiende gruppe. Hver gruppe sorteres for seg. Med kun to verdier kan det gjøres ved at de to verdiene bytter plass hvis de er i utakt. Det betyr f.eks. at a[0] = 8 må bytte plass med a[10] = 5. Osv.

Nå deler vi opp i 4 grupper à fem verdier. Første gruppe skal bestå av a[0], a[4], a[8], a[12] og a[16], dvs. av verdiene 5, 12, 1, 16 og 6. For lesbarhetens skyld får de (se figuren under) grå bakgrunn. Andre gruppe: a[1], a[5], a[9], a[13] og a[17], dvs. verdiene 14, 2, 10, 19 og 20. Osv. Disse 4 gruppene skal sorteres hver for seg ved hjelp av innsettingssortering.

Innsettingssortering brukes normalt på en hel tabell eller på et intervall. Men her har vi ingen av delene. Men verdiene har en fast avstand eller gap. Den er forskjellen mellom indeksene for to naboverdier. Mellom a[0] og a[4] er det 4 - 0 = 4, mellom a[4] og a[8] lik 8 - 4 = 4. Osv. Vanligvis økes (eller reduseres) en indeks med 1, men her blir det 4. Ta utgangspunkt i Programkode 1.3.8 c), bruk 4 istedenfor 1, i += 4 istedenfor i++ og j -= 4 istedenfor j--. Flg. kode vil sortere første gruppe (a[0], a[4], a[8], a[12], a[16]) i Figur 1.3.8 i):

  int[] a = {5,14,13,11,12,2,3,4,1,10,8,18,16,19,17,9,6,20,7,15};

  for (int i = 4; i < a.length; i += 4)   // avstanden/gapet er nå 4 og ikke 1
  {
    int temp = a[i], j = i - 4;
    for (; j >= 0 && temp < a[j]; j -= 4) a[j + 4] = a[j];
    a[j + 4] = temp;
  }

Hvis denne koden kjøres, vil tabellen a få samme innhold som i figuren under:

Det trengs kun én endring i koden over for at alle de fire gruppene skal bli sortert. Endringen er i++ i den ytterste for-løkken istedenfor i += 4. Det starter med i = 4. Med i++ blir i neste gang lik 5. Da sammenlignes a[5] og a[1] og de bytter plass hvis de er i «utakt». Så blir i = 6 og a[6] og a[2] sammenlignes. Osv. Det betyr at de to første verdiene i hver gruppe behandles først, så de tre første verdiene i hver gruppe, osv. Vi kan lage en metode for dette der avstanden eller gapet ikke er 4, men er generelt lik k:

  public static void shell(int[] a, int k)
  {
    for (int i = k; i < a.length; i++)
    {
      int temp = a[i], j = i - k;
      for ( ; j >= 0 && temp < a[j]; j -= k) a[j + k] = a[j];
      a[j + k] = temp;
    }
  }           Programkode 1.3.8 f)

Ved hjelp av metoden shell() kan vi sortere en tabell fullstendig. Vi starter med tabellen i Figur 1.3.8 g). Så bruker vi først avstand/gap lik 10, så lik 4 og til slutt lik 1:

  int[] a = {8,14,16,19,17,9,3,4,1,15,5,18,13,11,12,2,6,20,7,10};
  int[] gap = {1,4,10};
  for (int i = gap.length - 1; i >= 0; i--)
  {
    shell(a,gap[i]);                         // først 10, så 4 og 1 til slutt
    System.out.println(Arrays.toString(a));  // skriver ut
  }
  // [5, 14, 13, 11, 12, 2, 3, 4, 1, 10, 8, 18, 16, 19, 17, 9, 6, 20, 7, 15]
  // [1, 2, 3, 4, 5, 10, 7, 9, 6, 14, 8, 11, 12, 19, 13, 15, 16, 20, 17, 18]
  // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]

              Programkode 1.3.8 g)

Den som er observant vil se at i siste runde (1 som gap) utføres full innsettingssortering. Men hva er da poenget? Det er en masse arbeid i rundene foran og så full innsettingssortering til slutt. Men poenget er at i siste runde er tabellen delvis sortert. Det ser vi på den nest siste utskriften i Programkode 1.3.8 g). I slike tilfeller er vanlig innsettingssortering den beste av alle sorteringsalgoritmer. I starten (gapet er 10) foregår det på små grupper (eller intervaller med store gap). I slike tilfeller er også innsettingssortering best. Med andre ord er dette (dvs. shellsortering) en systematisk utnyttelse av de beste sidene ved innsettingssortering.

I figurene over og i Programkode 1.3.8 g) ble det brukt først 10, så 4 og til slutt 1. Hvorfor akkurat disse tallene? For det første må vi ha 1 til slutt for å sikre at tabellen blir sortert. Som nevnt svarer det til vanlig innsettingssortering og dermed vil tabellen bli sortert uansett hva som måtte å hendt på forhånd. Både 10 og 4 går opp i tabellengden 20, men det er ikke noe krav. Vi kunne f.eks. ha valgt 9 først. Da får vi 9 grupper med verdier der de to første får 3 verdier og de seks siste 2 verdier. F.eks. vil første gruppe da bestå av a[0], a[9] og a[18], mens a[8] og a[17] utgjør siste gruppe.

Generelt: La n være lengden på tabellen og k et tall mellom 0 og n. La r være resten og q kvotienten når n deles med k. Et gap på k vil da gi k grupper med q + 1 verdier i de r første gruppene og q verdier i de øvrige. Hvis r = 0 (k går opp i n), vil alle gruppene ha q verdier.

Men hvilke tall skal vi velge hvis tabellen er stor? Det er bygget opp en hel vitenskap rundt dette. Valget er avgjørende for effektiviteten. For store tabeller viser teori og eksperimenter at å bruke 1, 4, 10, 23, 57, 132, 301, 701, · · · er nær optimalt. Dette minner litt om en geometrisk følge. Husk at en følge er geometrisk hvis forholdet (kvotienten) mellom et tall i følgen og det foregående tallet, er konstant. Her får vi flg. kvotienter:

    4,00  2,50  2,30  2,48  2,32  2,28  2,33

Kvotientene (bortsett fra den første) svinger mellom 2,2 og 2,5. Dvs. ingen geometrisk følge, men kvotientene er ikke langt unna å være lik en konstant. Hvis vi ønsker oss slike tall som er større enn 701, har det blitt foreslått at vi da bør velge tall som er ca. 2,25 ganger større enn det forrige. F.eks. er 2,25 · 701 = 1577,25. Med avrunding nedover blir det 1577.

Vi skal nå sammenligne effektiviteten til innsettings- og shellsortering. Tilfeldige tabeller med f.eks. 200.000 verdier (eller færre på din maskin) vil gjøre at innsettingssortering ikke bruker alt for lang tid. Vi kan, som nevnt over, finne flere gap-verdier. Tilsammen blir det: 1, 4, 10, 23, 57, 132, 301, 701, 1577, 3548, 7984, 17965, 40423, 90952, 204642. Hvis metodene innsettingssortering(), shell() og erSortert() er lagt i samleklassen Tabell, vil flg. kode være kjørbar:

  int[] gap = {1,4,10,23,57,132,301,701,1577,3548,7984,17965,40423,90952,204642};
  int[] a = Tabell.randPerm(200_000);       // en tilfeldig tabell
  System.out.println(Tabell.erSortert(a));  // sjekker tabellen

  long tid = System.currentTimeMillis();    // starter klokken

  Tabell.innsettingssortering(a);           // sorterer
  //for (int i = gap.length - 1; i >= 0; i--) Tabell.shell(a,gap[i]);

  System.out.println(System.currentTimeMillis() - tid);  // tiden
  System.out.println(Tabell.erSortert(a));  // sjekker sorteringen

              Programkode 1.3.8 h)

Hvis du kjører programmet over, vil du se hvor lang tid (millisekunder) innsettingssortering bruker på din maskin. Kjør programmet et par-tre ganger for å få forskjellige tabeller. De to andre utskriftene (true/false) er kun for å sjekke at tabellen faktisk blir sortert. Flytt så kommentartegnet // fra for-løkken over til kallet på innsettingssortering. Hva blir resultatet nå? Bruk også Arrays.sort(a); dvs. Java's sorteringsmetode. Hvor lang tid bruker den?

Oppsummering - shellsortering:

• Navn: Kalles shellsortering til ære for «oppdageren» Donald Shell. Den ble kjent i 1959 og vakte stor interesse siden man på den tiden ikke kjente til generelle metoder med en (gjennomsnittlig) orden vesentlig bedre enn n².
• Effektivitet: Det er kjent at den er av kvadrastisk (n²) orden i det verste og av orden n log(n) i det beste tilfellet. Men metoden er sterkt avhengig av sekvensen av gap-verdier og det er ikke kjent hvilken orden den har i gjennomsnitt.
• Konklusjon: Metoden brukes ikke lenger i praksis siden det nå finnes bedre metoder - f.eks. kvikksortering. Men den er interessant siden den på en systematisk måte utnytter de beste sidene ved innsettingssortering.

  Oppgaver til Avsnitt 1.3.8

  1.3.9  Partisjonering og kvikksortering
Å partisjonere en tabell betyr å omorganisere og ordne den i deler etter bestemte kriterier.

Eksempel 1.3.9 a): Flg. tabell inneholder kun tallene 0 og 1:

Vi ønsker å «partisjonere» den slik at alle 0-ene kommer i første halvdel og dermed alle 1-erne i andre halvdel. Målet er å gjøre det med minst mulig innsats.

Eksempel 1.3.9 b): Flg. tabell inneholder 20 tall i området fra 1 til 25:

Ønske: Todelt tabell der venstre del inneholder alle mindre enn 10, høyre del resten og ingen krav til fordelingen innen de to delene. Målet er å få det gjort med minst mulig innsats.

Eksempel 1.3.9 c): Flg. tabell inneholder kun bokstavene R, H og B:

Ønske: Tredelt tabell der R-ene kommer først, så H-ene og til slutt B-ene. Det å gjøre dette på en mest mulig effektiv måte, kalles «Det hollandske flaggproblemet» (eng: The Dutch National Flag Problem). Her står bokstavene R, H og B for flaggfargene rød, hvit og blå.

Todelt partisjonering  Målet er å finne en algoritme som omorganiserer en tabell slik at alle verdier som er mindre enn en skilleverdi kommer først. Vi bruker Eksempel 1.3.9 b) som utgangspunkt. Tabellen kan, men behøver ikke, inneholde selve skilleverdien. La f.eks. 10 være skilleverdi. To indekser v og h starter i hver sin ende av tabellen:

Det starter ved at v flyttes mot høyre så lenge som tilhørende tabellverdi er mindre enn 10. Da vil v stoppe ved 15. Så flyttes h mot venstre så lenge som tilhørende tabellverdi er større enn eller lik 10. Da vil h stoppe ved 5. De verdiene som v og h har passert får hvit bakgrunn:

Tabellen er nå (og vil inntil videre være) tredelt. Venstre del (hvit bakgrunn) har verdier som er mindre enn 10 og høyre del (også hvit bakgrunn) verdier som er større enn (eller lik) 10. Den midterste delen (grå bakgrunn) inneholder de «ukjente» verdiene, dvs. de som ennå ikke er undersøkt. Indeksene v og h skal hele tiden ligge i hver sin ende av den «ukjente» delen.

I tabellen over har indeksen v stoppet på en verdi (15) som er større enn 10 og h på en verdi (5) som er mindre enn 10. Hvis de to bytter plass, vil 5 høre til den venstre «hvite» delen og 15 til de som er større enn (eller lik) 10. Men da må også v og h flyttes videre:

Nå står allerede v på en verdi (13) som er større enn 10 og må stå der. Men h må flyttes videre mot venstre til første verdi som er mindre enn (eller lik) 10:

Verdiene til v og h (13 og 8) bytter plass, v og h flyttes én posisjon:

Vi fortsetter til den «ukjente» (grå) delen er tom. Da vil v høre til den første av de som er større enn (eller lik) 10 og h til den siste av de som er mindre enn 10:

Legg merke til at det i tabellen over ikke er noen spesiell rekkefølge på tallene i venstre del (de mindre enn 10) og heller ingen spesiell rekkfølge på de i høyre del.

Spesialtilfeller: Hvis alle er mindre enn skilleverdi, vil v havne utenfor når den flyttes mot høyre. Omvendt vil h havne utenfor til venstre hvis ingen er mindre enn skilleverdi.

Flg. metode (som legges i klassen Tabell) deler intervallet a[v:h] ved hjelp av idéene over:

  private static int parter0(int[] a, int v, int h, int skilleverdi)
  {
    while (true)                                  // stopper når v > h
    {
      while (v <= h && a[v] < skilleverdi) v++;   // h er stoppverdi for v
      while (v <= h && a[h] >= skilleverdi) h--;  // v er stoppverdi for h      

      if (v < h) bytt(a,v++,h--);                 // bytter om a[v] og a[h]
      else  return v;  // a[v] er nåden første som ikke er mindre enn skilleverdi
    }
  }              Programkode 1.3.9 a)

De to while-løkkene over inneholder v <= h. Hvis alle verdiene i a[v:h] er mindre enn skilleverdi, vil v stoppe på h + 1. Omvendt vil h stoppe på v − 1 hvis ingen av dem er mindre enn skilleverdi. Hvis vi ikke har noen av disse tilfellene, vil første ombytting gjøre at a[v] er mindre enn og a[h] større enn eller lik skilleverdi. De to blir da stoppverdier eller vaktposter. Dermed kan vi fjerne v <= h i resten av algoritmen. Se Oppgave 8.

Metoden parter0() er privat. En offentlig metode bør (slik som metodene i java.util) bruke halvåpent intervall, dvs. fra og til. Se Oppgave 1.

Eksempel 1.3.1 d): Eksempel 1.3.9 a) og b) kan løses ved hjelp av en offentlig versjon av Programkode 1.3.9 a) fra samleklassen Tabell (der det brukes fra og til). Se Oppgave 1.

  int[] a = {0,0,1,0,0,1,0,1,1,0,0,1,1,1,0,1,0,1,1,0};
  int[] b = {8,3,15,13,1,9,20,3,18,2,6,25,14,8,20,16,5,21,11,14};

  Tabell.parter(a, 0, a.length, 1);      // bruker 1 som skilleverdi
  Tabell.parter(b, 0, b.length, 10);     // bruker 10 som skilleverdi

  System.out.println(Arrays.toString(a));
  System.out.println(Arrays.toString(b));

  // Utskrift:
  // [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
  // [8, 3, 5, 8, 1, 9, 6, 3, 2, 18, 20, 25, 14, 13, 20, 16, 15, 21, 11, 14]

              Programkode 1.3.9 b)

Eksempel 1.3.9 e): Tabellen i Eksempel 1.3.9 b) ble brukt til å utlede algoritmen for partisjonering, men den inneholdt ikke selve skilleverdien. Tabellen i Figur 1.3.9 g) nedenfor inneholder tallene fra 1 til 20. Den skal partisjoneres med 11 som skilleverdi. Her kan en som en øvelse på papir og med penn (se Oppgave 2) finne hvilket resultat algoritmen vil gi. Fasit får en så ved å kjøre Programkode 1.3.9 c) under. Se også Oppgave 1. Se spesielt på hvor skilleverdien havner. Den behøver ikke havne på skillet mellom de to delene:

  int[] a = {13,2,8,10,16,9,15,4,18,14,12,11,7,5,3,6,17,1,20,19};
  int pos = Tabell.parter(a, 11);   // bruker 11 som skilleverdi
  System.out.println(pos + "  " + Arrays.toString(a));

              Programkode 1.3.9 c)

Effektivitet: Hvor effektiv er parter0()? Skilleverdien sammenlignes med alle verdiene. Hvis det er n av dem, blir det derfor minst n sammenligninger (og maksimalt n + 1 stykker). Se Oppgave 5. Men hva med ombyttinger? For å gjøre analysen enklere antar vi at tabellen inneholder en permutasjon av tallene fra 1 til n og at et av dem, f.eks. tallet s, brukes som skilleverdi. Etter partisjoneringen vil de som er mindre enn s (tall fra 1 til s − 1) havne først, dvs. på de s − 1 første plassene. Det betyr at alle som ikke er mindre enn s blant de s − 1 første i den opprinnelige tabellen, vil bli flyttet ved ombyttinger. Det gir flg. setning:

Tabellen i Figur 1.3.9 g) inneholder en permutasjon av tallene fra 1 til 20. La s = 11 være skilleverdi. Blant de s − 1 = 10 første tallene er det fire (17, 20, 11 og 15) som ikke er mindre enn s. Dermed fire ombyttinger. Vi kan snu dette på hodet. Antallet ombyttinger blir også lik antallet tall blant de n − s + 1 siste som er mindre enn s. Flg. metode finner antallet:

  public static int antallOmbyttinger(int[] a, int s)
  {
    int antall = 0, m = s - 1;
    for (int i = 0; i < m; i++) if (a[i] > m) antall++;
    return antall;
  }
              Programkode 1.3.9 d)

Hvor mange ombyttinger er det i gjennomsnitt i partisjoneringsalgoritmen? Under bestemte forutsetninger kan antallet beregnes eksakt. Vi har flg. setning (se Avsnitt 1.3.16):

Vi kan telle opp ved hjelp av metoden Programkode 1.3.9 d). I flg. kode telles ombyttingene i alle permutasjonene av tallene fra 1 til 10 og med hvert av tallene som skilleverdi:

  int[] a = {1,2,3,4,5,6,7,8,9,10};
  boolean flere = true;
  int antall = 0;

  while (flere)
  {
    for (int s = 1; s <= a.length; s++) antall += antallOmbyttinger(a, s);
    flere = Tabell.nestePermutasjon(a);
  }

  System.out.println(antall);  // Utskrift: 59875200

              Programkode 1.3.9 e)

Det totale antallet ble 59 875 200 = 2⁷·3⁵·5²·7·11. Gjennomsnittet finner vi ved først å dele med 10 = 2·5 siden det er 10 skilleverdier for hver permutasjon. Deretter deler vi med antall permutasjoner som er 10! = 3 628 800 = 2⁸·3⁴·5²·7. Forkorting gir 33/20 som gjennomsnitt. Men det er eksakt lik (n2 - 1)/6n = (10² - 1)/60 = 99/60 = 33/20. Se også Oppgave 6.

I Eksempel 1.3.9 e) inngikk skilleverdien 11 i tabellen. Etter partisjoneringen havnet den litt til høyre for skillet mellom de to delene. Et mål kan være å få en skilleverdi, som hører til tabellen, til å havne nøyaktig på skillet mellom de to delene. Da er den på rett sortert plass:

I tabellen i Eksempel 1.3.9 e) har tallet 11, som ble brukt som skilleverdi, en bestemt indeks m. I flg. tabell er indeksene v, m og h markert:

Verdiene på indeks m og h (dvs. 11 og 19) bytter plass og indeks h flyttes én mot venstre:

En partisjonering av intervallet a[v:h] − den grå delen i Figur 1.3.9 i) over − med bakerste verdi (11) som skilleverdi, gir flg. oppdeling der indeks k angir skillet:

Tallet 11 som opprinnelig hadde indeks m i Figur 1.3.9 h), ble først flyttet bakerst. Den vil komme på rett sortert plass hvis den byttes med verdien (tallet 12) på indeks/plass k:

En vilkårlig tabellverdi, f.eks. a[indeks], kan være skilleverdi i parter0(). To ombyttinger (en før og en etter) får den inn på rett sortert plass (flg. metode hører til klassen Tabell):

  private static int sParter0(int[] a, int v, int h, int indeks)
  { 
    bytt(a, indeks, h);           // skilleverdi a[indeks] flyttes bakerst
    int pos = parter0(a, v, h - 1, a[h]);  // partisjonerer a[v:h - 1]
    bytt(a, pos, h);              // bytter for å få skilleverdien på rett plass
    return pos;                   // returnerer posisjonen til skilleverdien
  }
              Programkode 1.3.9 f)

Det er ingen ekstra sammenligninger i sParter0(). Hvis intervallet a[v:h] har n verdier, blir det n − 1 stykker i parter0() siden kallet skjer på a[v:h-1]. Det blir to ekstra ombyttinger. Det kan vises at hvis sParter0() brukes på en permutasjon av tallene fra 1 til n og med en tilfeldig indeks, vil gjennomsnittlig antall ombyttinger bli eksakt 2 + (n − 2)/6 = (n + 10)/6.

Hvis vi har offentlige versjoner av sParter0() (se Oppgave 9) vil flg. kode gjøre som i Fig. 1.3.9 h) − k). Legg merke til at tabelleverdien 11 også ligger på plass/indeks 11:

  int[] a = {13,2,8,10,16,9,15,4,18,14,12,11,7,5,3,6,17,1,20,19};
  int k = Tabell.sParter(a, 11);  // verdi 11 ligger på indeks 11
  System.out.println(k + " " + Arrays.toString(a));  // Utskrift:
  // 10 [1, 2, 8, 10, 6, 9, 3, 4, 5, 7, 11, 19, 14, 18, 15, 16, 17, 13, 20, 12]

              Programkode 1.3.9 g)

Utskriften fra Programkode 1.3.9 g) viser at 11 er på rett sortert plass. Alle verdiene til venstre for 11 er mindre og alle de til høyre er større.

Kvikksortering er en systematisk anvendelse av sParter0(). Først velges en tabellverdi som skilleverdi. Et kall på sParter0() får den inn på rett sortert plass k. Dette gjentas på hver side av k. Osv. Det beste er en skilleverdi som gjør de to sidene noenlunde like i størrelse. Men med en ukjent tabell er det ingen annen mulighet enn å velge vilkårlig. F.eks. den første, den midterste eller den siste. En bedre strategi er å ta den «midterste» av de tre. Se Oppgave 13. Her velger vi den på midten av a[v:h] (m = (v + h)/2) som skilleverdi:

Vi bruker på nytt tabellen fra Figur 1.3.9 h) som utgangspunkt, men denne gangen bruker vi verdien på midten, dvs. a[m] der m = (v + h)/2, som skilleverdi:

Metodekallet sParter0(a,v,h,(v + h)/2) vil gjøre at tabellen blir slik:

De «grå» delene a[v:k−1] og a[k+1:h] er separate deler. Hvis a[v:k−1] partisjoneres mhp. midtverdien (6), vil dens verdier fortsatt ligge til venstre for 14. Hvis a[k+1:h] partisjoneres mhp. dens midtverdi (17) blir det tilsvarende. Gjør vi begge deler, får vi flg. resultat:

Dette fortsetter ved at sParter0() kalles på hver av de fire «grå» delene. Osv. Hvis et intervall (en «grå» del) er tomt eller har kun ett element, stopper vi siden det er sortert.

  private static void kvikksortering0(int[] a, int v, int h)  // en privat metode
  {
    if (v >= h) return;  // a[v:h] er tomt eller har maks ett element
    int k = sParter0(a, v, h, (v + h)/2);  // bruker midtverdien
    kvikksortering0(a, v, k - 1);     // sorterer intervallet a[v:k-1]
    kvikksortering0(a, k + 1, h);     // sorterer intervallet a[k+1:h]
  }

  public static void kvikksortering(int[] a, int fra, int til) // a[fra:til>
  {
    fratilKontroll(a.length, fra, til);  // sjekker når metoden er offentlig
    kvikksortering0(a, fra, til - 1);  // v = fra, h = til - 1
  }

  public static void kvikksortering(int[] a)   // sorterer hele tabellen
  {
    kvikksortering0(a, 0, a.length - 1);
  }
              Programkode 1.3.9 h)

Kvikksortering kaller seg selv to ganger. Det kalles rekursjon. Mer om det i Avsnitt 1.5.7. Metodekallene stopper når vi får v >= h, og det vil før eller senere skje siden kallene utføres på intervaller som er kortere enn a[v:h]. Det ene kan i verste fall være tomt. Det andre er dermed bare én kortere enn a[v:h]. Det gjør at metoden i verste fall blir av kvadratisk orden. Men i gjennomsnitt vil lengden til intervallene a[v:k−1] og a[k+1:h] ikke skille seg så mye. Det gjør at kvikksortering i gjennomsnitt er av orden n log₂(n). Mer om dette senere.

Hvis metodene i Programkode 1.3.9 h) ligger i samleklassen Tabell, vil flg. være kjørbart:

  int[] a = Tabell.randPerm(20);           // en tilfeldig permutasjon
  Tabell.kvikksortering(a);                // sorterer
  System.out.println(Arrays.toString(a));  // skriver ut

              Programkode 1.3.9 i)

Oppsummering - kvikksortering:

• Navn: Kvikksortering (eng: quick sort) ble «oppfunnet» allerede i 1959 av briten Tony Hoare og er kjent som den beste (mest effektive) generelle sorteringsteknikken. I java.util er det en optimalisert versjon (a dual-pivot quicksort) som brukes for standardtypene (byte, short, int, long, float, double, char). Men for generiske typer brukes (i java.util) imidlertid flettesortering (eng: merge sort).
• Idé og effektivitet: Den kan ses på som en anvendelse av partisjonering, dvs. å dele en tabell (eller et tabellintervall) i to deler mhp. en skilleverdi (eng: pivot). Et enkelt valg av skilleverdi kan være den første eller siste verdien. Men det vil føre til at den får orden n² hvis tabellen allerede er sortert. Da er det bedre å velge den midterste. Men i optimaliserte versjoner gjøres valget på en «lurere» måte. Men uansett vil det være mulig (men ikke enkelt) å konstruere en tabell som gjør at den får orden n². Men i gjennomsnitt er den garantert av orden n log(n). Se Oppgave 17. En mulig optimaliseringsteknikk er å skifte til innsettingssortering for små intervaller (lengde mindre enn 47 brukes i java.util). Den er en «på plass»-algoritme (eng: in place), dvs. at den ikke trenger noen hjelpetabell.
• Ulemper: Den optimaliserte versjonen vil, som nevnt over, kunne være av kvadratisk orden i (svært) spesielle tilfeller. Hvis en trenger en teknikk som alltid er n log(n), må en velge noe annet - f.eks. heapsortering som alltid er av orden n log(n), men som ikke er fullt så god som kvikksortering i gjennomsnitt. Et mulig valg er å kombinere de to slik det er gjort i introsort. En (liten) ulempe er at den ikke er stabil, dvs. like verdier får ikke nødvendigvis samme innbyrdes rekkefølge etter sorteringen som de hadde før.
• Konklusjon: Dette vil normalt være førstevalget når en trenger en sorteringsalgoritme.

Vi kan også bruke partisjonering til å finne den m-te minste verdien i en (usortert) tabell, dvs. den verdien som ville ha kommet på plass nr m hvis vi hadde sortert tabellen. F.eks. er den 0-te minste verdien det samme som den minste og den 1-te minste verdien det samme som den andre eller nest minste verdien.

Kvikksøk bruker idéen i kvikksortering. En partisjonering med midtverdien som skilleverdi, vil gjøre at den havner på rett sortert plass (indeks k). Hvis det er lik indeks m, er vi ferdige. Hvis ikke må vi lete videre på venstre side hvis m < k og på høyre side hvis m > k. Flg. metode flytter om på på verdiene i tabellen a slik at den m-te verdien til slutt havner på indeks m. Hvis tabellen a har lengde n, vil kvikksøk får orden n siden sParter0() kalles kun én gang i hver iterasjon. I Oppgave 14 blir du bedt om å teste metoden.

  public static int kvikksøk(int[] a, int m)
  {
    if (m < 0 || m >= a.length)
      throw new IllegalArgumentException("m(" + m + ") er ulovlig!");

    int v = 0, h = a.length - 1;  // intervallgrenser

    while (true)
    {
      int k = sParter0(a,v,h,(v + h)/2);   // se Programkode 1.3.9 f)
      if (m < k) h = k - 1;
      else if (m > k) v = k + 1;
      else return k;
    }
  }           Programkode 1.3.9 j)

Medianen til en samling verdier er den som ville ha havnet på midten etter en sortering. Hvis antallet er odde, er dette veldefinert. Hvis ikke, defineres medianen som gjennomsnittet av de to verdiene på hver side av «midten». Vi kan bruke kvikksøk() til å finne medianen:

  public static double median(int[] a)
  {
    if (a.length == 0) throw new NoSuchElementException("Tom tabell!");

    int k = kvikksøk(a, a.length/2);
    return (a.length & 1) == 0 ? (a[k-1] + a[k])/2.0 : a[k];
  }
              Programkode 1.3.9 k)

  Oppgaver til Avsnitt 1.3.9

  public static int teller = 0;

  private static boolean comp(int x, int y)
  {
    teller++;  // øker for hver sammenligning
    return x < y;
  }

  1.3.10  Tredelt partisjonering

Hollands flagg

Eksempel 1.3.9 c) har en tabell som kun inneholder bokstavene R, H og B. Oppgaven er å få den omorganisert slik at først kommer R-ene, så H-ene og til slutt B-ene. Oppgaven har (av E. W. Dijkstra) fått navnet «The Dutch National Flag Problem». Bokstavene stå for fargene i det hollandske flagget (rød, hvit og blå). Målet er, med minst mulig «arbeid», å få tabellen «lik» flagget, dvs. det «røde» først, så det «hvite» og det «blå» til slutt.

Tabellen fra Eksempel 1.3.9 c) så slik ut:

Vi ønsker (med minst mulig «arbeid») at den skal bli slik:

Et mulighet å bruke vanlig partisjonering to ganger. Først separeres R-ene fra resten av bokstavene og legges først. Så deles resten av tabellen opp i H-er og B-er. For eksempel slik:

  public static void omorganiser(char[] c)
  {
    int v = 0, h = c.length-1;
    while (v <= h) if (c[v] == 'R') v++; else  Tabell.bytt(c,v,h--);
    h = c.length-1;  // nå ligger R-ene først
    while (v <= h) if (c[v] == 'H') v++; else  Tabell.bytt(c,v,h--);
  }
                 Programkode 1.3.10 a)

La c ha n verdier som er R, H eller B. Dermed blir det 3ⁿ mulige tabeller med i gjennomsnitt 1/3 R-er, 1/3 H-er og 1/3 B-er. I første while-løkke i Programkode 1.3.10 a) blir det alltid n sammenligninger. I andre like mange som det er H-er og B-er, dvs. i gjennomsnitt 2n/3 stykker. Til sammen 5n/3 sammenligninger i gjennomsnitt. I første while-løkke blir det én ombytting hver gang c[v] er ulik R. Dvs. i gjennomsnitt 2n/3 ganger. I den andre løkken blir det en hver gang c[v] er ulik H, dvs. n/3 ganger. Sammenlagt n ombyttinger i gjennomsnitt.

Det er ikke mulig med færre sammenligninger i gjennomsnitt enn i Programkode 1.3.10 a). Hver verdi må undersøkes minst én gang. Da trengs én sammenligning for å avgjøre om den er en R. Hvis ikke, én til for å avgjøre om det er en H eller B. I gjennomsnitt (1 · 1/3 + 2 · 2/3)n = 5n/3 stykker. Men det er mulig å gjøe det med færre ombyttinger.

Vi kan gjøre som i Avsnitt 1.3.9, men nå ha tabellen firedelt. Først R-er, så den «ukjente» delen, så H-er og til slutt B-er. Figuren viser hvordan det kan se ut etter noen iterasjoner:

Indeksene v og h står først og sist i den «ukjente» delen og k sist i H-delen (h = k hvis ingen H-er). Vi har tre muligheter for c[h]. Hvis den er lik R, bytter vi c[h] og c[v]. Da blir den én R mer og v må økes med 1. Hvis c[h] er lik H flytter vi h en mot venstre. Hvis c[h] er lik B, bytter vi c[h] og c[k] og reduserer både h og k med 1. Algoritmen går så lenge som v <= h:

  public static void omorganiser(char[] c)  // ny versjon
  {
    int v = 0, h = c.length-1, k = h;       // v forrest, h og k bakerst
    while (v <= h)
    {
      if (c[h] == 'R') Tabell.bytt(c,v++,h);
      else if (c[h] == 'H') h--;
      else  Tabell.bytt(c,h--,k--);
    }
  }              Programkode 1.3.10 b)

Det er ikke vanskelig å se at det utføres nøyaktig 5n/3 sammenligninger i gjennomsnitt i Programkode 1.3.10 b). I hver iterasjon vil det bli én ombytting hvis c[h] er lik R, ingen hvis den er lik H og én hvis den er lik B. Det gir 2n/3 ombyttinger i gjennomsnitt. Med andre ord er dette en del bedre enn i Programkode 1.3.10 a).

Det er mulig med noen færre ombyttinger. Hvis c[h] er lik R eller H samtidig som v er lik h, er ombyttingen unødvendig. Den kan fjernes ved å la while-løkken gå så lenge som v < h og så behandle v lik h spesielt. Det er også unødvendig å bytte om hvis c[h] er lik B og h er lik k. En test på om h er lik k vil imidlertid koste mer enn vi tjener inn. Men Programkode 1.3.10 b) kan endres slik at det gjennomsnittlig antall ombyttinger blir (se Oppgave 3):

(*)   2n/3 - 4/3 + (2/3)n

Det finnes 3ⁿ forskjellige n-permutasjoner med repetisjon som inneholder R, H eller B. Her definerer vi, med tanke på leksikografisk ordning, at R kommer foran H som igjen kommer foran B. Flg. metode gir den neste n-permutasjonen med repetisjon:

  public static boolean nestePermutasjon(char[] c)
  {
    int n = c.length, i = n - 1;           // i starter bakerst i c
    while (i >= 0 && c[i] == 'B') i--;
    if (i < 0) return false;               // tabellen c har kun B-er

    c[i] = (c[i] == 'R' ? 'H' : 'B');
    for (int j = i+1; j < n; j++) c[j] = 'R';
    return true;                           // c inneholder en ny permutasjon
  }
                   Programkode 1.3.10 c)

Hvis vi starter med RRR, vil neste bli RRH, så RRB, så RHR, osv. Flg. kodebit gir alle:

  char[] c = "RRR".toCharArray();
  boolean flere = true;

  while (flere)
  {
    Tabell.skrivln(c);
    flere =  nestePermutasjon(c);
  }
                Programkode 1.3.10 d)

Vi kan finne det gjennomsnittlige antallet ombyttinger som utføres i Programkode 1.3.10 b) ved å bruke Programkode 1.3.10 d) til å generere alle mulige n-permutasjoner (med repetisjon). Vi må imidlertid lage en omorganiser-metode der ombyttingene telles opp:

  public static int antallOmorganiser(char[] c)
  {
    int v = 0, h = c.length-1, k = h;  // v forrest, h og k bakerst
    int antall = 0;                    // antall ombyttinger

    while (v <= h)
    {
      if (c[h] == 'R') { Tabell.bytt(c,v++,h); antall++; }
      else if (c[h] == 'H') h--;
      else  { Tabell.bytt(c,h--,k--); antall++; }
    }
    return antall;
  }
                 Programkode 1.3.10 e)

Vi kan generere alle permutasjoner og så la metoden over telle opp. Gjennomsnittlig antall ombyttinger i Programkode 1.3.10 b) var 2n/3. Hvis n = 3 får vi totalt 27 permutasjoner og dermed 27*2*3/3 = 54 ombyttinger tilsammen. Flg. programbit bør derfor gi 54 som utskrift:

  char[] c = "RRR".toCharArray(), d = new char[c.length];
  boolean flere = true; int antall = 0;  // antall ombyttinger

  while (flere)
  {
    System.arraycopy(c,0,d,0,c.length);  // kopierer c over i d
    antall += antallOmorganiser(d);      // omorganiserer d
    flere =  nestePermutasjon(c);        // ny permutasjon
  }
  System.out.println(antall);            // Utskrift: 54

                 Programkode 1.3.10 f)

Vi kan gå fra R, H og B til tre vilkårlige tegn ved hjelp av parameterverdier. Se Oppgave 2.

  Oppgaver til Avsnitt 1.3.10

1.	Gjennomsnittlig antall ombyttinger som metoden i Programkode 1.3.10 b) gjør for de 3n forskjellige n-permutasjonene, er 2n/3. Hva blir det totale antallet ombyttinger for alle permutasjonene hvis n = 4, 5 og 6? Test med Programkode 1.3.10 f).
2.	Lag generaliserte versjoner av Programkode 1.3.10 b), 1.3.10 c) og 1.3.10 e) der de tre aktuelle tegnene oppgis som parameterverdier. Bruk dem i 1.3.10 f).
3.	En ombytting er unødvendig hvis c[h] er lik R eller H samtidig som v er lik h. Det er også unødvendig å bytte om hvis c[h] er lik B samtidig som h er lik k. Lag en ny versjon av antallOmorganiser uten disse ombyttingene. Hvis den brukes i Programkode 1.3.10 f), blir svaret lik formelen i (*) ganget med 3n. Sjekk det for noen verdier av n.
4.	Bruk idéen fra Programkode 1.3.10 b) til å lage en parter-metode med to skilleverdier s1 og s2 der s1 <= s2. Første del skal inneholde de som er mindre enn s1, andre del de som er mindre enn s2 (men ikke mindre enn s1) og siste del av de som ikke er mindre enn s2.
5.	Mauritius har flaggfargene rød, blå, gul og grønn. Vi bruker Mauritius engelsk (red, blue, yellow, green) siden både gul og grønn har g. Gitt en tabell med tegnene R, B, Y og G. Lag en algoritme som gjør at R-ene kommer først, så B-ene, så Y-ene og til slutt G-ene. Bruk færrest mulig sammenligninger og ombyttinger i løsningen av «Det mauritiske flaggproblemet».

  1.3.11  Fletting og flettesortering
Å flette (eng: merge) betyr å forene. F.eks. å tvinne sammen flere enheter til en felles enhet. Vi kan flette hår eller vi kan flette kvister til en kurv. Hvis en vei med to felter i samme retning snevres inn til kun ett felt, er det mest «rettferdig» at trafikken «flettes sammen».

I databehandling er det aktuelt å flette to eller flere sekvensielle enheter (f.eks. tegnstrenger, tabeller, lister eller filer) til en felles enhet av samme type. En enkel form for fletting av to enheter er at annenhver verdi kommer fra den ene og annenhver fra den andre. Hvis det er ulikt antall, må vi ha en regel for de som er «til overs». De kan f.eks. legges inn bakerst:

  public static int[] enkelFletting(int[] a, int[] b)
  {
    int[] c = new int[a.length + b.length];  // en tabell av rett størrelse
    int i = 0, j = 0, k = 0;                 // løkkevariabler

    while (i < a.length && j < b.length)
    {
      c[k++] = a[i++];      // først en verdi fra a
      c[k++] = b[j++];      // så en verdi fra b
    }
    // vi må ta med resten
    while (i < a.length) c[k++] = a[i++];
    while (j < b.length) c[k++] = b[j++];

    return c;
  }
              Programkode 1.3.11 a)

Hvis a og b er like lange, vil ingen av de to siste while-løkkene utføres. Med ulike lengder vil kun den som hører til den lengste, utføres. Flg. eksempel viser hvordan den virker:

  int[] a = {1,3,5,7,9,11}, b = {2,4,6,8,10};  // to heltallstabeller
  int[] c = enkelFletting(a, b);
  System.out.println(Arrays.toString(c));
  // Utskrift: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

              Programkode 1.3.11 b)

Det blir på samme måte for andre typer strukturer, f.eks. to tegnstrenger. Det som vil være forskjellig er hvordan en henter ut en og en verdi fra de to strukturene og hvordan man setter inn annenhver gang fra de to. Se Oppgave 1b).

Sortert fletting Anta at vi har to sekvensielle datastrukturer, f.eks. to tabeller, som begge er sortert. En viktig oppgave er da å kunne flette dem sammen til en datastruktur som er sortert. Da blir det normalt feil bruke regelen om «annenhver verdi». Vi må gjøre det på en annen måte. Se på flg. eksempel med to heltallstabeller:

I Figur 1.3.11 a) har vi to sorterte tabeller a og b med henholdsvis 7 og 10 verdier. De skal flettes sammen og legges i en tredje tabell c slik at c blir sortert. Den har plass til de 7 + 10 = 17 verdiene. Første posisjon (posisjon 0) i a, b og c er markert med henholdsvis i, j og k.

Algoritme: Sammenlign a[i] og b[j]. Hvis a[i] er mindre enn eller lik b[j], kopieres den over i posisjon k i c og både i og k økes med 1. Hvis ikke, dvs. hvis b[j] er minst, kopieres den over i posisjon k i c og både j og k økes med 1. Etter fem «runder» får vi:

Det er ofte aktuelt å kunne flette sammen to sorterte tabellintervaller, f.eks. de to halvåpne intervallene a[0:m> og b[0:n>. Flg. metode gjør dette og returnerer antallet. Tabellen c må være stor nok, dvs. ha plass til minst m + n verdier. Metoden legges i samleklassen Tabell:

  public static int flett(int[] a, int m, int[] b, int n, int[] c)
  {
    int i = 0, j = 0, k = 0;
    while (i < m && j < n) c[k++] = a[i] <= b[j] ? a[i++] : b[j++];

    while (i < m) c[k++] = a[i++];   // tar med resten av a
    while (j < n) c[k++] = b[j++];   // tar med resten av b

    return k;   // antallet verdier som er lagt inn i c
  }
              Programkode 1.3.11 c)

I Programkode 1.3.11 c) blir a[i] <= b[j] utført  m + n – 1 ganger hvis tallene i a og b er slik at a[i] <= b[j] blir sann/usann annenhver gang. F.eks. hvis a = { 1, 3, 5, 7, 9 } og b = { 2, 4, 6, 8, 10 }. Hvis siste verdi i a er mindre enn første i b, vil a[i] <= b[j] bli utført m ganger, og hvis omvendt, n ganger. Normalt et sted mellom min( m , n ) og  m + n – 1. Det betyr at algoritmen har orden m + n i gjennomsnitt.

Flg. metode fletter sammen to hele tabeller ved hjelp av flett():

  public static int flett(int[] a, int[] b, int[] c) // legges i samleklassen Tabell
  {
    return flett(a, a.length, b, b.length, c);
  }
              Programkode 1.3.11 d)

Flg. eksempel viser hvordan dette kan brukes:

  int[] a = {1,3,4,6,9,9,11}, b = {2,3,5,6,7,8,9,10,12,14};  // sorterte tabeller
  int[] c = new int[a.length + b.length];     // nå er c stor nok
  Tabell.flett(a,b,c);                        // fletter sammen
  Tabell.skriv(c);  // Utskrift: 1 2 3 3 4 5 6 6 7 8 9 9 9 10 11 12 14

              Programkode 1.3.11 e)

Fletting er en viktig teknikk. F.eks. er fletting den essensielle delen i flettesortering (eng: merge sort). Idéen er at en tabell kan sorteres ved at dens to halvdeler sorteres hver for seg og at de så flettes sammen. Dette gjentas rekursivt for hver av de to delene. I flettesortering er det sorterte nabointervaller som flettes sammen. Se på flg. eksempel:

Intervallene a[fra:m> (hvit del med tall) og a[m:til> (den grå delen) skal flettes sammen. Først kopieres a[fra:m> over i b. Den må minst ha plass til n verdier der n = m – fra:

Neste skritt er å flette sammen b[0:n> og a[m:til>. Legg spesielt merke til at hvis vi i flettingen blir ferdig med verdiene i b[0:n> først, trenger vi ikke gjøre noe med det som ligger igjen bakerst i a[m:til>. De ligger der de skal ligge:

Flg. private hjelpemetode fletter b[0:n> og a[m:til> over i a[fra:til>:

  private static void flett(int[] a, int[] b, int fra, int m, int til)
  {
    int n = m - fra;                // antall elementer i a[fra:m>
    System.arraycopy(a,fra,b,0,n);  // kopierer a[fra:m> over i b[0:n>

    int i = 0, j = m, k = fra;      // løkkevariabler og indekser

    while (i < n && j < til)        // fletter b[0:n> og a[m:til> og
    {                               // legger resultatet i a[fra:til>
      a[k++] = b[i] <= a[j] ? b[i++] : a[j++];
    }

    while (i < n) a[k++] = b[i++];  // tar med resten av b[0:n>
  }
              Programkode 1.3.11 f)

Flg. rekursive (og private) metode benytter flett-metoden i Programkode 1.3.11 f):

  private static void flettesortering(int[] a, int[] b, int fra, int til)
  {
    if (til - fra <= 1) return;   // a[fra:til> har maks ett element
    int m = (fra + til)/2;        // midt mellom fra og til

    flettesortering(a,b,fra,m);   // sorterer a[fra:m>
    flettesortering(a,b,m,til);   // sorterer a[m:til>

    if (a[m-1] > a[m]) flett(a,b,fra,m,til);  // fletter a[fra:m> og a[m:til>
  }
              Programkode 1.3.11 g)

I koden over deles a[fra:til> på midten og metoden kalles (rekursjon) først på a[fra:m> og så på a[m:til>. Etterpå vil de være sortert og kan flettes sammen. Legg merke til setningen: if (a[m-1] > a[m]). Intervallet a[fra:til> er allerede sortert hvis den siste i a[fra:m> er mindre enn eller lik den første i a[m:til>. Midtdelingen gjør at dette blir av orden n log₂(n) og dermed en effektiv metode. Flg. offentlige metode sorterer en hel tabell:

  public static void flettesortering(int[] a)
  {
    int[] b = Arrays.copyOf(a, a.length/2);   // en hjelpetabell for flettingen
    flettesortering(a,b,0,a.length);          // kaller metoden over
  }
              Programkode 1.3.11 h)

Hvis metodene over er lagt i samleklassen Tabell, vil flg. kodebit være kjørbar:

  int[] a = Tabell.randPerm(15);
  Tabell.flettesortering(a);
  Tabell.skriv(a); // Utskrift: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

              Programkode 1.3.11 i)

Union  La a[0:m> være sortert med ulike verdier. Tilsvarende for b[0:n>. De kan da ses på som to mengder. Vi finner «unionen» ved å flette dem sammen. En verdi som ligger i begge to tas med kun én gang. Flg. metode legger «unionen» i tabellen c og returnerer antallet:

  public static int union(int[] a, int m, int[] b, int n, int[] c)
  {
    int i = 0, j = 0, k = 0;             // indekser for a, b og c
    while (i < m && j < n)
    {
      if (a[i] < b[j]) c[k++] = a[i++];  // tar med a[i]
      else if (a[i] == b[j])             // a[i] og b[j] er like
      {
        c[k++] = a[i++]; j++;            // tar med a[i], men ikke b[j]
      }
      else  c[k++] = b[j++];             // tar med b[j]
    }

    while (i < m) c[k++] = a[i++];       // tar med resten av a[0:m>
    while (j < n) c[k++] = b[j++];       // tar med resten av b[0:n>

    return k;                            // antall verdier i unionen
  }
              Programkode 1.3.11 j)

Metoden union() returnerer antallet. Det er mindre enn m + n hvis a og b har felles verdier. Flg. metode finner «unionen» av hele tabeller:

  public static int union(int[] a, int[] b, int[] c)
  {
    return union(a, a.length, b, b.length, c);
  }
              Programkode 1.3.11 k)

Hvis metodene over er lagt i samleklassen Tabell, vil flg. kodebit være kjørbar:

  int[] a = {1,3,4,6,9,11,13};               // ingen like verdier
  int[] b = {2,3,5,6,7,8,9,10,11,12};        // ingen like verdier
  int[] c = new int[a.length + b.length];    // c er nå stor nok

  System.out.println(Arrays.toString(Arrays.copyOf(c, union(a, b, c))));
  // Utskrift: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]

              Programkode 1.3.11 l)

Snittet av to mengder er det de har felles. Vi kan finne snittet ved å bruke en fletteteknikk:

  public static int snitt(int[] a, int m, int[] b, int n, int[] c)
  {
    int i = 0, j = 0, k = 0;             // indekser for a, b og c
    while (i < m && j < n)
    {
      if (a[i] < b[j]) i++;              // hopper over a[i]
      else if (a[i] == b[j])             // a[i] og b[j] er like
      {
        c[k++] = a[i++]; j++;            // tar med a[i], men ikke b[j]
      }
      else  j++;                         // hopper over b[j]
    }

    return k;                            // antall i snittet
  }

  public static int snitt(int[] a, int[] b, int[] c)  // hele tabeller
  {
    return snitt(a, a.length, b, b.length, c);
  }
              Programkode 1.3.11 m)

Hvis metodene over er lagt i samleklassen Tabell, vil flg. kodebit være kjørbar:

  int[] a = {1,3,4,6,9,11,13};                       // ingen like verdier
  int[] b = {2,3,5,6,7,8,9,10,11,12};                // ingen like verdier
  int[] c = new int[Math.min(a.length,b.length)];    // c er nå stor nok

  System.out.println(Arrays.toString(Arrays.copyOf(c, snitt(a, b, c))));
  // Utskrift: [3, 6, 9, 11]

              Programkode 1.3.11 n)

I oppgavene nedenfor blir du bedt om, ved hjelp av fletteteknikk, å lage metoder for differens, xunion (eksklusiv union eller symmetrisk differens) og inklusjon.

  Oppgaver til Avsnitt 1.3.11

  1.3.12  Inversjoner
La a være en tabell med sorterbare verdier (f.eks. heltall). Definisjon 1.3.2 a) sier at et par av verdier danner en inversjon hvis de er i utakt, dvs. hvis den første av dem er større enn den andre. I Avsnitt 1.3.2 fant vi at en permutasjon av heltallene fra 1 til n kunne inneholde fra 0 til n(n − 1)/2 inversjoner. Ingen inversjoner betyr at permutasjonen er sortert stigende og n(n − 1)/2 stykker at den er sortert motsatt vei, dvs. avtagende.

En anvendelse:  Per og Kari skal tippe resultatet i en konkurranse. Konkurransen har A, B, C, D og E som deltagere. Kari tipper at D blir nr. 1, B nr. 2, E nr. 3, A nr. 4 og C nr. 5. Per tipper at B blir nr. 1, A nr. 2, D nr. 3, E nr. 4 og C nr. 5.

Konkurransen endte imidlertid med at D vant, A ble nr. 2, C nr. 3, B nr. 4 og E sist. Hverken Per eller Kari tippet rett. Men hvem var best? Spørsmålet kan ikke besvares før det er bestemt en regel for hvordan tipperesultater skal rangeres. F.eks. har Kari tippet vinneren riktig. Da kan man si at Kari har det beste tipperesultatet hvis det er viktigst å tippe rett vinner. Men her skal vi bruke en regel der det er like viktig med rett på alle plasser. Dermed: «det resultatet som har færrest inversjoner er best».

I forhold til det riktige resulatet gir tipset til Kari permutasjonen 1, 4, 5, 2, 3 siden hun har tippet D riktig på 1. plass, B (som ble nr. 4) på 2.plass, E (som ble nr. 5) på 3. plass, osv. Tilsvarende gir tipset til Per permutasjonen 4, 2, 1, 5, 3. Tipset til Kari har 4 inversjoner og det til Per 5 stykker. Kari har færrest inversjoner og har dermed det beste tipset.

Programkode 1.3.2 a) inneholder en enkel n² metode for å finne antallet inversjoner i en tabell. Men ved å bruke en fletteteknikk (se Avsnitt 1.3.11) er det mulig å lage en metode av orden n log(n).

Figur 1.3.12 a) under inneholder en tabell med 20 tall som er delt i to (hvit og grå):

I tabellen over er f.eks. (4,3), (4,1) og (17,10) inversjoner av den første typen, dvs. av typen (x, y) der begge verdiene ligger i venstre del (den «hvit» delen). Inversjonene (18,9), (9,2) og (9,7) har begge verdiene i høyre del (den «grå» delen). Mens (4,2), (20,18) og (11,9) er av den tredje typen: første verdi i venstre del og andre verdi i høyre del. Tabellen har tilsammen 80 inversjoner og det er flest av den tredje typen. Se Oppgave 1.

Ved hjelp av observasjonen kan vi sette opp flg. oppskrift for en algoritme:

1. Del tabellen i to deler - venstre og høyre del.
2. Finn antall inversjoner (x, y) i venstre del.
3. Finn antall inversjoner (x, y) i høyre del.
4. Finn antall inversjoner (x, y) der x ligger i venstre del og y i høyre del.
5. Summen av disse antallene er antallet inversjoner i hele tabellen.

Vi setter opp tallene fra Figur 1.3.12 a) på nytt, men med hver av de to halvdelene sortert:

Dette endrer ikke antallet inversjoner av den tredje typen, dvs. inversjoner (x, y) der x ligger i venstre og y i høyre del. Det spiller ingen rolle hvor x og y ligger så lenge de er på hver sin side. Det gjør det raskere å finne antallet. De ni tallene tallene i venstre del fra 3 og utover danner en inversjon med tallet 2. De syv tallene i venstre del fra 6 og utover danner en inversjon med 5. Osv. På denne måten finner vi fort at det er 40 stykker av den tredje typen.

En algoritme: La tabellen hete a og hjelpetabellen b. Vi starter med å kopiere den venstre delen av a over i hjelpetabellen b (slik som i flettesortering):