Bubble Sort

heartbeat

Hey Leute,

also ich muss hier die Namen von Personen in alphabetischer Reihenfolge sortiern. Erst wird der Nachname angeschaut und wenn der gleich ist wird der Vorname angeschaut. Wenn ich das in mein vollständiges Programm einbaue, gitb er mir die Namen zwar aus, aber nicht sortiert. Kann mir da jemand weiterhelfen

Code

/**
     * Die Teilnehmer werden in der gesamten Teilnehmerliste alphabetisch nach 
     * Nach- und Vornamen sortiert
     */

    public void sortierenNachNamen() {
        int i;
        int anzahlTeilnehmer = 0;
        TeilnehmendePerson vertauschen; //die Namen werden vertauscht

        for(i = 0; i < Uebungsgruppen.MAX_ANZAHL_TEILNEHMER *
            Uebungsgruppen.MAX_ANZAHL_GRUPPEN; i++) {

            if(teilnehmer[i] != null)
                anzahlTeilnehmer++;
            }

            if(anzahlTeilnehmer > 1) {
                for (int j = (anzahlTeilnehmer - 1); j > 0; j--) {
                    for (i = 0; i > anzahlTeilnehmer; i++) {
                        vertauschen = teilnehmer[i];
                        teilnehmer[i] = teilnehmer[i + 1];
                        teilnehmer[i + 1] = vertauschen;
                    }

                //wenn die Nachnamen gleich sind, vergleicht man die Vornamen
                if(teilnehmer[i].getNachname().compareToIgnoreCase
                        (teilnehmer[i + 1].getNachname()) == 0) {

                if(teilnehmer[i].getVorname().compareToIgnoreCase
                    (teilnehmer[i + 1].getVorname()) > 0) {

                    vertauschen = teilnehmer[i];
                    teilnehmer[i] = teilnehmer[i + 1];
                    teilnehmer[i + 1] = vertauschen;
                }
                }
                }
            }
}

Alles anzeigen

Christoph R.

Mir kommt der ganze Algorithmus irgendwie eigenartig vor. Die Variable i wird in 2 verschiedenen Schleifen als Zähler verwendet, und außerdem werden hier in der innersten for-Schleife Vertauschungen durchgeführt, noch bevor die Schlüssel überhaupt verglichen wurden. Bubble-Sort lässt sicher sicher auch einfacher implementieren. Das würde ich mal machen, vielleicht verschwindet dabei auch gleich der Fehler.

Edit: Hab's nicht laufen lassen, aber vom Prinzip her sollte es so ungefähr gehen:

Code

public void sortierenNachNamen() {
    int i, j;
    TeilnehmendePerson vertauschen; //die Namen werden vertauscht


    for(i = 0; i < Uebungsgruppen.MAX_ANZAHL_TEILNEHMER *
            Uebungsgruppen.MAX_ANZAHL_GRUPPEN; i++) {




        for (j = i - 1; j >= 0; j--) {
            bool swap = false;


            // Vertauschen wegen Nachnamen
            if(teilnehmer[j].getNachname().compareToIgnoreCase(teilnehmer[j + 1].getNachname()) > 0){
                swap = true;
            }


            // Vertauschen wegen Vornamen (bei gleichen Nachnamen)
            else if((teilnehmer[j].getNachname().compareToIgnoreCase(teilnehmer[j + 1].getNachname()) == 0) &&
            (teilnehmer[j].getVorname().compareToIgnoreCase(teilnehmer[j + 1].getVorname()) == 0)){
                swap = true;
            }


            if (swap){
                vertauschen = teilnehmer[j];
                teilnehmer[j] = teilnehmer[j + 1];
                teilnehmer[j + 1] = vertauschen;
            }
        }
    }
}

Alles anzeigen

Die Bedingungen müssen eventuell angepasst werden, je nachdem wie der Rückgabewert der compare-Funktion ausschaut.

Paulchen

Wenn ich das richtig sehe, sortierst du ein Array von Objekten vom Typ TeilnehmendePerson. Wenn es nicht darauf ankommt, dass du einen Sortieralgorithmus implementierst, sondern nur darauf, dass die Ergebnisliste sortiert ist, würde ich

entweder in der Klasse TeilnehmendePerson das Interface Comparable implementieren oder
eine Klasse schreiben, die das Interface Comparator implementiert und dem Zweck dient, zwei Objekte vom Typ TeilnehmendePerson zu vergleichen.

Dann ersparst du dir die Implementierung des Sortieralgorithmus und verwendest zur Sortierung je nach oben gewählter Vorgehensweise eine der folgenden beiden Implementierungen von Arrays.sort:

heartbeat

Christoph R.
hab deinen Code verwendet und leider läuft mein Programm noch weniger wie davor.
Kannst du mir vielleicht sagen, welche Fehler ich bei meinem Code hab. Wie kann ich das verbessern?

Christoph R.

Dass mein Code nicht genauso funktioniert wie ich ihn gepostet habe war anzunehmen. Vielleicht hab ich eine Indexgrenze falsch angegeben, eine Schleife in die falsche Richtung laufen lassen oder ähnliches. Aber vom Prinzip her wird er schon stimmen.

Der Bubble-Sort-Algorithmus vergleicht immer 2 aufeinanderfolgende Elemente und vertauscht sie falls das notwendig ist, wobei in einer äußeren Schleife die gesamte Eingabefolge n Mal durchlaufen wird. Der Suchbereich wird dabei nach jeder Iteration um 1 erweitert, bis im letzten Durchlauf schließlich alle Elemente überprüft werden (wobei dann auch das letzte Elemente ganz nach vorne rutschen kann, falls es das kleinste ist). Daraus resultiert auch die quadratische Laufzeit. Das ist das Prinzip des Algorithmus.

Wo genau die Fehler in deinem Code sind weiß ich nicht, weil mir die ganze Implementierung sehr komisch vorkommt: vertauschen vor dem Vergleich, 3 verschachtelte Schleifen, doppelte Verwendung von i als Zähler, und auch die Bedingung if (teilnehmerAnzahl > 1) sollte bei richtigen Schleifenbedingungen nicht notwendig sein. Anstatt die Implementierung zu verbessern würde ich vom Algorithmus ausgehen und diesen von Anfang an implementieren. (was jetzt nicht heißt dass deine Implementierung komplett falsch ist: kann durchaus sein dass eh nur ein kleiner Fehler drin ist; nur für mich ist sie aus den genannten Gründen einfach sehr schwer durchschaubar, denn der Algorithmus ist eigentlich viel einfacher)

Edit: Geht es nun eigentlich um die Implementierung oder eh nur um's Ergebnis? Weil wenn es nur darum geht die Daten zu sortieren, dann würde ich - so wie Paulchen schon geschrieben hat - eine vorhandene Implementierung verwenden. Nicht zuletzt deswegen, weil Bubble Sort sehr langsam ist.

Jetzt mitmachen!