Alphabetische sortierung mit Quicksort

[Shibas]

Moin,

ich hab mir ein Programm für den Quicksort geschrieben das Wörter aus einer eingelesenen Text Datei alphabetisch ordnen soll. Das ganze funktioniert auch ganz gut allerdings nur für die sortierung der anfangsbuchstaben.

zur verfügung habe ich das wort einmal als normalen string und als char array die in einen Daten objekt kombiniert sind.

mein Problem hierbei ist das ich nicht wirklich weiss wie ich es umsetzen könnte das die wörter auch unter der nachfolgenden buchstaben sortiert werden also:

aab
aac
abb
bab
bbc

hätte jemand einen ansatz wie ich sowas realisieren könnte?

ich darf dafür allerdings keine java eigenen methoden zum sortieren benutzen ;(

würde mich über jede hilfe freuen

mfg

Shibas

 

[SlaterB]

hängt alles davon ab wie zwei Einträge miteinander verglichen werden, das muss auf eine Codstelle/ Untermethode konzentriert werden,
und dann eben ändern, Schleife über alle Zeichen bis erstes unterschiedliches gefunden

 

[Paeddah]

Hi!

Wie SlaterB schon schrieb, musst du die Funktion, die den Vergleich ausführt ändern.

Meine Glaskugel vermutet, dass du zur Zeit nur ein Zeichen - das Erste - für den vergleich heranziehst. Dass muss du dahingehend ändern, dass du die beiden aktuellen Kandidaten Stelle für Stelle vergleichst und die erste differente Stelle auswertest.

Grüße

 

[Shibas]

so ich hab mir jetzt mal was zusammen geschuhstert was in etwa hinkommen müsste. Was mir allerdings noch zu schaffen macht ist das meine datenfelder unterschiedlich lang sind und ich bei meinen algorithmus dann abfragen müsste ob ein feldelement existiert. Hätte da wer nen tipp wie ich das machen könnte also etwas alla if(arrayfeld[x].exist = true) oder so?

 

[SlaterB]

if(x < arrayfeld.length)

 

[kirax]

Müsst ihr Quicksort verwenden?

Radix-Sort wäre da nämlich theoretisch schneller. Und einfacher, weil da kannst du es einfach rekursiv machen.
Bin mir grad nicht sicher, ob das bei Quicksort auch geht.

 

[icarus2]

Müsst ihr Quicksort verwenden?

Radix-Sort wäre da nämlich theoretisch schneller. Und einfacher, weil da kannst du es einfach rekursiv machen.
Bin mir grad nicht sicher, ob das bei Quicksort auch geht.

Klar, die einfachste Implementierung von Quicksort ist rekursiv.

Radix-Sort dürfte in diesem Fall auch gehen und wäre wohl auch performanter. Aber Radix-Sort würde ich auf keinen Fall rekursiv implementieren. Das kann man iterativ ziemlich einfach machen und Iteration ist meistens schneller als Rekursion.

*Edit
Bei Radix-Sort sollte auch die Länge bei allen zu vergleichenden Strings gleich sein. Wenn dann die Länge der Strings sehr lange wird ist Radix-Sort nicht mehr wirklich schneller als Quicksort. Radix-Sort hat mich, wenn ich mich richtig erinnre O(m*n) Worst case und Quicksort hat im Erwartungswert O(n*logn).

 

[Shibas]

Müsst ihr Quicksort verwenden?

Radix-Sort wäre da nämlich theoretisch schneller. Und einfacher, weil da kannst du es einfach rekursiv machen.
Bin mir grad nicht sicher, ob das bei Quicksort auch geht.

Jo müssen wir ist quasi sowas wie ne "Urschleim" aufgabe wo wir alles selber gemacht haben sollen bevor wir die java methoden benutzen

 

[HoaX]

Warum nimmt du nicht einfach String#compareTo(String) zum Vergleichen? 😉

 

[Andi_CH]

Wohl darum:

Jo müssen wir ist quasi sowas wie ne "Urschleim" aufgabe wo wir alles selber gemacht haben sollen bevor wir die java methoden benutzen

 

[kirax]

Aber Radix-Sort würde ich auf keinen Fall rekursiv implementieren. Das kann man iterativ ziemlich einfach machen und Iteration ist meistens schneller als Rekursion.

Joar meinte ich doch... 😀