Oppgave 1

Utskriften blir: 8 18 5 10 20 11 3 13 7 14

Oppgave 2

  Integer[] p = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,17,18,19,21,23,26,27,29};

  Tabell.innsettingssortering(p,
    Comparator.comparing(Integer::toBinaryString).reversed());

  for (int k : p) System.out.print(k + " ");
  // Utskrift: 29 14 7 27 26 13 12 6 3 23 11 21 10 5 19 18 9 17 8 4 2 1

Oppgave 3

  Integer[] p = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,17,18,19,21,23,26,27,29};

  Comparator<Integer> c = (x,y) ->
  {
    int a = x, b = y;                    // bruker int-format

    int m = Integer.highestOneBit(a);    // første 1-biten i a
    int n = Integer.highestOneBit(b);    // første 1-biten i b

    while (m > 0 && n > 0)
    {
      if ((m & a) == 0 && (n & b) != 0) return -1;      // 0 i a, 1 i b
      else if ((m & a) != 0 && (n & b) == 0) return 1;  // 1 i a, 0 i b

      m >>= 1; n >>= 1;       // flytter m og n
    }
    return m - n;    // n = 0 -> b forfeder til a, m = 0 -> omvendt
  };

  Tabell.innsettingssortering(p, c);
  for (int k : p) System.out.print(k + " ");
  // Utskrift: 1 2 4 8 17 9 18 19 5 10 21 11 23 3 6 12 13 26 27 7 14 29

Oppgave 4

Den eneste forskjellen fra løsningen på Oppgave 3 er at fortegnet snus i den siste return-setningen, dvs. return n - m; istedenfor return m - n;

  Integer[] p = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,17,18,19,21,23,26,27,29};

  Comparator<Integer> c = (x,y) ->
  {
    int a = x, b = y;                    // bruker int-format

    int m = Integer.highestOneBit(a);    // første 1-biten i a
    int n = Integer.highestOneBit(b);    // første 1-biten i b

    while (m > 0 && n > 0)
    {
      if ((m & a) == 0 && (n & b) != 0) return -1;      // 0 i a, 1 i b
      else if ((m & a) != 0 && (n & b) == 0) return 1;  // 1 i a, 0 i b

      m >>= 1; n >>= 1;       // flytter m og n
    }
    return n - m;    // n = 0 -> b forfeder til a, m = 0 -> omvendt
  };

  Tabell.innsettingssortering(p, c);
  for (int k : p) System.out.print(k + " ");
  // Utskrift: 17 8 18 19 9 4 21 10 23 11 5 2 12 26 27 13 6 29 14 7 3 1

Oppgave 5

  Integer[] p = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,17,18,19,21,23,26,27,29};

  Comparator<Integer> c = (a, b) ->
  {
    String s = Integer.toBinaryString(a);
    String t = Integer.toBinaryString(b);

    int m = Math.min(s.length(), t.length());

    for (int i = 0; i < m; i++)
    {
      int k = s.charAt(i) - t.charAt(i);
      if (k != 0) return k;
    }
    return t.length() - s.length();
  };

  Tabell.innsettingssortering(p, c);
  for (int k : p) System.out.print(k + " ");
  // Utskrift: 17 8 18 19 9 4 21 10 23 11 5 2 12 26 27 13 6 29 14 7 3 1

Oppgave 6

  Integer[] p = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,17,18,19,21,23,26,27,29};

  Comparator<Integer> c = (x,y) ->
  {
    int a = x, b = y;                    // bruker int-format

    int m = Integer.highestOneBit(a);    // første 1-biten i a
    int n = Integer.highestOneBit(b);    // første 1-biten i b

    while (m > 0 && n > 0)
    {
      if ((m & a) == 0 && (n & b) != 0) return -1;      // 0 i a, 1 i b
      else if ((m & a) != 0 && (n & b) == 0) return 1;  // 1 i a, 0 i b

      m >>= 1; n >>= 1;       // flytter m og n
    }

    return m > 0 ? ((m & a) == 0 ? -1 : 1) : ((n & b) == 0 ? 1 : -1);
  };

  Tabell.innsettingssortering(p, c);
  for (int k : p) System.out.print(k + " ");
  // Utskrift: 8 17 4 18 9 19 2 10 21 5 11 23 1 12 6 26 13 27 3 14 29 7