Oppgave 2

Siden tabellen a er tom når programmet starter, vil antall >= a.length være sann og tabellen vil bli «utvidet». Ny størrelse blir 2*a.length, dvs. det dobbelte av hva det var. Men det dobbelte av 0 er fortsatt 0. Derfor blir ikke tabellen utvidet. Dette kan f.eks. løses ved at det står copyOf(a,2*a.length + 1) eller copyOf(a,Math.max(2*a.length, 1)).

Oppgave 3

Metodene copyOf() og copyOfRange() vil ofte bli brukt. Begge er laget for alle standardtypene og for en generisk type T. Bruker vi f.eks. typen int, har de flg. signaturer:

  public static int[] copyOf(int[] original, int newLength)

  public static int[] copyOfRange(int[] original, int from, int to) 

I copyOf() kan ikke newLength være negativ, men den kan være 0, mindre enn, lik eller større enn original.length. Hvis den er støøre enn original.length, blir tabellen «utvidet» med 0-er på de plassene som har kommet i tillegg.

I copyOfRange() må vi ha 0 <= from <= to og from <= original.length. Hvis to > original.length, blir det 0-er på de nye plassene. Eksempel:

  int[] b = {1,2,3,4,5,6};
  b = Arrays.copyOfRange(b, 3, 9);
  // b = {4,5,6,0,0,0}

Oppgave 4

System.arraycopy(a, k, a, k + 1, antall - k);

Oppgave 5

Innsettingssortering bruker i gjennomsnitt n(n + 3)/4 - H_n sammenligninger for å sortere n forskjellige tall. H_n er tilnærmet lik log(n) + 0,577 og H₁₀₀₀ tilnærmet lik 7,5. Dermed får vi 1000(1000 + 3)/4 - 7,5 = 250.742,5 sammenligninger i gjennomsnitt for n = 1000. For utvalgssortering blir det 1000(1000 - 1)/2 = 499.500 sammenligninger for n = 1000. Med andre ord halvparten så mange i innsettingssortering sammenlignet med utvalgssortering.

Oppgave 6

  int[] a = Tabell.randPerm(100000);
  int[] b = a.clone();
  long tid1 = System.currentTimeMillis();
  Tabell.utvalgssortering(a);
  tid1 = System.currentTimeMillis() - tid1;

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

  System.out.println("Utvalgssortering: " + tid1);
  System.out.println("Innsettingssortering: " + tid2);

Oppgave 7

  public static void innsettingssortering(int[] a, int fra, int til)
  {
    fratilKontroll(a.length,fra,til);  // se Programkode 1.2.3 a)

    for (int i = fra + 1; i < til; i++)  // a[fra] er første verdi
    {
      int temp = a[i];  // flytter a[i] til en hjelpevariabel

      // verdier flyttes inntil rett sortert plass i a[fra:i> er funnet
      int j = i-1; for (; j >= fra && temp < a[j]; j--) a[j+1] = a[j];

      a[j+1] = temp;  // verdien settes inn på rett sortert plass
    }
  }

Oppgave 8

Innsettingssortering er stabil fordi indre for-løkke har setningen temp < a[j]. Det betyr at letingen etter rett sortert plass stopper hvis temp er lik a[j] og temp blir satt inn i a[j+1], dvs. etter a[j].

Oppgave 9

  public static void innsettingssortering(int[] a)
  {
    for (int i = 1, j = 0; i < a.length; j = i++)
    {
      int verdi = a[i];

      if (verdi < a[0]) while (j >= 0) a[j+1] = a[j--];
      else while (verdi < a[j]) a[j+1] = a[j--];

      a[j+1] = verdi;
    }
  }

Oppgave 10

  public static void innsettingssortering(int[] a)
  {
    for (int i = 1; i < a.length; i++)
    {
      int temp = a[i];

      int p = Tabell.binærsøk(a, 0, i, temp);
      if (p < 0) p = -(p + 1);

      System.arraycopy(a, p, a, p + 1, i - p);

      a[p] = temp;
    }
  }

Oppgave 11

Avgjør først om tabellstørrelsen er et oddetall eller et partall. Videre avgjør vi for hver i hvilken av verdiene a[i] og a[i + 1] som er minst og størst. Den største settes inn på rett sortert plass i a[0:i-1]. Den minste av de to skal plasseres et sted til venstre for den andre. Det betyr at letingen etter rett sortert plass for den kan fortsette videre fra der vi stoppet. Deretter økes i med 2 slik at vi får to nye tabellverdier å behandle.

I vanlig innsettingssortering vil en ny verdi i gjennomsnitt havne på midten av den sorterte delen. Her skal vi sette inn to verdier i den sorterte delen. I gjennomsnitt vil da den minste havne i 1/3-dels avstand fra starten og den andre i 2/3-dels avstand. Detter fører til ca. n²/6 sammenligninger i gjennomsnitt. I den vanlige innsettingssorteringen var det ca. n²/4 stykker. Denne idéen er derfor ca. 30% mer effektiv. Hvis en gjør testkjøringer vil en se at en får forbedringer av en slik størrelsesorden.

  public static void innsettingssortering(int[] a)
  {
    int i = (a.length & 1) == 0 ? 0 : 1;

    for ( ; i < a.length; i += 2)
    {
      int verdi1 = a[i];
      int verdi2 = a[i + 1];

      if (verdi1 > verdi2)
      {
        verdi1 = verdi2;
        verdi2 = a[i];
      }

      // nå er verdi1 <= verdi2

      int j = i-1;

      // finner først rett plass for verdi2
      for (; j >= 0 && verdi2 < a[j]; j--) a[j+2] = a[j];
      a[j+2] = verdi2;

      // finner deretter rett plass for verdi1
      for (; j >= 0 && verdi1 < a[j]; j--) a[j+1] = a[j];
      a[j+1] = verdi1;
    }
  }

Oppgave 12

  public static void innsettingssortering(int[] a, int k)
  {
    if (k < 1 || k > a.length)
      throw new IllegalArgumentException("Ulovlig k-verdi!");

    Tabell.innsettingssortering(a,0,k);
    int[] b = new int[k];

    for (int i = k ; i < a.length; i += k)
    {
      if (i + k > a.length) k = a.length - i;
      System.arraycopy(a,i,b,0,k);
      Tabell.innsettingssortering(b,0,k);

      int j = k - 1;
      int m = i - 1;
      int p = i + k - 1;
      while (j >= 0 && m >= 0)
      {
        a[p--] = a[m] >= b[j] ? a[m--] : b[j--];
      }
      while (j >= 0) a[p--] = b[j--];
    }
  }

Oppgave 13

  public static void innsettingssortering3(int[] a)
  {
    if (a.length > 0)
      innsettingssortering(a,(int)Math.sqrt(a.length));
  }

Oppgave 14

I Programkode 1.3.8 c) vil alltid sammenligningen verdi < a[j] bli utført når while-løkken starter. Hvis j er 0, blir det en break og ingen flere sammenligninger. Hvis ikke, blir verdi < a[j] utført på nytt for å kunne avgjøre om while-løkken skal fortsette eller avbrytes. Osv.

  public static int antallInnsettingssortering(int[] a)
  {
    int antallSammenligninger = 0;

    for (int i = 1, j = 0; i < a.length; j = i++)  // starter med i = 1
    {
      int verdi = a[i];           // flytter a[i] til en hjelpevariabel

      antallSammenligninger++;    // alltid mint en sammligning i while-løkken

      while (verdi < a[j])        // sammenligner
      {
        a[j + 1] = a[j];          // forskyver mot høyre
        if (j-- == 0) break;      // venstre ende av tabellen

        antallSammenligninger++;  // en til hvis ikke break
      }

      a[j + 1] = verdi;        // verdien inn på rett sortert plass
    }

    return antallSammenligninger;
  }

  public static int antallFormel(int n)
  {
    // finner først n!
    int fakultet = 1;
    for (int i = 2; i <= n; i++) fakultet *= i;

    // finner H = n! ganget med Hn
    int H = 0;
    for (int i = 1; i <= n; i++) H += fakultet/i;

    return fakultet*n*(n+3)/4 - H;
  }

  public static void main(String... args)
  {
    for (int n = 1; n <= 10; n++)
    {
      int[] a = new int[n];
      for (int i = 0; i < n; i++) a[i] = i + 1;

      int antall = 0;

      do
      {
        int[] b = a.clone();
        antall += antallInnsettingssortering(b);
      }
      while (Tabell.nestePermutasjon(a));

      System.out.println(antall + " " + antallFormel(n));
    }

    // Utskrift:
    // 0 0
    // 2 2
    // 16 16
    // 118 118
    // 926 926
    // 7956 7956
    // 75132 75132
    // 777456 777456
    // 8771184 8771184
    // 107307360 107307360
  }

Oppgave 15

  for (int g = a.length/2; g > 0; g /= 2) Tabell.shell(a,g);

Oppgave 16

  int[] gap = {1,4,10,23,57,132,301,701,1577,3548,7984,17965,40423,90952,204642,
               460445,1036002,2331004,5244761,11800712}; 

Oppgave 17

  for (double g = a.length / 2.25; g > 5.0; g /= 2.25)
  {
    Tabell.shell(a,(int)Math.floor(g));
  }
  Tabell.shell(a,1);  // avslutter med 1 som gap-verdi