Quicksort again

[r26t01]

Hallo zusammen =)

Ich habe (wie etliche vor mir) ein Problem mit dem Quicksort Algorithmus. Die anderen Threads konnten mir soweit nicht helfen, da ich die Funktionsweise schon verstanden habe, allerdings beim programmieren nicht weiterkomme.

Wir müssen in der BS ein kleines Gruppenprojekt vorbereiten für das sich jede Gruppe auf einen Algorithmus festlegen sollte. Dazu dann eine Präsentation, Beschreibung was es ist, wie es funktioniert, Struktogramm, Beispieldatei inkl. Quellcode.

Unsere Idee war es die Namen aller aus unserer Klasse in ein Array zu packen und dann nach der Länge des Namens sortieren zu lassen. Also dass geguckt wird, welches der kürzeste Name ist und der dann an die 1. Stelle gepackt wird.

Soweit so gut, unser Ansatz bisher:

#include <cstdlib>

#include <iostream>


using namespace std;


int main()

{

    int i;

    char *namen[13] = {"Andreas", "Sascha", "Daniel", "Kevin", "Engin", "Jennifer", "Jasmin", "Ramona", "Tim", "Kevin", "Peer", "Jan-Phillip", "Christian"};

    int size = sizeof(namen[13]);


    cout << "Quicksort Beispiel: Klassennamen nach Laenge sortieren:" << endl;

    cout << "_______________________________________________________" << endl;

    cout << endl;


    cout << "Ausgangssortierung: " << endl;

    cout << endl;


    for (i = 0; i < 13; i++)

    {

        cout << namen[i] << endl;

        cout << endl;

    }      

Nun das Problem, wie fange ich mit dem Quicksort an? Mir bzw. uns ist bewusst, dass wir mit sizeof(namen) erstmal die Länge der einzelnen Elemente herausfinden müssen und darauf dann den Quicksort Algorithmus anwenden.

Vielen Dank und liebe Grüße =)

[Guybrush Threepwood]

Mir bzw. uns ist bewusst, dass wir mit sizeof(namen) erstmal die Länge der einzelnen Elemente herausfinden müssen und darauf dann den Quicksort Algorithmus anwenden.

nicht mit sizeof sondern mit strlen

Wo genau ist denn dann das Problem wenn ihr wisst wie der Quicksort funktioniert?

[r26t01]

Das Problem liegt bei der Umsetzung von der Vorgehensweise des Algorithmus zum programmieren.

1. Schritt: Pivot auswählen

1. Problem: Wie programmiert man das?

2. Schritt: Alle Elemente < Pivot nach links, alle Elemente > Pivot nach rechts.

2. Problem: Wie programmiert man das?

Ich hab mir schon ein paar Bsp. rausgesucht, aber die waren nur mit Zahlen (nicht mit Namen) und auch nicht wirklich leicht verständlich (eins war mit OOP und soweit sind wir in der BS nicht einmal).

Wenn jemand einen Tipp bzw. ein leicht verständliches Bsp. hat an dem wir uns entlanghangeln können, wäre das schon eine große Hilfe.

Bei dem Bsp. in unserem Buch steht nur bei:

".... Die eigentliche Logik dieses Algorithmus bleibt verborgen." Tolles Buch bzw. Bsp.

[flashpixx]

Ich hab mir schon ein paar Bsp. rausgesucht, aber die waren nur mit Zahlen (nicht mit Namen) ...

Du willst doch im Grunde nach der Länge sortieren und die Länge ist eine Zahl. Die Sortierung ist identisch, nur dass Du eben um Dein Element ein "strlen" drum herum packst. Interessant wird es, wenn Du das ganze nicht nach Längen sondern nach Alphabet sortieren möchtest

Bei dem Bsp. in unserem Buch steht nur bei:

".... Die eigentliche Logik dieses Algorithmus bleibt verborgen." Tolles Buch bzw. Bsp.

Schau Dir dieses Buch an Algorithmen: Amazon.de: Robert Sedgewick: Bücher das ist "der Klassiker" für Algorithmen

[Klotzkopp]

Das Problem liegt bei der Umsetzung von der Vorgehensweise des Algorithmus zum programmieren.

1. Schritt: Pivot auswählen

1. Problem: Wie programmiert man das?

Welchen Pivotauswahlalgorithmus willst du denn umsetzen?

2. Schritt: Alle Elemente < Pivot nach links, alle Elemente > Pivot nach rechts.

2. Problem: Wie programmiert man das?

Durch wiederholtes Vergleichen und Vertauschen. Darauf beruhen fast alle Sortieralgorithmen. Wikipedia ist da übrigens ziemlich ausführlich

Ich hab mir schon ein paar Bsp. rausgesucht, aber die waren nur mit Zahlen (nicht mit Namen)

Es ist völlig egal, was du sortierst. Du musst nur in der Lage sein, die grundlegenden Operationen des Algorithmus (Vergleichen und Vertauschen) umzusetzen.

[r26t01]

Mit den andern beiden hab ich noch nicht weiter gesprochen, aber die median of three bzw. in unserem Fall median of thirteen könnten wir anwenden. Dass das 6. oder 7. Element als Pivot dient und demnach alle anderen damit verglichen werden und in die entsprechende Teilliste eingeordnet werden.

[Klotzkopp]

Mit den andern beiden hab ich noch nicht weiter gesprochen, aber die median of three bzw. in unserem Fall median of thirteen könnten wir anwenden. Dass das 6. oder 7. Element als Pivot dient und demnach alle anderen damit verglichen werden und in die entsprechende Teilliste eingeordnet werden.

Von median of 13 habe ich im Zusammenhang mit Quicksort noch nie etwas gehört. 3 oder 9 ist mir geläufig. Wie kommst du auf 13?

Und ist dir klar, dass du dann immer wieder 13 Zahlen sortieren musst, und zwar mit einem anderen Algorithmus, nur um das Pivotelement zu finden?

[r26t01]

Würde er sich daraufhin nicht den 6. oder 7. Wert nehmen, die anderen damit vergleichen und jeweils 2 gleichgroße Teillisten erstellen?

Die Länge wird auf jeden Fall jetzt ausgegeben (danke für die Verbesserung bzgl. strlen anstatt sizeof).

edit: war nen Denkfehler mit median of 13. Ich sollte nicht von der Anzahl meiner Elemente ausgehen *Kopf vor Wand hau*

Bearbeitet 4. März 2010 von r26t01

[Klotzkopp]

edit: war nen Denkfehler mit median of 13. Ich sollte nicht von der Anzahl meiner Elemente ausgehen

Richtig.

Der Ansatz, das Pivotelement über einen Median auszuwählen, dient nur der Effizienzsteigerung von Quicksort. Quicksort funktioniert auch, wenn du irgendein Pivotelement auswählst (z.B immer das erste oder das in der Mitte).

[flashpixx]

Ich will mal ergänzen:

Welchen Pivotauswahlalgorithmus willst du denn umsetzen?

Quicksort ist ein Divide-and-Conquer (Teile & Herrsche) Algorithmus, d.h. Du teilst die Gesamtmenge in 2 Teile und teilst diese beiden wieder und wieder. Wenn Du am Ende dieser rekursiven Kette bist, sortierst Du.

Ich würde Dir erst einmal vorschlagen, dass Du den Algo so implementierst, dass Du immer die Menge genau in der Mitte halbierst. Wenn Du das dann hast, kannst Du auch die Pivotisierung implementieren, das wäre dann die Teilung an einer beliebigen Stelle.

Durch wiederholtes Vergleichen und Vertauschen.

und das heißt bei Dir konkret, Du musst die Länge Deiner Strings vergleichen und ggf vertauschen

[Klotzkopp]

Ich würde Dir erst einmal vorschlagen, dass Du den Algo so implementierst, dass Du immer die Menge genau in der Mitte halbierst. Wenn Du das dann hast, kannst Du auch die Pivotisierung implementieren, das wäre dann die Teilung an einer beliebigen Stelle.

Die Stelle, an der geteilt wird, ergibt sich bei Quicksort durch die Wahl des Pivotelements.

[pascal87]

Neben den guten Erläuterungen bei Wikipedia zu den einzelnen Sortieralgorithmen, finde ich diese Erklärung mit Codebeispielen sehr gut, ist zwar Java, solltest du aber schnell nachvollziehen können.

Bearbeitet 4. März 2010 von pascal87

[Wodar Hospur]

Die Seite für irgendwas ist und bleibt ja

die hier.

Ansonsten ist die Länge schon etwas langweilig, interessanter wäre es doch wirklich jeden Namen zu sortieren .

[r26t01]

Danke für die Links, werden sie uns dann morgen zusammen nochmal angucken (kann ja nicht sein, dass ich das alles alleine machen muss).

Alphabetische Sortierung haben wir uns auch schon überlegt, aber wir sind ja schon froh, wenn es erstmal nach der Länge klappt. Je nachdem wie viel Zeit über ist, werden wir vl. doch mal überlegen, ob wir es nicht doch alphabetisch machen.