Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:algorithmen:sorting:radixsort:start [01.07.2025 08:52] – Frank Schiebel
+++ faecher:informatik:oberstufe:algorithmen:sorting:radixsort:start [07.07.2025 19:01] (aktuell) – Frank Schiebel
@@ Zeile 22: / Zeile 22: @@
 === (A1) ===
-Überlege, welche Eigenschaften die Elemente einer Liste haben müssen, wenn man sie mit Radix-Sort sortieren möchte. Gib Beispiele an.
+Ü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.
+++++ Lösungsvorschlag |
+<code java>
+    // Radixsort sortiert die ArrayList
+    public void sort(ArrayList<Integer> a) {
+        // Unsortiertes Array ausgeben
+        System.out.println(Arrays.toString(a.toArray()));
+        // Buckets als Array aus ArrayLists erzeugen
+        ArrayList<Integer>[] bucket = new ArrayList[10];
+        for(int i=0; i<10; i++) {
+            bucket[i] = new ArrayList<>();
+        }
+        for(int d=0 ; d<digits; d++) {
+            int q=1;
+            for(int i=0; i<d; i++) {
+                q=q*10;
+            }
+            // Verteilen
+            for(int z=0; z<a.size(); z++) {
+                int ziel_bucket = (a.get(z)/q)%10;
+                bucket[ziel_bucket].add(a.get(z));
+            }
+            // Einsammeln
+            int pos = a.size()-1;
+            for(int b=9; b>=0; b--) {
+                while(!bucket[b].isEmpty()) {
+                    a.set(pos, bucket[b].removeLast());
+                    pos--;
+                }
+            }
+            // Zwischen/Endergebnis
+            System.out.println(Arrays.toString(a.toArray()));
+        }
+    }
+</code>
+++++