Radixsort mit Basis b = 6

Question

Aufgabe

Die Zahlenfolge A= [231,230,101,777,450,381,950,517] ist durch Radixsort mit Basis b= 6 zu sortieren.Stellen Sie dabei, in b-ärer Darstellung, die Belegung der Schlangen nach jeder Verteilungsphase sowie das Array A nach jeder Sammelphase in einer Tabelle der folgenden Form dar.

Phase 1

Verteilungsphase Queue 0: Queue 1: Queue 2: Queue 3: Queue 4: Queue 5: Queue 6:

Sammelphase Array (A)

Problem/Ansatz

Ich weiß zwar wie Radix-Sort funktioniert [erst die letzte Dezimalstelle anschauen und sortieren. Danach die vorletzte us.w.]. Aber mich verwirrt b = 6.

Muss ich die Dezimalzahlen jetzt vorher ins 6er-System umwandeln? Also 231 im 10er-System wird zu 1023 im 6er-System u.s.w ? Und wieso sprechen die hier von 6 Verteilungsphasen? Normalerweise guckt man sich doch bei 3-stelligen Zahlen die hinterste Stelle an, dann die mittige und dann die erste Stelle. Würde es im Zehnersystem sein, hätt ich jetzt so sortiert:

1. Durchgang:

230

450

950

231

101

381

777

577

2. Durchgang:

101

517

230

231

450

950

777

381

3. Durchgang:

101

230

231

381

450

517

777

950

Kann mir jemand bitte erklären, wie man das jetzt mit Basis b = 6 machen soll?

LG

Marceline, The Vampire Queen

Comments

Hallo Marceline,

Muss ich die Dezimalzahlen jetzt vorher ins 6er-System umwandeln?

Im Prinzip ja. Ich versetehe die Aufgabestellung genau so.

Hast Du noch Interesse an einer Antwort? Ich frage deshalb, weil Deine Frage schon ein wenig her ist; vielleicht hat sie sich schon erledigt ...

---

Danke, Werner-Salomon.

Ich versteh' nur nicht, warum der Übungsgruppenleiter in der Aufgabenstellung von 6 Verteilungs und 6 Sammelphasen spricht. Ich krieg' es irgendwie nur mit 4 hin.

Zuerst wandle ich die Zahlen um ins 6er System

231 -> 1023

230 -> 1022

101 -> 245

777 - 3333

450 - 2030

381 - 1433

950 - 4222

517 - 2221

Zuerst sortier ich dann nach dem "Einer", also in der 1. Phase:

2030, 2221, 1022, 4222, 1023, 3333, 1433, 245.

In der zweiten Phase wir dnach der "Zehner"-Stelle sortiert, d.h.

221, 1022, 4222, 1023, 2030, 3333, 1433, 245

In der dritten Phase nach dem Hunni sortieren:

1022, 1023, 2030, 2221, 4222, 245, 3333, 1433

Und in der vierten Phase nach der Tausender-Stelle:

245, 1022, 1023, 1433, 2221, 3333, 4222

Zack, ferdisch: Radix-Sort. (?)

Kannst du mir bitte sagen, was ich falsch gemacht hab, bzw. wie man hier auf die gewünschten 6 Phasen kommt.

Answer 1

Hallo Marceline,

Kannst du mir bitte sagen, was ich falsch gemacht hab

ich denke, dass Du gar nichts falsch gemacht hast! Die Anzahl der Verteilungsphasen ist nur von der Größe der gößten Zahl in der Folge abhängig. Vielleicht hat sich der Übungsleiter nur vertan.

Es sind auch nicht 6 Verteilungsphasen, sondern 6 Fächer bzw. Queues - also Queue0 bis Queue 5 und nicht Queue0 bis Queue6!

Noch ein Hinweis: die Umwandlung in des 6'er-System der Zahlen kann man im Programm direkt mit dem Einsortieren der Zahlen in die Fächer kombinieren. Man berechnet pro Durchgang nur einmal den Rest bei der Division durch 6 und in Abhängigkeit des Rests ordnen man die Zahl dem Fach zu. Gleichzeitig merkt man sich dann das ganzzahlige Ergebnis bei der Division durch 6 und im nächsten Schritt erzeugt man den Rest von dem vorhergehenden Divisions-Ergebnis. Das Verfahren stoppt, Wenn alle diese Ergebnisse =0 sind.

Beispiel mit der 450:

1. Division durch 6 gibt 75 Rest 0. 450 in Fach 0 und die 75 merken.

2. Division der 75 durch 6 gibt 12 Rest 3. 450 in das 3. Fach und 6 merken.

3. Division 6 durch 6 gibt 1 Rest 0 - also wieder die 450 in Fach 0 und 1 merken.

4. Division der 1 durch 6 gibt 0 Rest 1 - 450 in Fach 1 und da die 0 bleibt.

Bleibt bei allen Zahlen die 0 übrig, so bist Du fertig.

Bedenke dass im Speicher eines Rechners die Zahlen ja auch nicht im Dezimal- sondern im Binärsystem vorliegen!

Gruß Werner