Such-/Sortieralgorithmen

Suchalgorithmen

Gegeben ist eine sortierte Liste List<Integer>, gefüllt mit Werten. Wie können wir herausfinden, ob und an welchem Index eine Zahl n vorkommt?

Lineare Suche

Der einfachste Ansatz ist das iterative Durchsuchen der Liste. Wir gehen jedes Element der Liste durch und gucken, ob der Wert in der Liste der selber ist, wie unser n.

int getIndexOf(List<Integer> list, int n) {
  for (int i = 0; i < list.size(); i++) {
    final int val = list.get(i);
    if (val == n) {
      // Gefunden bei index i!
      return i;
    }
  }
  // n kommt in der Liste nicht vor.
  return -1;
}

Dieser Ansatz ist einfach, allerdings nicht sehr effizient, weil diese Methode, je größer unsere Liste ist, immer länger brauchen wird. Um genau zu sein, erhöht jedes weitere Element in der Liste die Laufzeit linear. Daher: $O(n)$.

Binäre Suche

Weil unsere Liste sortiert ist, wissen wir, dass bei einem beliebigen Element, welches nicht außen liegt, links von diesem, kleinere, und rechts von diesem, größere Werte liegen werden.

Nun können wir als einfach unser n mit dem mittleren Element vergleichen, um eine kleinere Unterliste gegeben zu bekommen, bei welcher wir denselben Schritt rekursiv wiederholen können, bis der Index unseres Elementes gefunden ist.

int getIndexOf(List<Integer> list, int n) {
  final int size = list.size();
  if (size == 1) {
    return list.getFirst() == n ? 0 : 1;
  }

  if (size > 1) {
    final int middleIndex = size / 2;
    final int middleValue = list.get(middleIndex);

    if (n < middleValue) {
      return getIndexOf(list.subList(0, middleIndex), n);
    } else if (n == middleValue) {
      return middleIndex;
    } else {
      final int result = getIndexOf(list.subList(middleIndex, size), n);
      return result == -1 ? -1 : result + middleIndex;
    }
  }

  // empty list
  return -1;
}

Sortieralgorithmen

Beispiel: bubblesort. Bubblesort iteriert jeweils die ganze Liste und tauscht zwei benachbarte Elemente aus. Falls diese nicht in der richtigen Reihenfolge auftreten. Dies wird so lange wiederholt, bis die ganze Liste sortiert ist.

Zeitkomplexität (bereits sortiert): $O(n)$
Zeitkomplexität (worst-case): $O(n^2)$