faecher:informatik:oberstufe:algorithmen:sorting:radixsort:start

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung
Nächste Überarbeitung		 Vorherige Überarbeitung
faecher:informatik:oberstufe:algorithmen:sorting:radixsort:start [07.07.2025 18:42] – Frank Schiebelfaecher:informatik:oberstufe:algorithmen:sorting:radixsort:start [07.07.2025 19:01] (aktuell) – Frank Schiebel
Zeile 24: Zeile 24:
 Überlege, welche Eigenschaften die Elemente einer Liste haben müssen, wenn man sie mit Radix-Sort sortieren möchte. Gib weitere Beispiele an, die Listen beinhalten die dich aus zahlen bestehen. Überlege, welche Eigenschaften die Elemente einer Liste haben müssen, wenn man sie mit Radix-Sort sortieren möchte. Gib weitere Beispiele an, die Listen beinhalten die dich aus zahlen bestehen.
  
 +----
 +{{:aufgabe.png?nolink  |}}
 +=== (A2) ===
 +
 +Implementiere Radix-Sort im Programmgerüst der entsprechenden Klasse in der Bluej-Vorlage von https://codeberg.org/qg-info-unterricht/algs4-sort-bluej. 
 +
 +**A2.1** Betrachte zunächst den Konstruktor: Notiere dir die Bedeutung von $n$, $digits$ und $a$ im Kontext von Radix-Sort. Welche Aufgabe hat die for-Schleife?
 +
 +Kontrolliere deine Überlegung mit Hilfe entsprechender Eingaben, indem du das erzeugte Objekt untersuchst.
 +
 +**A2.2** Als "Buckets" verwenden wir ein "Array aus ArrayLists":
 +
 +<code java>
 +// Buckets als Array aus ArrayLists erzeugen
 +ArrayList<Integer>[] bucket = new ArrayList[10]; 
 +for(int i=0; i<10; i++) {
 +     bucket[i] = new ArrayList<>();
 +}
 +</code>
 +
 +''bucket[7]'' ist die ArrayList, die alle Elemente mit der betrachteten Ziffer ''7'' aufnimmt. Analog für alle anderen Ziffern, die in den Zahlen vorkommen können (0-9).
 +
 +**A2.3** Implementiere die beiden Abschnitte "Verteilen" und "Einsammeln" so, dass die eingegebenen Zahlen anschließend nach ihrer Einer-Ziffer sortiert sind. Beachte die Anmerkungen in der Vorlage!
 +
 +**A2.4** Wiederhole den Verteilen/Einsammeln-Zyklus nun für jede Stelle der Zahlen, indem du eine Schleife um diese Abschnitte herum erzeugst - beachte die Kommentare im Code. 
 +
 +Du musst dir noch überlegen, wie du der Reihe nach Einer-, Zehner, Hunderter-Stelle ermitteln kannst, um bei jedem neuen Durchlauf in die passenden Buckets zu sortieren. 
 +
 +Außerdem musst du festlegen, wie oft diese äußere Schleife durchlaufen werden soll - ''digits'' hilft hier weiter.
  
  
Zeile 64: Zeile 93:
     }     }
 </code> </code>
 +++++
  • faecher/informatik/oberstufe/algorithmen/sorting/radixsort/start.1751913742.txt.gz
  • Zuletzt geändert: 07.07.2025 18:42
  • von Frank Schiebel