Erster Quicksort Versuch



  • Hallo,

    ich versuche mich gerade an Quicksort. Es sollten dabei folgende Funktionen benutzt werden:

    void swap ( std:: vector <int >& v, int i, int j);
    int partition ( std::vector <int >& v, int ileft , int iright , int ipivot );
    void quicksort ( std::vector <int >& v, int ileft , int iright );
    

    (Zu einfachheitshalber werde ich statt swap() hier std:swap() direkt nutzen.)

    Ich habe mir https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme durchgelesen und mein Program an dem Pseudocode orientiert.

    Hoare v1:

    int partition(std::vector<int>& v, int ileft, int iright, int ipivot)
    {
      int i = ileft- 1 , j = iright + 1;
    
      while (true)
      {
        do 
        {
          i++;
        } while (v[i] < ipivot);
    
        do
        {
          j--;
        } while (v[j] > ipivot); 
    
        if (i >= j) 
          return j;
    
        std::swap(v[i], v[j]);
      }
    }
    
    void quicksort(std::vector<int>& v, int ileft, int iright)
    {
      if (ileft < iright)
      {
        int j, ipivot =  v[(ileft + iright) / 2]; //v[ileft]; // v[iright];  
    
        j = partition(v, ileft, iright, ipivot);
        quicksort(v, ileft, j);
        quicksort(v, j+1, iright);
      }
    }
    
    int main()
    {
      std::vector<int> v = {5,2,-9};
    
      for (int i = 0; i < v.size(); i++)
        std::cout << v[i] << std::endl;
    
      quicksort(v, 0, v.size() - 1);
    
      std::cout << std::endl;
    
      for (int i = 0; i < v.size(); i++)
        std::cout << v[i] << std::endl;
    
      return 0;
    }
    

    Klar, der obige Code funktioniert und ich bin Hoare's Algorithmus mehrmals fürs Verstandnis durchgegangen, jedoch frage ich mich, ob es keine effizientere Version gibt. Oder: Eigentlich sollte man doch keine Endlosschleifen nutzen, oder?

    Dann bin ich auf folgende Version gestoßen (http://www.algolist.net/Algorithms/Sorting/Quicksort):

    void quicksort(std::vector<int>& v, int ileft, int iright)
    {
      int j=iright, i=ileft, ipivot = v[ileft]; //  //v[(ileft + iright) / 2]; 
    
      /*partition*/
      while (i <= j)
      {
        while (v[i] < ipivot)
          i++;
    
        while (v[j] > ipivot)
          j--;
    
        if (i <= j)
        {
          std::swap(v[i], v[j]); //swap
          i++;
          j--;
        }
      }
    
      /*quicksort*/
      if (ileft < j)
        quicksort(v, ileft, j);
    
      if (i < iright)
        quicksort(v, i, iright);
    }
    

    Bei dieser Version wird "partition" so lange ausgeführt, bis i<j ist. Jedoch bei v = {5,2,-9} wird das Array zwar sortiert, jedoch wird das Programm nie beendet, denn i=-1 und j=1, wenn ich obige Version auf die ganz oben genannten Unterprogramme übertrage.

    Was meint ihr dazu?

    Gruß
    C_boy



  • C_Boy schrieb:

    Oder: Eigentlich sollte man doch keine Endlosschleifen nutzen, oder?

    Begründung?
    Wenn man Andrei Alexandrescu fragt, beginnt jeder effiziente Algorithmus damit, dass man zunächst mal eine Endlosschleife schreibt. Siehe: https://www.youtube.com/watch?v=o4-CwDo2zpg&t=1080 😉

    Edit:

    C_Boy schrieb:

    Bei dieser Version wird "partition" so lange ausgeführt, bis i<j ist. Jedoch bei v = {5,2,-9} wird das Array zwar sortiert, jedoch wird das Programm nie beendet, denn i=-1 und j=1, wenn ich obige Version auf die ganz oben genannten Unterprogramme übertrage.

    Sorry, verstehe ich nicht. Kann ich auch nicht nachvollziehen. Wie soll i auch negativ werden, wenn du nur ++ verwendest?



  • Danke, das Video ist echt gut!

    Mir ist halt immer als Programmier-Anfänger gesagt worden, break, goto, labels und eben Endlosschleifen zu meiden. Da das Programm "sauber" ohne Unterbrechungen von Vorne bis Hinten durchlaufen sollte. Aber manchmal gibt es doch bestimmte Zwecke, wo obiges durchaus Sinn macht?

    Zu meinem Programm:
    Sorry, ich habe mich da vertan. Da ist j=0 und i=2. Jedoch gibt mir partition() nur eben j zurück. Und folgende Quicksort-Rekursion schlägt dann fehl, da ich davon ausgegangen bin, dass i=j+1 sein müsste laut dem Bild hier am Anfang: http://www.algolist.net/Algorithms/Sorting/Quicksort

    (Und da ich mich an die vorgegebenen Prototypen im Startbeitrag halten sollte, kann ich auch den Wert von i nicht wirklich klug im quicksort() bekannt machen)

    Zusammengefasst: Wenn ich das Programm(Das zweiter im Startpost nur eben modular) mit dem Debugger durchgehe, dann bleibt dieses einfach in endlos in der Rekursion hängen, also es wird immer wieder aufgerufen, wobei das array v schon längst sortiert wurde und nach dem Sortieren ist j=0 und i=2.

    void quicksort(std::vector<int>& v, int ileft, int iright)
    {
      int j, ipivot =  v[(ileft + iright) / 2]; //v[ileft]; // // v[iright];  //v[(ileft + iright) / 2]; //
    
      j = partition(v, ileft, iright, ipivot);
    
      if (ileft < j)
        quicksort(v, ileft, j);
    
      if (j+1 < iright)
        quicksort(v, j+1, iright);
    }
    


  • C_Boy schrieb:

    Mir ist halt immer als Programmier-Anfänger gesagt worden, break, goto, labels und eben Endlosschleifen zu meiden.

    Das ist ja auch in Ordnung (zumindest bzgl. goto und labels).
    Die Effizenz des Codes von Alexandrescu entscheidet darüber, ob man ein Kraftwerk mehr oder weniger benötigt; dein Code sollte in erster Linie lesbar und verständlich sein.


Log in to reply