QuickSort und Liste

[MaggyMo]

Guten Morgen,

ich versuche derzeit eine Liste (ObservableList) mithilfe eines QuickSorts zu sortieren. Leider finde ich nur Beispiele, die das mit einem Array machen, aber das habe ich nicht. Nun zu meiner Frage:
Kann man eine Liste mit dem QuickSort sortieren? Und wie mache ich das, wenn ich keine Zahlen, sondern Wörter sortieren möchte?

Liebe Grüße und Danke im Voraus

 

[mihe7]

Ob Array oder Liste spielt keine Rolle. Du ersetzt den lesenden Arrayzugriff einfach durch get() und den schreibenden durch set(). Ebenfalls keine Rolle spielt es, welche Objekte sich in der Liste befinden. Das einzige Kriterium ist, dass eine Ordnung definiert oder definierbar ist. String-Objekte implementieren z. B. das Comparable-Interface, über das eine solche Ordnung definiert wird.

Statt a < b (für primitive Werte) kannst Du bei Objekten, die Comparable implementieren, schreiben: a.compareTo(b) < 0.

 

[MaggyMo]

Hmmm also irgendwie blicke ich da nicht wirklich durch Die zweite if Abfrage wirft Fehler und ich bin mir irgendwie auch unsicher.
Das ist mein Code bis jetzte:

public ObservableList<Person> nachMerkmalSortieren(String merkmal, int l, int r) {
        int q;
        if(l<r) {
            q = partition(l, r);
            nachMerkmalSortieren(merkmal, l, q);
            nachMerkmalSortieren(merkmal, q+1, r);
        }
        return listenVerzeichnis;
    }
    
    public int partition(int l, int r) {
        int i;
        int j;
        int listenindex = (l+r)/2;
        
        int x = listenVerzeichnis.indexOf(listenindex);
        i = l-1;
        j = r+1;
        while(true) {
            do {
                i++;
            } while (listenVerzeichnis.get(i).getHoehe() < x);
            
            do {
                j--;
            } while(listenVerzeichnis.get(j).getHoehe() > x);
            
            if(i<j) {
                double k = listenVerzeichnis.get(i).getHoehe();
                listenVerzeichnis[i] = listenVerzeichnis[j];
                listenVerzeichnis[j] =k;
            } else {
                return j;
            }
        }
    }

 

[MaggyMo]

Hmmm also irgendwie blicke ich da nicht wirklich durch Die zweite if Abfrage wirft Fehler und ich bin mir irgendwie auch unsicher.
Das ist mein Code bis jetzte:


public ObservableList<Person> nachMerkmalSortieren(String merkmal, int l, int r) {
int q;
if(l<r) {
q = partition(l, r);
nachMerkmalSortieren(merkmal, l, q);
nachMerkmalSortieren(merkmal, q+1, r);
}
return listenVerzeichnis;
}

public int partition(int l, int r) {
int i;
int j;
int listenindex = (l+r)/2;

int x = listenVerzeichnis.indexOf(listenindex);
i = l-1;
j = r+1;
while(true) {
do {
i++;
} while (listenVerzeichnis.get(i).getHoehe() < x);

do {
j--;
} while(listenVerzeichnis.get(j).getHoehe() > x);

if(i<j) {
double k = listenVerzeichnis.get(i).getHoehe();
listenVerzeichnis = listenVerzeichnis[j];
listenVerzeichnis[j] =k;
} else {
return j;
}
}
}

Vlllt ist noch wichtig zu wissen, dass ich in der Liste mehrere Objekte eines POJOs habe, also keine Strings oder so.
Und dann würde ich die Liste gerne nach den Attributen des Objektes sortieren.

 

[mihe7]

Hmmm also irgendwie blicke ich da nicht wirklich durch

Implementiere einfach mal den Algorithmus von https://de.wikipedia.org/wiki/Quicksort

 

[MaggyMo]

Implementiere einfach mal den Algorithmus von https://de.wikipedia.org/wiki/Quicksort

Danke das hat geklappt ich kann jetzt die entsprechenden Zahlen sortieren
Bei Strings muss ich ja dann mit CompareTo arbeiten oder?
Dort wird mir ja dann eine positive Zahl ausgegeben wenn String 1 > String 2 usw.
Wie geht man da denn dann weiter vor?

 

[MaggyMo]

Danke das hat geklappt ich kann jetzt die entsprechenden Zahlen sortieren
Bei Strings muss ich ja dann mit CompareTo arbeiten oder?
Dort wird mir ja dann eine positive Zahl ausgegeben wenn String 1 > String 2 usw.
Wie geht man da denn dann weiter vor?

Hat sich erledigt hat gerade geklappt