# Alphabetische sortierung mit Quicksort



## Shibas (4. Apr 2011)

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 (4. Apr 2011)

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 (4. Apr 2011)

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 (4. Apr 2011)

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 (4. Apr 2011)

if(x < arrayfeld.length)


----------



## kirax (4. Apr 2011)

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 (4. Apr 2011)

kirax hat gesagt.:


> 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 (5. Apr 2011)

kirax hat gesagt.:


> 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 (5. Apr 2011)

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


----------



## Andi_CH (5. Apr 2011)

Wohl darum:


Shibas hat gesagt.:


> 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 (5. Apr 2011)

icarus2 hat gesagt.:


> 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...


----------

