Løsningsforslag - oppgaver i Avsnitt 1.3.9


Oppgave 1 

  // intervallet a[fra:til>
  public static int parter(int[] a, int fra, int til, int skilleverdi)
  {
    fratilKontroll(a.length, fra, til);
    return parter0(a, fra, til - 1, skilleverdi);
  }

  public static int parter(int[] a, int skilleverdi)  // hele tabellen
  {
    return parter0(a, 0, a.length - 1, skilleverdi);
  }

Oppgave 2

132810169 15418141211 7536171 2019
v h
0 : Starttabellen med v og h på hver side

12810169 15418141211 75361713 2019
 v h 
1 : Tabellen etter første ombytting

1281069 15418141211 753161713 2019
 v h 
2 : Tabellen etter andre ombytting

1281069 3418141211 7515161713 2019
 v h 
3 : Tabellen etter tredje ombytting

1281069 345141211 71815161713 2019
 v h 
4 : Tabellen etter fjerde ombytting

1281069 34571211 141815161713 2019
 vh 
5 : Tabellen etter femte ombytting

Etter dette blir først setningen: while (v <= h && a[v] < skilleverdi) v++; utført og så setningen: while (v <= h && a[h] >= skilleverdi) h--; Det gir flg. tabell der v > h. Da stopper algoritmen, v er indeksen til den første av de som er større enn eller lik skilleverdien 11 og dermed h indeksen til den siste av de som er mindre enn skilleverdien 11. Legg merke til at innenfor de to delene er det ikke sortert.


1281069 34571211 141815161713 2019
 hv 
6 : Algoritmen er ferdig!

Hvis en bruker flg. versjon av parter0() (som blir kalt av parter) i Programkode 1.3.9 c), får vi utskrift som nedenfor. 

  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)
      {
        Tabell.bytt(a,v++,h--);          // bytter om a[v] og a[h]
        System.out.println(Arrays.toString(a) + " v = " + v + " h = " + h);
      }
      else  return v;                             // partisjoneringen er ferdig
    }
  }
[1, 2, 8, 10, 16, 9, 15, 4, 18, 14, 12, 11, 7, 5, 3, 6, 17, 13, 20, 19] v = 1 h = 16
[1, 2, 8, 10, 6, 9, 15, 4, 18, 14, 12, 11, 7, 5, 3, 16, 17, 13, 20, 19] v = 5 h = 14
[1, 2, 8, 10, 6, 9, 3, 4, 18, 14, 12, 11, 7, 5, 15, 16, 17, 13, 20, 19] v = 7 h = 13
[1, 2, 8, 10, 6, 9, 3, 4, 5, 14, 12, 11, 7, 18, 15, 16, 17, 13, 20, 19] v = 9 h = 12
[1, 2, 8, 10, 6, 9, 3, 4, 5, 7, 12, 11, 14, 18, 15, 16, 17, 13, 20, 19] v = 10 h = 11
10  [1, 2, 8, 10, 6, 9, 3, 4, 5, 7, 12, 11, 14, 18, 15, 16, 17, 13, 20, 19]

Oppgave 3

Med a = {7,10,3,4,1,6,8,2,9,5} og 7 som skilleverdi: 

[5, 10, 3, 4, 1, 6, 8, 2, 9, 7]
v = 1 h = 8
[5, 2, 3, 4, 1, 6, 8, 10, 9, 7]
v = 2 h = 6
[5, 2, 3, 4, 1, 6, 8, 10, 9, 7]
v = 6 h = 5

Med a = {7,10,3,4,1,6,8,2,9,5} og 5 som skilleverdi: 

[2, 10, 3, 4, 1, 6, 8, 7, 9, 5]
v = 1 h = 6
[2, 1, 3, 4, 10, 6, 8, 7, 9, 5]
v = 2 h = 3
[2, 1, 3, 4, 10, 6, 8, 7, 9, 5]
v = 4 h = 3

Oppgave 4

Med a = {11,2,17,1,9,8,12,14,15,3,19,18,7,10,16,20,13,4,6,5} og 6 som skilleverdi: 

[5, 2, 17, 1, 9, 8, 12, 14, 15, 3, 19, 18, 7, 10, 16, 20, 13, 4, 6, 11]
v = 1 h = 18
[5, 2, 4, 1, 9, 8, 12, 14, 15, 3, 19, 18, 7, 10, 16, 20, 13, 17, 6, 11]
v = 3 h = 16
[5, 2, 4, 1, 3, 8, 12, 14, 15, 9, 19, 18, 7, 10, 16, 20, 13, 17, 6, 11]
v = 5 h = 8
[5, 2, 4, 1, 3, 8, 12, 14, 15, 9, 19, 18, 7, 10, 16, 20, 13, 17, 6, 11]
v = 5 h = 4

Med a = {11,2,17,1,9,8,12,14,15,3,19,18,7,10,16,20,13,4,6,5} og 10 som skilleverdi: 

[5, 2, 17, 1, 9, 8, 12, 14, 15, 3, 19, 18, 7, 10, 16, 20, 13, 4, 6, 11]
v = 1 h = 18
[5, 2, 6, 1, 9, 8, 12, 14, 15, 3, 19, 18, 7, 10, 16, 20, 13, 4, 17, 11]
v = 3 h = 17
[5, 2, 6, 1, 9, 8, 4, 14, 15, 3, 19, 18, 7, 10, 16, 20, 13, 12, 17, 11]
v = 7 h = 16
[5, 2, 6, 1, 9, 8, 4, 7, 15, 3, 19, 18, 14, 10, 16, 20, 13, 12, 17, 11]
v = 8 h = 11
[5, 2, 6, 1, 9, 8, 4, 7, 3, 15, 19, 18, 14, 10, 16, 20, 13, 12, 17, 11]
v = 9 h = 8
[5, 2, 6, 1, 9, 8, 4, 7, 3, 15, 19, 18, 14, 10, 16, 20, 13, 12, 17, 11]
v = 9 h = 8

Med a = {11,2,17,1,9,8,12,14,15,3,19,18,7,10,16,20,13,4,6,5} og 15 som skilleverdi: 

[11, 2, 5, 1, 9, 8, 12, 14, 15, 3, 19, 18, 7, 10, 16, 20, 13, 4, 6, 17]
v = 3 h = 18
[11, 2, 5, 1, 9, 8, 12, 14, 6, 3, 19, 18, 7, 10, 16, 20, 13, 4, 15, 17]
v = 9 h = 17
[11, 2, 5, 1, 9, 8, 12, 14, 6, 3, 4, 18, 7, 10, 16, 20, 13, 19, 15, 17]
v = 11 h = 16
[11, 2, 5, 1, 9, 8, 12, 14, 6, 3, 4, 13, 7, 10, 16, 20, 18, 19, 15, 17]
v = 12 h = 15
[11, 2, 5, 1, 9, 8, 12, 14, 6, 3, 4, 13, 7, 10, 16, 20, 18, 19, 15, 17]
v = 14 h = 13

Oppgave 5

Alle verdier i tabellen blir sammenlignet med skilleverdi. Derfor må det være minst n sammenligninger der skilleverdi inngår. Metoden parter0() har to while-løkker. Den første gjør at indeks v flytter seg mot høyre og den andre at indeks h flytter seg mot venstre. Når de møtes, vil ett og samme tabellelement kunne bli sammenlignet med skilleverdi to ganger.

Ta først tallene 6, 5, 1, 2, 4 som eksempel og med 3 som skilleverdi. Først vil v stoppe på tallet 6. Deretter vil h stoppe på tallet 2. De byttes om. Så vil v stoppe på tallet 5 og h på tallet 1. De byttes om og vi er ferdige. Tilsammen 5 sammenligninger.

Ta så 1, 4, 6, 2, 5 som eksempel og fortsatt med 3 som skilleverdi. Indeks v vil stoppe på tallet 4 og så h på tallet 2. De byttes om. Så vil v stoppe på tallet 6. Men h vil fortsette videre mot venstre forbi tallet 6 og så stoppe. Det betyr at tallet 6 blir sammnelignet med skilleverdi to ganger. Dermed blir det nå 6 sammenligninger.

Hvis vi ser på alle de 120 forskjellige permutasjonene av 1, 2, 4, 5, 6 og hele tiden bruker 3 som skilleverdi, vil 48 av dem føre til 5 sammenligninger og resten (72) til 6 sammenligninger. Vi får flg. tabell hvis vi hele tiden ser på tallene 1, 2, 3, 4, 5, 6 og fortløpende tar ut ett av dem og bruker det som skilleverdi: 

  Tabell: 2, 3, 4, 5, 6  Skilleverdi: 1    5:   0    6: 120
  Tabell: 1, 3, 4, 5, 6  Skilleverdi: 2    5:  24    6:  96
  Tabell: 1, 2, 4, 5, 6  Skilleverdi: 3    5:  48    6:  72
  Tabell: 1, 2, 3, 5, 6  Skilleverdi: 4    5:  72    6:  48
  Tabell: 1, 2, 3, 4, 6  Skilleverdi: 5    5:  96    6:  24
  Tabell: 1, 2, 3, 4, 5  Skilleverdi: 6    5: 120    6:   0

Det betyr at halvparten gir 5 og halvparten 6 sammenligninger. Med andre ord 5,5 sammenligninger i gjennomsnitt.

Oppgave 6

Men n = 9, skal svaret bli (92 - 1)/(6·9) = 40/27. Hvis programmet kjøres med en tabell der 9 er siste tall, blir svaret 4838400. Men (40·9·9!)/27 = 4838400.

Men n = 8, skal svaret bli (82 - 1)/(6·8) = 21/16. Hvis programmet kjøres med en tabell der 9 er siste tall, blir svaret 423360. Men (21·8·8!)/16 = 423360.

Oppgave 7 

  int[] a = Tabell.randPerm(30);
  int pos = Tabell.parter(a, 11);
  Tabell.parter(a, pos, a.length, 21);
  System.out.println(Arrays.toString(a));

Oppgave 8 

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

    while (true)                                  // stopper når v >= h
    {
      if (v < h) Tabell.bytt(a,v++,h--);          // bytter om a[v] og a[h]
      else  return v;                             // partisjoneringen er ferdig
      while (a[v] < skilleverdi) v++;             // flytter v mot høyre
      while (a[h] >= skilleverdi) h--;            // flytter h mot venstre
    }
  }

Oppgave 9 

  public static int sParter(int[] a, int fra, int til, int indeks)
  {
    fratilKontroll(a.length, fra, til);

    if (fra == til) throw new
      IllegalArgumentException("Intervallet a[" + fra + ":" + til + "> er tomt!");

    if (indeks < fra || indeks >= til) throw new
      IllegalArgumentException("indeks(" + indeks + ") er utenfor intervallet!");

    return sParter0(a, fra, til - 1, indeks);
  }

  public static int sParter(int[] a, int indeks)
  {
    if (indeks < 0 || indeks >= a.length) throw new
      IllegalArgumentException("indeks(" + indeks + ") er utenfor tabellen!");

    return sParter0(a, 0, a.length - 1, indeks);
  }

Oppgave 12 

  int[] a = Tabell.randPerm(200000);
  int[] b = a.clone();
  int[] c = a.clone();

  long tid1 = System.currentTimeMillis();
  Tabell.innsettingssortering(a);
  tid1 = System.currentTimeMillis() - tid1;

  long tid2 = System.currentTimeMillis();
  Tabell.kvikksortering(b);
  tid2 = System.currentTimeMillis() - tid2;

  long tid3 = System.currentTimeMillis();
  Arrays.sort(c);
  tid3 = System.currentTimeMillis() - tid3;

  System.out.println("Innsettingssortering: " + tid1);
  System.out.println("Kvikksortering: " + tid2);
  System.out.println("Sort fra java.util: " + tid3);

Et førsøk på å optimalisere kvikksortering ved hjelp av innsettingssortering: 

  private static void kvikksortering0(int[] a, int v, int h)  // en privat metode
  {
    if (h - v < 20) return;   // stopper på 20, men andre verdier kan være bedre
    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
    innsettingssortering(a, fra, til);   // avslutter med innsettingssortering
  }

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

Oppgave 13 

  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 m = (v + h)/2;   // midten

    // sorterer a[v], a[m] og a[h];
    if (a[m] < a[v]) bytt(a, m, v);      // sammenligner/bytter
    if (a[h] < a[v]) bytt(a, h, v);      // sammenligner/bytter
    if (a[h] < a[m]) bytt(a, h, m);      // sammenligner/bytter

    int k = sParter0(a, v, h, m);        // bruker midtverdien
    kvikksortering0(a, v, k - 1);        // sorterer intervallet a[v:k-1]
    kvikksortering0(a, k + 1, h);        // sorterer intervallet a[k+1:h]
  }

Oppgave 14 

  int[] a = Tabell.randPerm(100);
  System.out.println(a[Tabell.kvikksøk(a, 10)]);  // 11
  System.out.println(Tabell.median(a));           // 50,5

Oppgave 15 

  public static int parter(int[] a, int v, int h, int skilleverdi)
  {
    while (v <= h) if (a[v] < skilleverdi) v++; else Tabell.bytt(a,v,h--);
    return v;
  }

Oppgave 16 

  public static int parter(int[] a, int v, int h, int skilleverdi)
  {
    int verdi = a[v];   // a[v] legges tilside
    int k = v;          // ledig posisjon

    for (v++; v <= h; v++)
    {
      if (a[v] < skilleverdi)
      {
        a[k] = a[v];    // a[v] flyttes til ledig plass
        a[v] = a[++k];  // nå er k ledig
      }
    }
    a[k] = verdi;

    return verdi < skilleverdi ? k + 1 : k;
  }

Oppgave 17

Metoden parter0() skal se slik ut: 

  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

      while (v <= h && comp(a[v], skilleverdi)) v++;   // h er stoppverdi for v
      while (v <= h && !comp(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
    }
  }

Et program: 

  public static void main(String... args)
  {
    Tabell.teller = 0;
    Tabell.kvikksortering(Tabell.randPerm(1000));
    System.out.println(Tabell.teller);  // Eksempel på utskrift: 11548

    int[] a = new int[1000];
    Arrays.setAll(a, i -> i + 1);  // 1, 2, 3, . . .

    Tabell.teller = 0;
    Tabell.kvikksortering(a);
    System.out.println(Tabell.teller);  // Utskrift: 8498
  }

Hvis en kjører dette programmet mange ganger, vil en se at resultatet i den første delen varierer, men ligger i området 10000 - 13000. Vi har at 1000 log2(1000) er ca. 10000 (eller mer nøyaktig 9965,8). Dette er ikke et bevis på at algoritmen er av orden n log2(n) i gjennomsnitt, men gir en god indikasjon på at det er tilfellet. I den andre delen blir det samme svar hver gang siden det er samme tabell.

Bytter vi skilleverdi fra midtverdien til verdien lengst til høyre i intervallet, blir det samme typen resultater i første del, men derimot hele 499500 sammenligninger i den andre delen. I dette tilfellet er algoritmen av kvadratisk orden.