✔ Implementierung quickSort auf ein Array von String

[Xching]

Hallo Zusammen,

ich habe meinen Code noch einmal komplett überarbeitet. Ich hab Quicksort zuerst mit int-Werten implementiert und jetzt in String umgewandelt. Leider funktioniert mein Vergleich nicht richtig, so dass meine Liste nur zum teil sortiert wird.

    public class Quicksort {
     
            /**
             * Hilfsmethode zum Vertauschen zweier Elemente
             *
             * @param personenListe
             * @param idx1
             * @param idx2
             */
            public static void tausche(Person[] personenListe, int links, int rechts) {
                    Person tmp = personenListe[links];
                    personenListe[links] = personenListe[rechts];
                    personenListe[rechts] = tmp;
            }
     
            /**
             * Hilfsmethode zum Zerlegen der Folge
             *
             */
            public static int partition(Person[] personenListe, int unten, int oben, int pivot) {
                    int pn = unten; // Untergrenze
                    Person pv = personenListe[pivot]; // PivotElement
     
                    // PivotElement an das Ende vershieben
                    tausche(personenListe, pivot, oben);
                    for (int i = unten; i < oben; i++) {

                            if ((personenListe[i].Equals(pv))) {
                                    tausche(personenListe, pn++, i);
                            }
                    }
                    // PivotElement an die richtige Position kopieren
                    tausche(personenListe, oben, pn);
                    // neue PivotPosition zurückgeben
                    return pn;
            }
     
            /**
             * Hilfmethode zum rekursiven Sortieren
             *
             */
            public static void qSort(Person[] personenListe, int unten, int oben) {
                    // PivotElement bestimmen
                    int pivot = (unten + oben) / 2;
                    if (oben > unten) {
                            // Feld zerlegen
                            int pn = partition(personenListe, unten, oben, pivot);
                            // und Partitionen zerlegen
                            qSort(personenListe, unten, pn - 1);
                            qSort(personenListe, pn + 1, oben);
                    }
            }
     
            public Person[] quickSort(Person[] personenListe) {
                    qSort(personenListe, 0, personenListe.length - 1);
                    return personenListe;
            }
     
    //      public static void main(String[] args) {
    //              Person[] unsortiert = { "F H A B C R D E" };
    //              System.out.println("F H A B C R D E");
    //              Person[] sortiert = quickSort(unsortiert);
    //              for (int i = 0; i < sortiert.length; i++) {
    //                      System.out.print(sortiert[i] + " ");
    //              }
    //
    //      }
    }

 

[sheel]

Hi

a) statt int[] nimmst du String[]
b) Überall, wo zwei int auf >, < oder == geprüft werden vergleichst du jetzt,
welcher String im Alphabet zuerst kommen würde (oder ob sie gleich/equals sind).

 

[Xching]

ich danke ihnen für ihre Antwort aber ich weiß es nicht , wie ich vergleiche, welche String im Alphabet zuerst kommen würde

 

[sheel]

a==b wird zu a.equals(b)
a>b wird a.compareTo(b)>0
a<b wird a.compareTo(b)<0

edit @zerix: Daran hab ich gar nicht gedacht

 

[zerix]

Man könnte auch komplett die compareTo verwenden. ;-)
a==b -> a.compareTo(b) == 0

So bräuchte man die Methode nur einmal auszuführen merkt sich den Rückgabewert und vergleicht nur noch den. So wird das ganze auch gleich etwas performanter.


Gruß

Sascha

 

[Xching]

ich habe neue Code in String umgewandelt aber mit Vergleich funktioniert noch nicht richtig, ich weiß es nicht wo der Fehler liegen könnte

 

[timestamp]

Das wissen wir auch nicht wenn du keinen Code rausrückst...

 

[Xching]

ich habe oben noch mal neu gepostet und gespeichert, es zeigt mir Fehler bei equals und ich weiß es nicht warum?

 

[timestamp]

Weil equals kleingeschreiben wird, und nicht groß.