📄
Papierspeicher-Modell
Decke bis zu 2 Karten auf · vergleiche Werte · tausche oder überspringe · sortiere aufsteigend
Simulation
Sortieralgorithmen
Speichermodell
🎯 Worum geht's? Klasse 11 · 1 Unterrichtsstunde
Nach dieser Seite kannst du …
- Werte nur durch Aufdecken, Vergleichen und Tauschen sortieren – wie ein Computer
- deine Vorgehensweise als Algorithmus beschreiben
- die Zahl der Vergleiche und Vertauschungen verschiedener Strategien vergleichen
Vorwissen: keines
🗂 Anzahl Speicherstellen
📦 Datentyp
🔀 Vorsortierung
⇄ Tauschfeld
Karte A
—
⇄
Karte B
—
0
Vergleiche
Paare ausgewählt
0
Tauschvorgänge
Werte vertauscht
0
Elementaroperationen
Lesen + Vergleich + Schreiben
📋 Protokoll
📚 Hintergrundwissen
🗃️ Was ist das Papierspeicher-Modell?
Das Papierspeicher-Modell macht das Verhalten eines Computerspeichers beim Sortieren greifbar. Jede Karte steht für einen Speicherplatz im RAM.
Ein Computerspeicher besteht aus nummerierten
Speicherplätzen. Der Computer kann immer nur
einen Wert gleichzeitig lesen — genau wie man bei diesem
Modell immer nur eine Karte aufdeckt.
🔑 Kernregeln
1
Nur 2 Karten gleichzeitig sichtbar: Der Prozessor vergleicht
immer genau 2 Werte.
2
Aufdecken = Leseoperation: Jedes Aufdecken kostet eine
Elementaroperation.
3
Vergleich: Beide Karten sichtbar → entscheiden: tauschen
oder nicht?
4
Tausch = 3 Schreiboperationen:
temp = A, A = B,
B = temp.
5
Zustand speichern: Mit 💾 wird der aktuelle Spielstand
im Browser gespeichert.
💾 LocalStorage – Was wird gespeichert?
| Gespeicherte Daten | Bedeutung |
|---|---|
| values / types | Aktuelle Kartenwerte und Datentypen |
| numericVals | Numerische Vergleichswerte |
| flipped | Welche Karten aufgedeckt sind |
| SLOTS / currentType | Anzahl Karten und Datentyp |
| currentPreset | Gewählte Vorsortierung |
| openMode | Offener oder versteckter Modus |
| statCompare/Swap/Ops | Aktuelle Statistikwerte |
| theme | Hell / Dunkel Modus |
| infoPanelOpen | Ob das Info-Panel geöffnet ist |
| timestamp | Zeitstempel des letzten Speicherns |
Der Zustand wird
automatisch beim Verlassen der Seite gespeichert und beim
nächsten Besuch wiederhergestellt. Mit 💾 kann jederzeit manuell
gespeichert werden.
LocalStorage ist browserspezifisch. Daten gehen verloren,
wenn der Browser-Cache geleert wird. Für dauerhafte Sicherung: Screenshot
oder Export.
👁 Offener vs. versteckter Modus
| Merkmal | 🔒 Versteckt | 👁 Offen |
|---|---|---|
| Karten | Umgedreht, einzeln aufdecken | Alle sichtbar |
| Leseops. | +1 pro aufgedeckter Karte | 0 (bereits sichtbar) |
| Tausch | Karten fliegen und tauschen | Karten fliegen und tauschen |
🫧 Bubble Sort
Vergleicht immer benachbarte Paare. Große Werte wandern nach rechts.
1
Wähle SP 0 und SP 1.
Ist SP 0 > SP 1? → Tauschen.
2
Weiter mit SP 1 und SP 2 usw. bis zum Ende.
3
Nach einem Durchlauf steht der größte Wert am Ende.
4
Wiederhole ohne den letzten Platz.
Nach jedem Durchlauf ist mindestens ein weiterer Wert
an seiner endgültigen Position.
🃏 Selection Sort
Sucht in jedem Durchlauf das Minimum des unsortierten Bereichs.
1
Merke SP 0 als aktuelles Minimum.
2
Vergleiche mit SP 1, SP 2, … bis zum Ende.
3
Tausche Minimum mit SP 0. Nächste Runde ab SP 1.
Nur n−1 Tausche maximal —
immer gleich viele Vergleiche.
🎯 Insertion Sort
Fügt jeden neuen Wert an der richtigen Stelle in den sortierten Teil ein.
1
SP 0 gilt als sortiert. Wähle SP 1 als
key.2
Vergleiche
key rückwärts.
Größer? → Nach rechts schieben.3
Weiter mit SP 2, SP 3, …
Best Case bei fast sortierten Daten:
nur n−1 Vergleiche, keine Tausche.
⚙️ Elementaroperationen
Lesen
READ(SP i)
Karte aufdecken
Vergleich
CMP(A, B)
Werte prüfen
Schreiben
WRITE(SP i)
Wert ablegen
Kein Tausch
+0 Ops
kein Schreiben
🔁 Tausch-Mechanismus
3 Schreiboperationen pro Tausch:
Gesamt: +3 Elementaroperationen
temp = A → 1 Schreib-OpA = B → 1 Schreib-OpB = temp → 1 Schreib-OpGesamt: +3 Elementaroperationen
Ohne Hilfsvariable würde der ursprüngliche Wert
verloren gehen.
temp = Zwischenspeicher.📐 Ops nach Modus
| Aktion | 🔒 Versteckt | 👁 Offen |
|---|---|---|
| Karte auswählen | +1 (READ) | +0 |
| Vergleich | +1 (CMP) | +1 (CMP) |
| ✔ Tauschen | +3 | +3 |
| ✘ Nicht tauschen | +0 | +0 |
📈 Zeitkomplexität
O(n²): Verdoppelt man n, vervierfacht
sich der Aufwand. Bei n=10: ~100 Ops, bei n=20: ~400 Ops.
🔢 Vergleich der Verfahren
| Verfahren | Best | Avg. | Worst | Stabil |
|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | ✅ |
| Selection Sort | O(n²) | O(n²) | O(n²) | ❌ |
| Insertion Sort | O(n) | O(n²) | O(n²) | ✅ |
📊 Worst-Case-Vergleiche
| n | Vergleiche n·(n-1)/2 | Max. Tausche |
|---|---|---|
| 5 | 10 | 10 |
| 10 | 45 | 45 |
| 15 | 105 | 105 |
| 20 | 190 | 190 |
Alle drei elementaren Sortierverfahren haben im
Worst Case O(n²).