Oppgave 1

Tester metoden på samtlige 3628800 permutasjoner av tallene fra 1 til 10:

  int[] a = {1,2,3,4,5,6,7,8,9,10};
  do
  {
    int[] b = a.clone();
    Tabell.boblesortering(b);
    if (!Tabell.erSortert(b))  // Programkode 1.3.2 c)
    {
      System.out.println(Arrays.toString(b) + " er usortert!");
      break;
    }
  }
  while (Tabell.nestePermutasjon(a));  // Programkode 1.3.1 b)

Oppgave 2

Her er svaret helt avhengig av hvilken prosessor, operativsystem og versjon av Java en bruker. Da undertegnede sist testet koden under (hele tiden med Intel Core i7-7700, 3.60 GHz og Windows 10) var versjon 2 (den med færre gjennomganger) en del bedre enn versjon 1 med Java 8, men de var helt like med Java 10.

Java 8:  1. versjon ca.7 sek  2. versjon ca. 5 sek
Java 10: ca. 5 sek på begge

  int[] a = Tabell.randPerm(50000);        // en tilfeldig permutasjon
  int[] b = a.clone();                     // en kopi
  long tid = System.currentTimeMillis();   // leser av klokken
  Tabell.boblesortering1(a);               // sorterer a
  tid = System.currentTimeMillis() - tid;  // tidsforbruket
  System.out.println(tid);                 // skriver ut

  tid = System.currentTimeMillis();        // leser av klokken
  Tabell.boblesortering2(b);               // sorterer b
  tid = System.currentTimeMillis() - tid;  // tidsforbruket
  System.out.println(tid);                 // skriver ut    

Oppgave 3

  public static void boblesortering(int[] a)
  {
    for (int n = 0; n < a.length - 1; )
    {
      int byttindeks = a.length - 1;
      for (int i = a.length - 2; i >= n; i--)
      {
        if (a[i] > a[i + 1])
        {
          bytt(a, i, i + 1);
          byttindeks = i;
        }
      }
      n = byttindeks;
    }
  }

Oppgave 4

Oppgave 5

  public static double H(int n)
  {
    if (n < 1) throw new IllegalArgumentException("Må ha n >= 1");

    double sum = 1.0;
    for (int k = 2; k <= n; k++) sum += 1.0/k;
    return sum;
  }

  public static void main(String... args)
  {
    int n = 10;
    double Hn = H(n);

    double sum = 0.0;
    for (int k = 1; k < n; k++)
    {
      double ombyttinger = (n + k*(H(k) - Hn - 1));
      sum += ombyttinger;
      System.out.printf("%5.2f\n",ombyttinger);
    }
    System.out.println(sum + " " + n*(n-1)/4.0);
  }

Utskrift:
 7.07
 5.14
 3.71
 2.62
 1.77
 1.13
 0.65
 0.31
 0.10
22.5 22.5