Deutsch

Sortieralgorithmen

MittelschuleInformatikDeterministische Spuren vergleichender Sortieralgorithmen; Schreibvorgänge im Hauptarray werden separat gezählt

Bereit zum Sortieren

11091325374451061278829110611

Orange markiert die an diesem Vorgang beteiligten Positionen. Die Indizierung beginnt bei null. Verwenden Sie „Zurück“ und „Schritt“, um die einzelnen Vorgänge zu untersuchen.

Über dieses Experiment

Beobachte, wie Bubble Sort, Insertion Sort und Merge Sort dieselbe Eingabe in aufsteigende Reihenfolge bringen. Halte bei einem Vergleich an, gehe jeden Schreibzugriff einzeln durch oder gehe den vollständigen Ablauf rückwärts durch. Separate Zählungen für Wertvergleiche und Schreibzugriffe auf das Hauptarray helfen dabei, den algorithmischen Aufwand von der Animationsdauer zu unterscheiden.

Lernziele

  • Vergleiche und Schreibzugriffe bei drei vergleichsbasierten Sortieralgorithmen nachverfolgen
  • Die Leistung bei zufälligen, sortierten und umgekehrt sortierten Eingaben vergleichen
  • Quadratisches Wachstum im ungünstigsten Fall von Wachstum gemäß n log n unterscheiden

Anleitung

  1. 1Behalte die zufällige Eingabe und die Array-Länge unverändert bei. Führe Bubble Sort vollständig aus und notiere die Anzahl der Vergleiche und Schreibzugriffe.
  2. 2Starte mit derselben Eingabe neu, zunächst mit Insertion Sort und dann mit Merge Sort. Vergleiche die Endwerte.
  3. 3Probiere eine sortierte Eingabe aus und untersuche den vorzeitigen Abbruch von Bubble Sort sowie die wenigen Vergleiche bei Insertion Sort.
  4. 4Verwenden Sie „Zurück“ und den Ablaufregler, um einen Merge-Vorgang zu untersuchen. Temporäre Puffer können Werte enthalten, die an ihren ursprünglichen Positionen im Hauptarray nicht mehr sichtbar sind.

Das Modell

Vergleiche von Werten bei Bubble-Sort im Worst Case
Zeitwachstum von Insertion-Sort und Merge-Sort im Worst Case
Ein Tausch wird als zwei Schreibvorgänge ins Hauptarray gezählt

Annahmen

  • Die Eingaben enthalten eindeutige Ganzzahlen von 1 bis n. Beim Mischen wird ein fester Seed verwendet, damit jeder Algorithmus identische Daten erhält.
  • Ein Vergleich ist ein Test zwischen Datenwerten, kein Test eines Index oder einer Schleifenbedingung. Ein Schreibvorgang ist eine Zuweisung ins Hauptarray, einschließlich eines unveränderten Einfügeschlüssels.
  • Kopien in temporäre Puffer bei Merge-Sort werden bei der Anzahl der Schreibvorgänge nicht berücksichtigt. Der zusätzliche Speicherbedarf ist in den angezeigten Operationssummen nicht enthalten.
  • Die Wiedergabegeschwindigkeit wurde zu Lehrzwecken gewählt und ist kein Benchmark für die Leistung in Echtzeit.

Im Unterricht ausprobieren

  1. Q1Warum benötigt Bubble-Sort in dieser Implementierung bei bereits sortierter Eingabe nur n − 1 Vergleiche?
  2. Q2Welcher Algorithmus führt bei umgekehrter Eingabereihenfolge und gleicher Arraylänge weniger Vergleiche durch?
  3. Q3Warum ist die Anzahl der Animationsframes kein zuverlässiges Maß für die Geschwindigkeit eines Algorithmus?

Häufig gestellte Fragen

Warum erscheinen Werte beim Einfügen oder Sortieren durch Mischen kurzzeitig doppelt?

Ein Wert kann in einem temporären Schlüssel oder Merge-Puffer zwischengespeichert werden, während das Hauptarray überschrieben wird. Die Visualisierung zeigt bei jedem Schreibvorgang den Inhalt des Hauptarrays; die Eindeutigkeit ist wiederhergestellt, sobald der Vorgang abgeschlossen ist.

Verwendet Mergesort immer weniger Schreibvorgänge?

Nein. Mergesort weist ein effizientes Wachstum der Vergleichsanzahl auf, schreibt zusammengeführte Ergebnisse aber wiederholt zurück. Die Anzahl der Operationen hängt von der Eingabe und davon ab, welche Zuweisungen genau gezählt werden.