Array #

Einführung #

Ein Array ist eine Datenstruktur, dessen Inhalt nebeneinander im RAM liegt.

Verwendung #

//Initialisierung mit Platz für 100 int Elemente
int[] numbers = new int[100];

// Erste Zahl in num speichern
int num = numbers[0];

//Eine Zahl an zweiter Stelle speichern
numbers[1] = 4711;

Nützliche Funktionen #

equals(A, B). A und B sind arrays und nur true, wenn sie die gleiche Anzahl Elemente und dieselben Elemente enthalten.
fill(A, x). Jede Zelle des Array mit x füllen.
copyOf(A, n). Kopiert die ersten n Element von A in einen neuen Array
copyOfRange(A, s, t). Kopiert t - s Elemente von s bis t - 1 in einen neuen Array.
toString(A). Gibt “[” + element2.toString() “, " + element2.toString() + “]” zurück.
sort(A). Sortiert den Array
binarySearch(A, x). Sucht ein Element im sortierten Array.

Sortierungsalgorithmen #

Insertion-Sort #

//Input ist unsortiertes Array
//Output ist ein sortiertes Array
public static void insertionSort(char[] data) {
  int size = data.length;
  //Starte beim zweiten Element und iteriere bis zum letzten Element
  for (int index = 1; index < size; index++) {
    char currentElement = data[index];
    int indexEmptySpot = index;

    //Überprüfe das aktuelle Element mit den jeweiligen Vorgängern.
    //Wenn Grösser dann darf der Vorgänger den Platz des aktuellen Elements übernehmen
    //Anschliessend Loopen bis der korrekte Platz gefunden wurde
    while (indexEmptySpot > 0 && data[indexEmptySpot-1] > currentElement) {
      data[indexEmptySpot] = data[indexEmptySpot - 1];
      indexEmptySpot--;
    }
    //Korrekte Platz ist jetzt leer und das Element kann gesetzt werden.
    data[indexEmptySpot] = currentElement;
  }
}

Merge-Sort #

In einer Geschichte kann der Merge-Sort gut erklärt werden. Da man keine Lust hat, das ganze Array auf einmal zu sortieren, wird zuerst eine Hälfte angeschaut. Das ist die Divide Phase. Beim Sortieren (conquer Phase) wird nun gleich bemerkt, dass diese Hälfe immer noch zu gross ist und halbiert nochmals. Das Verfahren wird durchgeführt, bis nur noch ein Element übrig ist. Das ist dann per Definition sortiert. Würde dieses Verfahren bildlich aufgezeichnet, ergäbe das Halbieren jeweils ein Knoten in einem Baum. Die höchste Ebene ist das komplette unsortierte Array und der unterste Knoten auf der tiefsten Ebene wäre das Array mit einem Element.

Nun kommt die Merge-Phase, die diese Hälften zusammenführt. Da beide Hälften auf der untersten Ebene sortiert sind, wird in diesem Verfahren immer das kleinere Element der beiden Hälften ausgewählt (bis es keine Elemente mehr hat). Dann wird zur höheren Ebene gewechselt und es wird das gleiche Verfahren nochmals ausgeführt. Das Verfahren wird bis zur obersten Ebene ausgeführt. Am Schluss der Merge-Phase ist das Array sortiert.

In Code sieht das wie folgt aus:

public static <T> void mergeSort(T[] S, Comparator<T> comp) {
  int n = S.length;
  if (n < 2) return; //bereits sortiert
  //divide
  int mid = n / 2;
  T[] S1 = Arrays.copyOfRange(S, 0, mid);
  T[] S2 = Arrays.copyOfRange(S, mid, n);

  //conquer
  mergeSort(S1, comp);
  mergeSort(S2, comp);

  //merge
  merge(S1, S2, S, comp);
}

public static <T> void merge(T[] S1, T[] S2, T[] S, Comparator<T> comp) {
  int i = 0, j = 0;
  while (i + j < S.length) {
    if (j == S2.length || (i < S1.length && comp.compare(S1[i], S2[j]) < 0)) {
      S[i + j] = S1[i++];
    } else {
      S[i + j] == S2[j++]
    }
  }
}

Die Merge Funktion lässt sich noch stark vereinfachen. Die Index Addition in den Array ist schwer verständlich. Mit geeigneten Datenstrukturen ist es aber einfacher.

Das sieht dann so aus:

public static void merge(Queue<T> S1, Queue<T> S2, Queue<T> S, Comperator<S comp>) {
  //Merge solange es in beiden noch Elemente hat
  while(!S1.isEmpty() && !S2.isEmpty()) {
    if(comp.compare(S1.first(), S2.first()) < 0) {
      S.enqueue(S1.dequeue());
    } else {
      S.enqueue(S2.dequeue());
    }
  }

  //Da jetzt mind. ein Array leer ist, ist die andere Hälfte sortiert
  //Dieser Fall tritt ein, wenn beide Hälfen nicht die gleiche Anzahl haben
  while(!S1.isEmpty()) {
    S.enqueue(S1.dequeue());
  }
  while(!S2.isEmpty()) {
    S.enqueue(S2.dequeue());
  }
}