Algorithmen lernen

Kapitel 5. Sortieren ohne Hut

Diese Arbeit wurde mithilfe von KI übersetzt. Wir freuen uns über dein Feedback und deine Kommentare: [e-mail]

In diesem Kapitel lernst du:

• Wie vergleichsbasierte Sortieralgorithmen benötigen zwei grundlegende Operationen:

  • less(i,j) bestimmt, ob A[i] < A[j].

  • swap(i,j) tauscht den Inhalt von A[i] undA[j] aus.

• Wie du beim Sortieren eine Komparatorfunktion bereitstellst; zum Beispiel kannst du Ganzzahlen oder String-Werte in absteigender Reihenfolge sortieren. Die Komparatorfunktion kann auch komplexe Datenstrukturen ohne Standardreihenfolge sortieren; es ist zum Beispiel nicht klar, wie man eine Sammlung von zweidimensionalen (x, y) Punkten sortiert.

• Wie man ineffiziente O(^N2)-Sortieralgorithmen wie Insertion Sort und Selection Sort an der Struktur ihres Codes erkennt.

• Rekursion, bei der eine Funktion sich selbst aufrufen kann. Dieses grundlegende Konzept der Informatik bildet die Grundlage für eine Strategie des Teilens und Beherrschens beim Lösen von Problemen.

• Wie Merge Sort und Quicksort ein Array mit N Werten in O(N logN) mit Divide and Conquer sortieren können. Wie Heap Sort auch O(N log N) garantiert.

• Tim Sort kombiniert Insertion Sort und Funktionen von Merge Sort, um Pythons Standard-Sortieralgorithmus in garantiertem O(N log N) zu implementieren.

In diesem Kapitel stelle ich Algorithmen vor, die die N Werte in einem Array so anordnen, dass sie in aufsteigender Reihenfolge stehen. Eine Sammlung ...