Oppgave 1

  public static void kvikksortering(int[] a, int v, int h)
  {
    int k = Tabell.sParter(a, v, h, (v + h)/2);
    if (v < k - 1) kvikksortering(a,v,k-1);
    if (k + 1 < h) kvikksortering(a,k+1,h);
  }

OBS: Metoden over fungerer kun hvis intervallet a[v : h] har minst én verdi, dvs. vi må ha v <= h. Det kan være gunstig å lage en metode som sorterer en hel tabell:

  public static void kvikksortering(int[] a)
  {
    if (a.length > 2) kvikksortering(a,0,a.length-1);
  }

Oppgave 2

  public static int kvikksortering(int[] a, int v, int h)
  {
    int k = Tabell.sParter(a, v, h, (v + h)/2);
    int venstre = 0, høyre = 0;
    if (v < k - 1) venstre = kvikksortering(a,v,k-1);
    if (k + 1 < h) høyre = kvikksortering(a,k+1,h);
    return Math.max(venstre,høyre) + 1;
  }

Eksempel på programkjøring:

  int[] a = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
  System.out.println("Antall lag: " + kvikksortering(a,0,a.length-1));
  Tabell.skrivln(a);

  int[] b = {1,4,6,8,10,12,14,15,2,9,5,11,3,13,7 };
  System.out.println("Antall lag: " + kvikksortering(b,0,b.length-1));
  Tabell.skrivln(b);

  // Utskrift:
  // Antall lag: 3
  // 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
  // Antall lag: 14
  // 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Oppgave 3

  public static void kvikksortering2(int[] a)
  {
    if (a.length > 2) kvikksortering2(a,0,a.length-1);
  }

  public static void kvikksortering3(int[] a)
  {
    if (a.length > 2) kvikksortering3(a,0,a.length-1);
  }

Eksempel på testprogram:

  int n = 10;
  int[] a = Tabell.randPerm(n);
  Tabell.skrivln(a);
  kvikksortering2(a);
  Tabell.skrivln(a);

Oppgave 4

  public static void kvikksortering(int[] a, int v, int h)
  {
    while (v < h)
    {
      int k = Tabell.sParter(a,v,h,(v + h)/2);
      if (k + 1 < h) kvikksortering(a,k+1,h);
      h = k - 1;
    }
  }

Oppgave 5

  public static int middel(int[] a, int i , int j, int k)
  {
    if (a[i] <= a[j])
    {
      if (a[j] <= a[k]) return j;
      if (a[k] <= a[i]) return i;
      return k;
    }
    if (a[i] <= a[k]) return i;
    if (a[k] <= a[j]) return j;
    return k;
  }

  public static void kvikksortering1(int[] a, int v, int h)
  {
    while (v < h)
    {
    	int m = middel(a,v,(v+h)/2,h);
      int k = Tabell.sParter(a,v,h,m);
      if (v < k - 1) kvikksortering1(a,v,k-1);
      v = k + 1;
    }
  }

Oppgave 6

  int[] a = Tabell.randPerm(10000000);
  long tid = System.currentTimeMillis();
  kvikksortering(a); // eller kvikksortering(a,0,a.length-1);
  tid = System.currentTimeMillis() - tid;
  System.out.println(tid);