Oppgave 1

3	4	5	6	7	19	21	23	10	14	15	11	16	17	8
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
Tabellen etter 5 iterasjoner

3	4	5	6	7	8	10	23	21	14	15	11	16	17	19
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
Tabellen etter 7 iterasjoner

Oppgave 2

15	8	17	16	5	6	7	4	10	14	3	11	19	21	23
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
Figur 1.3.4 a) : Gitt en (usortert) tabell.

Oppgave 4

  int[] a = Tabell.randPerm(100000);
  long tid = System.currentTimeMillis();
  Tabell.utvalgssortering(a);
  tid = System.currentTimeMillis() - tid;
  System.out.println(tid);

Oppgave 5

  public static void utvalgssortering(int[] a)
  {
    for (int i = 0; i < a.length - 1; i++)
    {
      int m = i;             // indeks til den foreløpig minste
      int  minverdi = a[i];  // verdien til den foreløpig minste

      for (int j = i + 1; j < a.length; j++)
      {
        if (a[j] < minverdi)
        {
          minverdi = a[j];  // ny minste verdi
          m = j;            // indeksen til ny minste verdi
        }
      }
      // bytter om a[i] og a[m]
      int temp = a[i];
      a[i] = a[m];
      a[m] = temp;
    }
  }

Oppgave 6

  public static void utvalgssortering(int[] a)
  {
    for (int i = 0; i < a.length - 1; i++)
    {
      int m = i;             // indeks til den foreløpig minste
      int  minverdi = a[i];  // verdien til den foreløpig minste

      for (int j = i + 1; j < a.length; j++)
      {
        if (a[j] < minverdi)
        {
          minverdi = a[j];  // ny minste verdi
          m = j;            // indeksen til ny minste verdi
        }
      }
      // bytter om a[i] og a[m]
      a[m] = a[i];
      a[i] = minverdi;
    }
  }

I a[m] = a[i]; a[i] = minverdi; inngår det to tilordninger og tre tabellaksesser, mens det i int temp = a[i]; a[i] = a[m]; a[m] = temp; inngår tre tilordninger og fire tabellaksesser. Vi sparer en tilordning og to tabellaksesser. Men dette vil ikke ha noen målbar effekt på algoritmens effektivitet. Innsparingen skjer i den ytre løkken og den går bare n − 1 ganger. Det er innsparinger i den indre løkken som vil kunne få effekt.

Oppgave 7

Med hjelpemetoder:

  public static void utvalgssortering(int[] a)
  {
    for (int i = a.length; i > 1; i--)
    {
      bytt(a, maks(a, 0, i), i-1);
    }
  }

Uten hjelpemetoder:

  public static void utvalgssortering(int[] a)
  {
    for (int i = a.length - 1; i > 0; i--)
    {
      int m = 0;              // indeks til den foreløpig største
      int  maksverdi = a[0];  // verdien til den foreløpig minste

      for (int j = 1; j < i; j++)
      {
        if (a[j] > maksverdi)
        {
          maksverdi = a[j];  // ny minste verdi
          m = j;            // indeksen til ny minste verdi
        }
      }
      // bytter om a[i] og a[m]
      a[m] = a[i];
      a[i] = maksverdi;
    }
  }

Oppgave 8

Hvis vi tar utgangspunkt i Programkode 1.3.4 a), blir det sortert avtagende hvis vi bytter ut min() med maks():

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

Vi kan også ta utgangspunkt i versjonen fra Oppgave 6. Bruker vi variabelnavnet maksverdi istedenfor minverdi og snur ulikhet til a[j] > maksverdi, så blir det også sortert avtagende:

  public static void utvalgssortering(int[] a)
  {
    for (int i = 0; i < a.length - 1; i++)
    {
      int m = i;             // indeks til den foreløpig minste
      int  maksverdi = a[i];  // verdien til den foreløpig minste

      for (int j = i + 1; j < a.length; j++)
      {
        if (a[j] > maksverdi)
        {
          maksverdi = a[j];  // ny minste verdi
          m = j;            // indeksen til ny minste verdi
        }
      }
      // bytter om a[i] og a[m]
      a[m] = a[i];
      a[i] = maksverdi;
    }
  } 

Oppgave 9

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

    for (int i = fra; i < til - 1; i++)
    {
      bytt(a, i, min(a, i, til));  // to hjelpemetoder
    }
  }

Oppgave 10

2	8	2	6	5	1	7	3	9	4
0	1	2	3	4	5	6	7	8	9
Tall fra 1 til 9 inklusive to 2-ere

I tabellen er det to 2-ere. Den første av dem har rød farge. Den minste verdien 1 ligger i posisjon 5. Den byttes med verdien i posisjon 0:

1	8	2	6	5	2	7	3	9	4
0	1	2	3	4	5	6	7	8	9
Den minste verdien er på rett plass

Neste skritt er å finne den minste blant de usorterte (den hvite delen). Algoritmen er laget slik at hvis det er flere, er det den første av dem vi velger. Med andre ord stopper vi på verdien 2 i posisjon 2. Den byttes med verdien i posisjon 1:

1	2	8	6	5	2	7	3	9	4
0	1	2	3	4	5	6	7	8	9
To av de minste er på rett plass

Så velger vi igjen den minste. Det er verdien 2 i posisjon 5. Etter byttingen blir tabellen slik:

1	2	2	6	5	8	7	3	9	4
0	1	2	3	4	5	6	7	8	9
Tre av de minste er på rett plass

Vi ser at de to 2-erne har byttet innbyrdes rekkefølge. Utvalgssortering er ikke stabil.

Oppgave 11

La m være posisjonen til den minste i intervallet. Hvis m = i, er ombyttingen unødvendig:

  public static void utvalgssortering(int[] a)
  {
    for (int i = 0; i < a.length - 1; i++)
    {
      int m = min(a, i, a.length);  // posisjonen til den minste
      if (m != i) bytt(a, i, m);
    }
  }

Hvis vi gjør noen små endringer i koden over, vil vi få vite antallet ganger m = i:

 public static int utvalgssortering(int[] a)
  {
    int antall = 0;
    for (int i = 0; i < a.length - 1; i++)
    {
      int m = min(a, i, a.length);  // posisjonen til den minste
      if (m != i) bytt(a, i, m);
      else antall++;
    }
    return antall;
  }

Flg. programbit (med den versjonen av utvalgssortering som står rett over) gir antallet for noen tilfeldige permutasjoner av tallene fra 1 til 10:

  for (int i = 0; i < 10; i++)
  {
    int[] a = Tabell.randPerm(10);
    System.out.print(Tabell.utvalgssortering(a) + " ");
  }

Ved en kjøring av programbiten ble resultatet slik: 4 4 1 0 3 1 2 0 0 2

Men resultatet blir forskjellig hver gang. Men hva blir gjennomsnittsverdien? Vi har 10! forskjellige permutasjoner. Det er 9! stykker som har tallet 1 først. Det betyr at i første iterasjon er sannsynligheten 1/10 for at m og i er like. I neste iterasjon vil sannsynligheten være 1/9 for at de er like. Osv. til intervallet inneholder kun to verdier. Da vil sannsynligheten være 1/2. Sammenlagt blir det 1/10 + 1/9 + · · · + 1/2. Dette er lik H10 − 1 = 4861/2520 = 1.93. Med andre ord er gjennomsnittsverdien nær 2.

Hvis tabellen inneholder tallene fra 1 til n, vil gjennomsnittet bli Hn − 1. I Avsnitt 1.1.6 fant vi at for store n er Hn − 1 ≈ log(n) – 0,423. Hvis n f.eks. er 100 000, vil det bli 11,1. Dette betyr at det overhodet ikke lønner seg å ha testen if (m != i). Den utføres hver gang (n − 1 ganger), men det er svært sjelden at m og i er like.