Ist das C ++ - Quicksort-Programm in Ordnung?

  • Ich habe ein Quicksort-Programm in C ++ geschrieben.

    1. Ist es in Ordnung, es auf diese Weise zu implementieren?
    2. Verwende ich Zeiger richtig?
    3. Ist mein Stil in Ordnung?
    4. Haben Sie eine Idee, die Geschwindigkeit zu erhöhen oder Speicher zu sparen?

     void change(int *i, int *j)
    {
    int temp = *j;
     *j = *i;
    *i = temp;
    }
    
    
    int *toplace(int *start, int *end)
    {
        int *i = start+1, *j= end;
    
        while(i<=j)
        {
        for(; *i<=*start && i<=end; i++);
        for(; *j>=*start && start+1<=j; j--);   
        if (i<j) change(i++,j--); 
        }
    
        change(start,i-1); 
        return i-1;
    }
    
    
    
    void quicksort(int *start, int *end)
    {
        if (start >= end) return;
    
        for(int *debug = start;debug<=end;debug++) std::cout<<*debug <<" ";
        std::cout<<std::endl;  //this and...
    
        int *temp = start;
        temp = toplace(start,end);
    
        for(int *debug = start;debug<=end;debug++) std::cout<<*debug <<" ";
        std::cout<<std::endl; //...this are only to "see under the hood"
        std::cout<<std::endl;
    
        quicksort(start,temp-1);
        quicksort(temp+1,end);
    
    }
     

    Eine Beispielanwendung:

     int main(int argc, char* argv[])
    {
        int A[] = {5,14,8,12,1,2,11,15,6,9,7,3,13,4,10};
        int n = sizeof (A) / sizeof(A[0]);
    
        quicksort(A, &A[n-1]);
    
        for (int i =0; i<n; i++) std::cout<<A[i] <<" ";
    
        getchar();
        return 0;
    }
     

    erzeugt die Ausgabe:

     5 14 8 12 1 2 11 15 6 9 7 3 13 4 10
    1 4 3 2 5 12 11 15 6 9 7 8 13 14 10
    
    1 4 3 2
    1 4 3 2
    
    4 3 2
    2 3 4
    
    2 3
    2 3
    
    12 11 15 6 9 7 8 13 14 10
    8 11 10 6 9 7 12 13 14 15
    
    8 11 10 6 9 7
    6 7 8 10 9 11
    
    6 7
    6 7
    
    10 9 11
    9 10 11
    
    13 14 15
    13 14 15
    
    14 15
    14 15
    
    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
     
    08 January 2014
    Jamal
2 answers
  • Die Schnittstelle zu Quicksort:

     quicksort(A, &A[n-1]);
     

    In C würde ich erwarten, dass ein Zeiger und ein angezeigt werden size.
    In C ++ würde ich erwarten, dass zwei Iteratoren (wie oben) zu sehen sind, aber der Endpunkt ist in der Regel einer nach dem Ende (wenn Sie mit den C ++ - Idiomen und der STL-Methode übereinstimmen möchten Dinge).

     quicksort(A, A+n); // This is what I would expect to see.
     

    Ändern!
    Normalerweise würde ich das swap ()

     void change(int *i, int *j)
    {
        int temp = *j;
         *j = *i;
         *i = temp;
    }
     

    Auch in C ++ würde ich die zu verweisenden Werte als Referenz übergeben. Und es gibt bereits eine std :: swap (), die perfekt funktioniert.

    Ihre for () - Schleifen, die nichts im Körper tun.

     for(; *i<=*start && i<=end; i++);
     

    Diese sind bei Wartungsarbeiten schwer lesbar. Auf den ersten Blick sieht es so aus, als hätten Sie den Code versehentlich nicht richtig eingerückt. Sie müssen den Code studieren, um zu verstehen, dass er korrekt ist. Ich finde es am besten, einen leeren Körper zu setzen (vielleicht sogar mit einem Kommentar / * absichtlich leer * /

     for(; *i<=*start && i<=end; i++)  { /* Empty */ }
     

    In Ihren Schleifen testen Sie die Schleifenvariable gegen Anfang und Ende. Sollten sie nicht gegeneinander getestet werden?

     while(i<=j)
    {
    for(; *i<=*start && i<=end; i++);
    for(; *j>=*start && start+1<=j; j--);   
    
    // Should be:
    
    for(; *i<=*start && i <= j; i++) { /* Empty */ }
    for(; *j>=*start && i <= j; j--) { /* Empty */ }
     

    Ihre schnelle Sortierung scheint zu funktionieren, ist jedoch in einigen Funktionen etwas unüblich.

    Der Pivotpunkt *start. Gleiche Werte scheinen in beide Sub-Buckets zu passen Normalerweise würden sie in einen bestimmten Bucket gehen.

    Sie verwenden immer das erste Element als Pivot-Punkt, was zu einem Worst-Case-Verhalten von quicksort führt, wenn die Liste bereits sortiert ist. Wählen Sie entweder ein zufälliges Element oder das Element in der Mitte der Partition.

    Derzeit arbeitet Ihr Code mit Zeigern auf Ganzzahlen. In Wirklichkeit verwenden Sie jedoch Zeiger als Iteratoren. Sie sollten daher eine Vorlage erstellen Da es sich bei den Eingaben also nicht um Zeiger, sondern um generische Iteratoren handelt, können Sie den Algorithmus dann für jeden Containertyp verwenden (mit Der Nebeneffekt, dass es mit jedem Typ funktioniert, der den Operator & lt; = implementiert.

    24 November 2011
    Joseph Daigle
  • Zunächst gibt es in der Standardbibliothek bereits eine std::sort -Funktion. Wenn Sie sich dessen bewusst sind und dies nur als Lernübung geschrieben haben, die in Ordnung ist, aber wenn Sie diesen Code tatsächlich in der Produktion verwenden möchten, gibt es keinen Grund, stattdessen std::sort zu verwenden. Das heißt, hier ist eine Überprüfung Ihres Codes:


    Effizienz

    Eine wichtige Sache Was Sie über Ihren Algorithmus beachten sollten, ist, dass Sie das erste Element des Arrays als Pivot-Element verwenden. Dies ist ziemlich ineffizient, wenn Sie ein Array sortieren, das bereits teilweise sortiert ist (was zu einer quadratischen Laufzeit führt). Sie sollten stattdessen ein zufälliges Element verwenden.

    Ansonsten sehe ich in Ihrem Code keine Ineffizienzen.


    Genericity

    Derzeit kann Ihr Code nur für Arrays von Ints verwendet werden. Dies ist schlecht, weil es keinen Grund gibt, a) Sie sollten nicht verwenden, um a) alles zu verwenden, das mit <, > usw. anstelle von Ints vergleichbar ist, und b) andere Sammlungen wie vector statt Arrays. Wenn Sie Ihre Funktionen in Vorlagenfunktionen umwandeln, können Sie dies ganz einfach erreichen, indem Sie alle Vorkommen von int* durch ein Vorlagenargument ersetzen.

    Sie können Ihre Sortierfunktion mit generalisieren ein optionales Vergleicherargument wie std::sort tut.


    Codelesbarkeit und allgemeine bewährte Verfahren

    < Ich würde Ihre change -Funktion in swap umbenennen, da diese Funktion normalerweise aufgerufen wird und der Name change keine wirklich gute Vorstellung von der Funktion der Funktion gibt. Ich würde es auch ändern, um Verweise anstelle von Zeigern zu verwenden, da es ratsam ist, die Verwendung von Zeigern zu vermeiden, wenn Sie sie nicht benötigen. Und noch einmal: Wenn Sie dies nicht einfach als Lernübung implementiert haben, verwenden Sie std::swap, anstatt Ihr eigenes zu erstellen (was dasselbe tut).

    In Ihrem Sortierfunktion Sie sollten temp in etwas beschreibender umbenennen, weil die

    24 November 2011
    RoyiJohn Robertson