Probleme mit Quicksort/Median Algorithmus



  • Hallo zusammen,☺
    ich bin gerade dabei ein Programm zu schreiben was Zahlenfolgen aus einer Textdatei sortieren soll. Es soll der Median bestimmt werden, die Zahlenfolge mit QuickSort sortiert werden, und in einer weiteren Methode der Quicksort mit der "vorgeschalteten" Medianbestimmung ausgeführt werden.
    Also anstatt dass das kte Element (l+r)/2 ist, soll der Median verwendet werden.

    Die Algorithmen sollen auch nochmal auf die bereits sortierten Folgen angewendet werden.
    Ich bin eigentlich fertig, bis auf einen Fehler der mich wirklich wahnsinnig macht und schon seit ewigkeiten beschäftigt.
    Die kombinierten QuickSort/Median Methode funktioniert nicht. Ich kann nur Zahlenfolgen bis 10 sortieren, danach schleichen sich erste Fehler ein,
    und so ab 14 kommt totaler Quatsch dabei raus.

    Ich hoffe irgendjemand ist schlauer als ich und kann mir sagen wo der Fehler liegt😀 Ich bin mit meinem Latein am Ende so langsam.😓

    Für andere Verbesserungsvorschläge bin ich natürlich auch offen.

    Das ist der Code:
    Falls jemand den Code ausführen möchte: download
    (ziemlich groß wegen den riesigen Zahlenfolgen)

    Darstellung.h

    
    #ifndef DARSTELLUNG_H
    #define DARSTELLUNG_H
    
    #include "Sequenz.h"
    #include "Median.h"
    #include "QSMedian.h"
    #include "QuickSort.h"
    #include <iomanip>
    
    class Darstellung {
        
    private:
      string dateiPfade[50];
    public:
    
        //Konstruktoren****Fettschrift****
        Darstellung();
        virtual ~Darstellung();
    
        //Methoden
        void print();
        inline static void printLine(uint breite);
        inline static void printUeberschrift(const string& eingabe);
        void printSort(bool saveSort, Sequenz* sequenz);
    
    };
    
    #endif /* DARSTELLUNG_H */
    
    
    

    Darstellung.cpp

    
    
    #include "Darstellung.h"
    
    Darstellung::Darstellung() {
    
        uint index = 0;
    
        for (uint i = 1; i < 4; i++) {
            string ordner = "TestSuite" + to_string(i);
            for (uint j = 1; j < 11; j++) {
    
                string datBezei;
                if (i == 1) datBezei = "_no_dups.txt";
                if (i == 2) datBezei = "_wc.txt";
                if (i == 3) datBezei = "_random.txt";
                if (i == 3 && j ==7){
                    continue;;
                }
                string temp = ordner + "\\sample" + to_string(j) + datBezei;
                dateiPfade[index] = temp;
                index++;
            }
        }
    
    //    uint arrSize = sizeof (dateiPfade) / sizeof (dateiPfade[0]);
    //    for (uint i = 0; i < arrSize; i++) {
    //        cout << "--" << dateiPfade[i] << endl;
    //    }
    
    
    
    }
    
    
    Darstellung::~Darstellung() {
    }
    
    
    void Darstellung::print() {
    
    //    bool printFlag = true;
    
        Sequenz *sequenz;
    
        Median median; QuickSort quickSort; QSMedian qsmedian;
        
        bool saveSort= false; 
        while (true) {
    
            cout << "M: Median" << endl << "Q: QuickSort" << endl << "S: QuickSort/Median" << endl;
    
            char input;
            cin >> input;
            switch (input) {
                case 'M':
                {
    
                    printUeberschrift("median");
                    sequenz = &median;
    
                    for (uint i = 0; i < 10; i++) {
    
                        sequenz ->leseZahlenfolge(dateiPfade[i]);
    
                        pair<uint, uint> impPair2 = sequenz ->impl(sequenz->get_zf(), sequenz->get_n(),1);
                        uint median2 = sequenz->get_zf()[impPair2.first];
    
                        const string T = "|  ";
                        cout << left << setw(40) << (T + dateiPfade[i]);
                        cout << left << setw(20) << (T + to_string(sequenz->get_n()));
                        cout << left << setw(30) << (T + to_string(impPair2.second));
                        cout << left << setw(30) << (T + to_string(median2));
                        cout << T << endl;
    
    
                    }
                    printLine(119);
                    break;
                }
                case 'Q':
                
    
                    printUeberschrift("sort");
                    sequenz = &quickSort;
                               
                    printSort(saveSort,sequenz);
                    saveSort=true;
                    cout << setw (80) << internal << "Zuvor sortierte Zahlenfolgen: " << endl;      
                    printSort(saveSort,sequenz);
                                
    
                    break;
                
                case 'S':
                    printUeberschrift("sort");
                    sequenz = &qsmedian;
                   
                                              
                    printSort(saveSort,sequenz);
                    saveSort=true;
                    cout << setw (80) << internal << "Zuvor sortierte Zahlenfolgen: " << endl;               
                    printSort(saveSort,sequenz);
                    
                    break;
                default:
                    cout << "Error" << endl;
                    break;
            }
    
        }
    }
    
    void Darstellung::printSort(bool saveSort, Sequenz* sequenz){
       
        
        bool istQSMedian  = dynamic_cast<QSMedian*>(sequenz) ?  1:0;
    
        for (uint i = 0; i < 28; i++) {
        
        if (saveSort && !istQSMedian) sequenz ->leseZahlenfolge("saveQuickSort\\" + dateiPfade[i]);
        else if (saveSort && istQSMedian) sequenz ->leseZahlenfolge("saveQSMedian\\" + dateiPfade[i]);
        else sequenz ->leseZahlenfolge(dateiPfade[i]);
    
        string isSorted = (sequenz->isSorted() ? "sortiert" : "nicht sortiert");
        
        //Folgen aus TestSuite2 ignorieren
    //    if (dateiPfade[i].find("TestSuite2") != std::string::npos) continue;
        
                        pair<uint, uint> impPair = sequenz ->impl(sequenz->get_zf(), 0, sequenz->get_n() - 1);
    
                        //Ausgabe einer Zeile
                        const string T = "|  ";
                        cout << left << setw(40) << (T + dateiPfade[i]);
                        cout << left << setw(20) << (T + to_string(sequenz->get_n()));
                        cout << left << setw(30) << (T + to_string(impPair.first));
                        cout << left << setw(30) << (T + to_string(impPair.second));
                        cout << left << setw(20) << (T + isSorted);
                        cout << T << endl;
    
    //                              if (printFlag) sequenz ->printZahlenfolge();
                        if (!saveSort && istQSMedian) sequenz ->saveZahlenfolge("saveQSMedian\\" + dateiPfade[i]);
                        else if (!saveSort && !istQSMedian) sequenz ->saveZahlenfolge("saveQuickSort\\" + dateiPfade[i]);
    }
        printLine(139);
    }
    
    
    void Darstellung::printLine(uint breite) {
        cout << "|" << string(breite, '_') << "|" << endl;
    }
    
    void Darstellung::printUeberschrift(const string& eingabe) {
    
        uint breite = eingabe == "sort" ? 139 : 119;
        printLine(breite);
        if (eingabe == "sort") {
            cout << left << setw(40) << "|  Dateiname";
            cout << left << setw(20) << "|  Anzahl Elemente";
            cout << left << setw(30) << "|  Vergangene Zeit: [ms]";
            cout << left << setw(30) << "|  Vertauschungen";
            cout << left << setw(20) << "| Folge sortiert?";
            cout << "|" << endl;
        } else {
            cout << left << setw(40) << "|  Dateiname";
            cout << left << setw(20) << "|  Anzahl Elemente";
            cout << left << setw(30) << "|  Vergangene Zeit: [ms]";
            cout << left << setw(30) << "|  pivotelement";
            cout << "|" << endl;
        }
    
    
        printLine(breite);
    }
    
    
    

    Median.h

    
    #ifndef MEDIAN_H
    #define MEDIAN_H
    
    using namespace std;
    
    #include "Sequenz.h"
    
    struct Median : public Sequenz {
        Median();
        virtual ~Median();
    
        //Methoden
        pair<uint, uint> impl(int zahlenFolge[], int n, int k);
    
    };
    
    #endif /* MEDIAN_H */
    
    
    

    Median.cpp

    
    #include "Median.h"
    
    Median::Median() {
    }
    
    Median::~Median() {
        delete[] zahlenFolge;
        zahlenFolge = NULL;
    }
    
    pair<uint, uint> Median::impl(int zahlenFolge[], int r, int l) {
         
        k = (l + r) / 2 + ((l + r) % 2 > 0 ? 1 : 0); //aufrunden
       
        int pivot;
        
        clock_t start = clock();
        
        while (true) {
            pivot = Sequenz::split(zahlenFolge, l,r);
            pivot = pivot - l + 1;
    
            /* Index relativ zum Bereichsanfang l */
            if (pivot < k) { /* k im oberen Teilbereich */
                l = l + pivot; /* r bleibt, neuer Bereich l...r */
                k = k - pivot; /* neues k, hiermit weitermachen */
            } else if (pivot == k) { /* jetzt Volltreffer, d.h. p == k: */
    
                clock_t end = clock();
                return make_pair((l - 1 + k), (end - start)); /* Index relativ zum Feldanfang */
                
            } else
                /* beachte: alle unterhalb von p sind kleiner-gleich */
                /* dieses sind p-1 viele */
                r = l + pivot - 2; /* l und k bleiben unveraendert*/
        }
    }
    
    
    

    QSMedian.cpp

    
    #ifndef QSMEDIAN_H
    #define QSMEDIAN_H
    
    using namespace std;
    #include"Sequenz.h"
    #include"Median.h"
    
    struct QSMedian : public Sequenz {
        
        Median tempMed;
    
        //Konstruktoren
        QSMedian();
        virtual ~QSMedian();
    
        //Methoden
        int split(int zahlenFolge[], int l, int r);
    
    };
    
    #endif /* QSMEDIAN_H */
    
    
    

    QSMedian.h

    
    #include "QSMedian.h"
    
    QSMedian::QSMedian() {
    }
    
    QSMedian::~QSMedian() {
        delete[] zahlenFolge;
        zahlenFolge = NULL;
    }
    
    int QSMedian::split(int zahlenFolge[], int l, int r) {
       
    
        uint pivot = pivot = this->tempMed.impl(zahlenFolge, r,l).first-l;
       
        if (anzEle<3) pivot = r;
    
    //    cout << "NORMAL" << "  PIVOT: " << pivot << "  L:  " << l << "  R.  " << r << endl;
        
        swap(zahlenFolge, pivot, l);
        pivot = l;
    
    
        for (uint i = l + 1; i <= r; i++) 
            if (zahlenFolge[i] <= zahlenFolge[pivot]) {
                swap(zahlenFolge, i, (pivot + 1));
                swap(zahlenFolge, pivot, (pivot + 1));
                pivot += 1;
            }
         
        
        return pivot;
        
    }
    
    
    

    Quicksort.h

    
    #ifndef QUICKSORT_H
    #define QUICKSORT_H
    
    using namespace std;
    #include "Sequenz.h"
    #include "Median.h"
    
    struct QuickSort : public Sequenz {
        //Konstruktoren
        QuickSort();
        virtual ~QuickSort();
    
    };
    
    #endif /* QUICKSORT_H */
    
    
    

    Sequenz.h

    
    #ifndef SEQUENZ_H
    #define SEQUENZ_H
    
    typedef unsigned int uint;
    using namespace std;
    
    #include <fstream>
    #include <iostream>
    #include <string>
    #include <cstdlib>
    #include <ctime>
    #include <time.h>
    #include <vector>
    #include <cmath>
    #include <stdexcept>
    
    struct Sequenz {
      
        //Konstruktoren
        Sequenz();
        virtual ~Sequenz();
    
        //Methoden
        void leseZahlenfolge(const string& dateiName);
        void printZahlenfolge();
        void saveZahlenfolge(const string&);
        virtual int split(int zahlenFolge[], int l, int r);
        void swap(int zahlenFolge[], int l, int r);
        virtual pair<uint, uint> impl(int zahlenFolge[], int l, int r);
        bool isSorted();
    
    
        //Getter-Methoden
        uint get_n() const;
        uint get_k() const;
        int *get_zf() const;
    
    
    
    protected:
        int* zahlenFolge;
        uint n;
        uint k;
        
    
    
    };
    
    #endif /* SEQUENZ_H */
    
    
    

    Sequenz.cpp

    #include "Sequenz.h"
    
    Sequenz::Sequenz() {
    }
    
    Sequenz::~Sequenz() {
        delete[] zahlenFolge;
        zahlenFolge = NULL;
    }
    
    void Sequenz::leseZahlenfolge(const string& dateiName) {
    
        ifstream inputFile(dateiName.c_str());
        if (inputFile.is_open()) {
    
            //Sequenzlaenge einlesen
            string nTemp;
            getline(inputFile, nTemp);
            this->n = stoi(nTemp);
            zahlenFolge = new int [n];
    
            string line;
            for (uint i = 0; i < n; i++) {
                getline(inputFile, line);
                zahlenFolge[i] = stoi(line);
            }
    
            inputFile.close();
            
        } else cout << "Datei nicht gefunden!" << endl;
    
    }
    
    void Sequenz::printZahlenfolge() {
        cout << endl;
        for (uint i = 0; i < n; i++) cout << zahlenFolge[i] << " ";
        cout << endl;
    }
    
    void Sequenz::saveZahlenfolge(const string& datName) {
        fstream myfile;
        myfile.open(datName.c_str(), fstream::out);
        myfile << n << "\r\n";
    
        for (uint i = 0; i < n; i++) 
            myfile << zahlenFolge[i] << "\r\n";
        
        myfile.close();
    }
    
    void Sequenz::swap(int zahlenFolge[], int l, int r) {
    
        int temp = zahlenFolge[l];
        zahlenFolge[l] = zahlenFolge[r];
        zahlenFolge[r] = temp;
    }
    
    pair<uint, uint> Sequenz::impl(int zahlenFolge[], int l, int r) {
       
        int stack_l[static_cast<int> (log2(n))], stack_r[static_cast<int> (log2(n))];
        int k = 0; /* Anzahl der gespeicherten Bereiche */ 
        uint vertauschungen = 0;
        
        clock_t start = clock();
        
        while ((l < r) || (k > 0)) { /* noch etwas zu sortieren? */
            if (!(l < r)) { /* also k>0 -> gespeicherten Bereich verarbeiten */
                l = stack_l[k];
                r = stack_r[k];
                k--;
            }
            
            
            int s = split(zahlenFolge, l, r); /* Aufteilung bei a[(l+r)/2] */
    
            if ((r - l) >= 2) { /* mindestens drei Elemente */
                if ((s - l) > (r - s)) { /* grösseren -> linken Bereich merken */
                    k = k + 1;
                    stack_l[k] = l;
                    stack_r[k] = s - 1;
                    l = s + 1; /* rechten Bereich sofort verarbeiten */
                } else { /* rechten Bereich merken */
                    k = k + 1;
                    stack_l[k] = s + 1;
                    stack_r[k] = r;
                    r = s - 1; /* linken Bereich sofort verarbeiten */
                }
            } else
                l = r; /* weniger als 3 Elemente: Folge nach split() sortiert! */
            vertauschungen++;
    
        }
        clock_t end = clock();
    
        return make_pair((end - start), vertauschungen);
    }
    
    int Sequenz::split(int zahlenFolge[], int l, int r) {
        
        //Pivotelement aufrunden
        int pivot = (l + r) / 2 + ((l + r) % 2 > 0 ? 1 : 0);
        
    //    cout << "NORMAL" << "  PIVOT: " << pivot << "  L:  " << l << "  R.  " << r << endl;
        
        swap(zahlenFolge, pivot, l);
        pivot = l;
    
    
        for (uint i = l + 1; i <= r; i++) {
            if (zahlenFolge[i] <= zahlenFolge[pivot]) {
                swap(zahlenFolge, i, (pivot + 1));
                swap(zahlenFolge, pivot, (pivot + 1));
                pivot += 1;
            }
        }
    
        return pivot;
    }
    
    bool Sequenz::isSorted() {
        for (uint i = 0; i < n-1; i++)
            if (zahlenFolge[i] > zahlenFolge[i + 1]) return false;
        return true;
    }
    
    //Getter-Methoden
    uint Sequenz::get_n() const {
        return n;
    }
    
    uint Sequenz::get_k() const {
        return k;
    }
    
    int* Sequenz::get_zf() const {
        return zahlenFolge;
    }
    
    

    Main.cpp

    using namespace std;
    
    #include "Sequenz.h"
    #include "Median.h"
    #include "QuickSort.h"
    #include "QSMedian.h"
    #include "Darstellung.h"
    
    int main(int argc, char** argv) {
    
        
        Darstellung d;
        d.print();
      
    
        //    //Zahlenfolge ausgeben?
        //    bool printFlag=false;
        //    cout << "Zahlenfolge ausgeben? J oder N" << endl;
        //    char inputPrint;
        //    cin >> inputPrint;
        //    if (inputPrint == 'J') printFlag= true;
        //    
        //    cout << "Bitte Dateinamen eingeben" << endl;
        //    string dateiName;
        //    cin >> dateiName;
        //
    
    
    
        return 0;
    }
    
    
    


  • Was meinst du mit Methode und vorgeschalteter Medianbestimmung? Vielleicht machst du mal ein Zahlenbeispiel was für Ergebnisse du haben willst.
    Ich hab mir den Code auch nicht angeschaut. Der ist zu lang und da stehen Dinge drin, die für dein Problem irrelevant sind. Das muss kompakter und konkreter werden.



  • Ja ich verstehe dass es schwierig ist, sich da hineinzuversetzen.
    Das Problem tritt auf in der Datei QSMedian.cpp in Zeile 15. Das ganze drumherum ist eigentlich Nebensache und es funktioniert ja auch.

    Der Quicksort funktioniert ja so, dass die Folge in Teilfolgen gespaltet wird und die Folgen sortiert werden.
    Die Aufspaltung findet an dem Element statt, welches an dem Index in der Mitte steht. Die zugehörige Zahl wird an die richtige Position im Array verschoben und an dieser Stelle wird die Folge dann aufgespaltet.

    ABBILDUNG QUICKSORT

    Im besten Fall wird die Folge genau in der Mitte aufgespaltet.
    siehe "pair<uint, uint> Sequenz::impl(int zahlenFolge[], int l, int r) "

    Deshalb der Ansatz den Median quasi "davorzuschalten" damit immer an dem Element, welches in der Mitte der Folge steht, gespaltet wird.

    Ich hoffe ich habe das einigermaßen verständlich beschrieben☺

    @out sagte in Probleme mit Quicksort/Median Algorithmus:
    Vielleicht machst du mal ein Zahlenbeispiel was für Ergebnisse du haben willst.

    Es stehen Zahlenfolgen in einer Datei (Zeilenweise, erste Zeile gibt die Anzahl der Zahlen in der Folge an). Und das Ergebnis ist wieder eine Datei, diesmal mit der sortierten Zahlenfolge.

    Die benötigte Zeit und weitere Daten sollen in der Konsole ausgegeben werden



  • Ok, das Pivot Element soll der Median sein. Wieso muss es Quicksort sein, was ist mit std::sort? Wie du siehst, kostet dein Weg mehr Zeit, verursacht Probleme, und das führt zu noch mehr Zeitaufwand.



  • Ich habe oben noch einmal einen Link eingefügt. Das Bild erklärt eigentlich alles.

    @out sagte in Probleme mit Quicksort/Median Algorithmus:

    Ok, das Pivot Element soll der Median sein. Wieso muss es Quicksort sein, was ist mit std::sort? Wie du siehst, kostet dein Weg mehr Zeit, verursacht Probleme, und das führt zu noch mehr Zeitaufwand.

    Ich bin Student und wir sollen das Programm mit diesem Algorithmus schreiben. Sonst würde ich den Algorithmus auch nicht selbst schreiben, wenn ich es nicht muss😅



  • Aha, ok. Kann generell nicht schaden, selbst einmal eine Quicksort geschrieben zu haben 🙂

    Dann eine komplett andere Frage: wie lernt ihr denn Vererbung? Wenn ich mir das hier angucke:

    struct Median : public Sequenz {
    

    Dann kommen schon Zweifel auf. Denn Vererbung bedeutet eine "ist-ein"-Beziehung. Ein Median ist eine Sequenz? Jeden Median kann man auch als Sequenz verwenden? Das hört sich irgendwie falsch an.

    Und was ist ein QSMedian? Irgendwie erscheint mir das ganze Design merkwürdig.

    Und weitere Frage: dürft ihr std::vector nicht verwenden?! Eine eigene Sequenz-Klasse? Warum wird std::vector nicht gelehrt?!!!! ARGH!



  • QSMedian steht wohl für "Quicksort mit Median".

    @Philipp2706: Hast du denn keinen Debugger (bei deiner IDE)? Oder kannst du nicht nach jedem Sortiervorgang die Liste (zum Test) ausgeben?

    Aber noch ein paar generelle Programmierhinweise:

    • Niemals using namespace std; in Headerdateien!
    • Nur die Headerdateien einbinden, die auch wirklich benötigt werden (Negativbeispiele: Darstellung.h, Sequenz.h)
    • Der Destruktor ~QSMedian ist falsch (implementiert) - das Löschen macht doch schon die Basisklasse Sequenz.


  • @wob sagte in Probleme mit Quicksort/Median Algorithmus:

    Aha, ok. Kann generell nicht schaden, selbst einmal eine Quicksort geschrieben zu haben
    Dann eine komplett andere Frage: wie lernt ihr denn Vererbung? Wenn ich mir das hier angucke:
    struct Median : public Sequenz {

    Meine Überlegung war folgende:
    Ich habe eine Sequenz (also Zahlenfolge die sortiert werden soll), und das soll auf verschiedenen Arten geschehen.
    Also wenn ich mich für den einfachen Quicksort entscheide, soll die Sequenz mit dem einfachen Quicksort sortiert werden. Die Sequenz ist dann also ein QuickSort.
    Wenn ich „QSMedian“ auswähle, wird die Sequenz mit dem kombinierten Quicksort/Median ausgeführt. Die Sequenz ist dann also ein QSMedian und verwendet die speziellen, überladenen Methoden.

    @wob sagte in Probleme mit Quicksort/Median Algorithmus:

    Und weitere Frage: dürft ihr std::vector nicht verwenden?!

    Vector sollen wir nicht benutzen, sondern alles im c-Style mit Arrays.

    @Th69 sagte in Probleme mit Quicksort/Median Algorithmus:

    Hast du denn keinen Debugger (bei deiner IDE)? Oder kannst du nicht nach jedem Sortiervorgang die Liste (zum Test) ausgeben?

    Anstatt einen Debugger zu benutzen, habe ich mit cout eine Zeile ausgegeben wo die Relevanten Daten stehen. Also Bereichsgrenzen und PivotElement.

    //    cout << "NORMAL" << "  PIVOT: " << pivot << "  L:  " << l << "  R.  " << r << endl;
    

    So konnte ich genau sehen was er macht. Ich hab das Verhalten allerdings nicht verstanden.
    Jede Zahlenfolge die eingelesen wird, wird nach der Sortierung in eine neue Datei geschrieben. Beim Quicksort funktioniert alles, der Median funktioniert auch. Nur die kombinierte Version „QSMedian“ funktioniert nicht.

    Diese Zeile

    uint pivot = pivot = this->tempMed.impl(zahlenFolge, r,l).first-l;
    

    in

    int QSMedian::split(int zahlenFolge[], int l, int r)
    

    ist das Problem

    Wenn ich das Pivotelement auf die ”normale” Weise bestimme, also die Problemzeile durch:

    int pivot = (l + r) / 2;
    

    beziehungsweise aufgerundet.

    int pivot = (l + r) / 2 + ((l + r) % 2 > 0 ? 1 : 0);
    

    ersetze, funktioniert alles.

    Es werden Zahlenfolgen bis 10 Elemente fehlerfrei sortiert, bei mehr Elementen kommen die ersten Fehler und größere Zahlenfolgen funktionieren garnicht.



  • @Philipp2706 sagte in Probleme mit Quicksort/Median Algorithmus:

    Ich habe eine Sequenz (also Zahlenfolge die sortiert werden soll), und das soll auf verschiedenen Arten geschehen.
    Also wenn ich mich für den einfachen Quicksort entscheide, soll die Sequenz mit dem einfachen Quicksort sortiert werden. Die Sequenz ist dann also ein QuickSort.

    Ich habe ein Auto (also einen Kasten auf vier Rädern, der gewaschen werden soll), und das soll auf verschiedenen Arten geschehen.
    Also wenn ich mich für die einfache Waschanlagenwäsche entscheide, soll das Auto mit der einfachen Waschanlagenwäsche gewaschen werden. Das Auto ist dann also eine Waschanlagenwäsche.

    Du siehst, dass da etwas nicht stimmt?



  • @manni66 sagte in Probleme mit Quicksort/Median Algorithmus:

    @Philipp2706 sagte in Probleme mit Quicksort/Median Algorithmus:

    Ich habe eine Sequenz (also Zahlenfolge die sortiert werden soll), und das soll auf verschiedenen Arten geschehen.
    Also wenn ich mich für den einfachen Quicksort entscheide, soll die Sequenz mit dem einfachen Quicksort sortiert werden. Die Sequenz ist dann also ein QuickSort.

    Ich habe ein Auto (also einen Kasten auf vier Rädern, der gewaschen werden soll), und das soll auf verschiedenen Arten geschehen.
    Also wenn ich mich für die einfache Waschanlagenwäsche entscheide, soll das Auto mit der einfachen Waschanlagenwäsche gewaschen werden. Das Auto ist dann also eine Waschanlagenwäsche.
    Du siehst, dass da etwas nicht stimmt?

    Okay dann anders formuliert. Ich habe eine Sequenz.
    Wenn ich mich für Quicksort entscheide, ist es eine mit QuickSort sortierte Sequenz.
    Wenn ich mich für Quicksort mit Median entscheide ist es eine mit Quicksort/Median sortierte Sequenz.

    Oder in deinem Fall wäre es ein Auto dass mit der einfachen/bzw. anderen Waschanlagenwäsche gewaschen wurde.



  • @Philipp2706 sagte in Probleme mit Quicksort/Median Algorithmus:

    Wenn ich mich für Quicksort entscheide, ist es eine mit QuickSort sortierte Sequenz.

    Ja, es ist aber eben kein QuickSort. Insbesondere lässt sich die Sequenz nicht von einer mit einem anderen Algorithmus sortierten unterscheiden.



  • @manni66 sagte in Probleme mit Quicksort/Median Algorithmus:

    @Philipp2706 sagte in Probleme mit Quicksort/Median Algorithmus:

    Wenn ich mich für Quicksort entscheide, ist es eine mit QuickSort sortierte Sequenz.

    Ja, es ist aber eben kein QuickSort. Insbesondere lässt sich die Sequenz nicht von einer mit einem anderen Algorithmus sortierten unterscheiden.

    Wäre es denn in Ordnung wenn ich die Klassen QuickSort und QSMedian in sowas wie QuickSortSequenz und QSMedianSequenz umbenenne?

    Ich habe in der Elternklasse Methoden die alle abgeleiteten Klassen benötigen. Zum Beispiel zum Einlesen und Speichern der Folge.

    In den Unterklassen implementiere ich dann falls nötig die speziellen Methoden.

    Die Methode Split unterscheidet sich zum Beispiel beim QSMedian, daher habe ich sie in der Klasse implementiert und sie überlädt die Elternmethode.



  • So hab mir den Code mal in Xcode kopiert und kurz drübergeschaut. Meine Empfehlung: Fang von vorne an, da passt vieles nicht.
    Wieso musst du alles in Klassen hauen?
    Ein Median ist keine Sequenz. Ein Median ist eine Funktion, die ich auf eine Zahlenfolge anwende und dann eine sortierte Sequenz erhalte.

    Im Endeffekt brauchst du doch 1 Funktion die den Median berechnet. Dann brauchst du eine Funktion die Quicksort macht. Diesen Funktionen übergibst du dein Array.



  • @Philipp2706 sagte in Probleme mit Quicksort/Median Algorithmus:

    Wäre es denn in Ordnung wenn ich die Klassen QuickSort und QSMedian in sowas wie QuickSortSequenz und QSMedianSequenz umbenenne?

    Nein. Schau dir an, wie es die Standardalgoithmen machen:

    std::vector<int> v = { 3, 6, 2, 9 };
    
    std::sort( begin(v), end(v) );
    
    std::stable_sort( begin(v), end(v) );
    

    Der Container (bei dir die Sequenz) wird den verschiedenn Algorithmen übergeben. begin/end beschreiben hier den Container, da könnte auch einfach v stehen.



  • Ok danke erstmal😊
    ich werde die Änderungen umsetzen und euch davon berichten



  • Also das wäre meine Lösung für die Aufgabe. Wirklich schneller finde ich es mit Median aber nicht, oder ich hab einen Fehler drin ?! (Ich hatte es testweise mit 5000 Zahlen probiert. Wegen der Übersicht gebe ich hier nur ein paar an...)

    #include <iostream>
    #include <chrono>
    using namespace std;
    
    class stopwatch
    {
        chrono::time_point<chrono::high_resolution_clock> last_;
    public:
        void start()
        {
            last_ = chrono::high_resolution_clock::now();
        }
        chrono::milliseconds::rep elapsed() const
        {
            auto t = chrono::high_resolution_clock::now();
            return chrono::duration_cast<chrono::microseconds>(t - last_).count();
        }
    };
    
    void print( int* numbers, int size )
    {
        for( auto i=0; i!=size; ++i )
            cout << numbers[i] << " ";
        cout << endl;
    }
    
    void swap( int* numbers, int i, int u )
    {
        auto tmp{ numbers[i] };
        numbers[i] = numbers[u];
        numbers[u] = tmp;
    }
    
    int median_of_the_three( int* numbers, int left, int right )
    {
        auto mid = (left + right) / 2;
        if( numbers[mid] < numbers[left] )
            swap( numbers[left], numbers[mid] );
        if( numbers[right] < numbers[left] )
            swap( numbers[left], numbers[right] );
        if( numbers[mid] < numbers[right] )
            swap( numbers[mid], numbers[right] );
        return numbers[right];
    }
    
    int partition( int* numbers, int left, int right, bool use_median_for_pivot )
    {
        auto pivot{ numbers[left] };
        if( use_median_for_pivot )
            pivot = median_of_the_three( numbers, left, right );
        
        auto i = left  -1;
        auto u = right +1;
        
        for(;;)
        {
            do
            {
                ++i;
            }while( numbers[i] < pivot );
            do
            {
                --u;
            }while( numbers[u] > pivot );
            
            if( i >= u )
                return u;
            swap( numbers, i, u );
        }
    }
    
    void quicksort( int* numbers, int left, int right, bool use_median_for_pivot )
    {
        if( left < right )
        {
            auto part_idx = partition( numbers, left, right, use_median_for_pivot );
            quicksort( numbers, left, part_idx, use_median_for_pivot );
            quicksort( numbers, part_idx +1, right, use_median_for_pivot );
        }
    }
    
    int main()
    {
        constexpr int size{ 26 };
        
        cout << "Starte Quicksort ohne Median:" << endl;
        stopwatch sw;
        sw.start();
        {
            int numbers[size]{57,58,18,99,61,99,65,89,20,49,67,33,42,79,64,83,3,71,12,21,65,85,73,57,5,84};
            //print( numbers, size );
            quicksort( numbers, 0, size-1, false );
            //print( numbers, size );
        }
        cout << "Zeit Quicksort ohne Median: " << sw.elapsed() << "us" << endl << endl;
        
        cout << "Starte Quicksort mit Median:" << endl;
        sw.start();
        {
            int numbers[size]{57,58,18,99,61,99,65,89,20,49,67,33,42,79,64,83,3,71,12,21,65,85,73,57,5,84};
            //print( numbers, size );
            quicksort( numbers, 0, size-1, true );
            //print( numbers, size );
        }
        cout << "Zeit Quicksort mit Median: " << sw.elapsed() << "us" << endl << endl;
    }
    
    


  • @out Man könnte auch nach der Partition eine Seite (den jeweils kleineren Part) rekursiv, die andere Seite iterativ lösen:

    void quickSort(...)
    {
    	while(left<right)
    	{
    		auto p=partition(numbers, left, right, use_median_for_pivot);
    		if(p-left<right-p) 
    		{
    			quickSort(numbers, left, p-1, use_median_for_pivot); 
    			left=p+1; 
    		}
    		else
    		{
    			quickSort(numbers, p+1, right, use_median_for_pivot); 
    			right=p-1; 
    		}
    	}
    }
    

    Man müsste mal messen, wieviel das wirklich bringt (jedoch N>>26).

    Hast du denn mal probiert, wie es aussieht. wenn die Daten teilweise vorsortiert bzw. komplett entgegengesetzt sortiert sind?



  • @out sagte in Probleme mit Quicksort/Median Algorithmus:

    Also das wäre meine Lösung für die Aufgabe. Wirklich schneller finde ich es mit Median aber nicht, oder ich hab einen Fehler drin ?!

    Ne das ist schon richtig so. Ich meine sogar dass diese Herangehensweise langsamer ist.

    @yahendrik sagte in Probleme mit Quicksort/Median Algorithmus:

    Hast du denn mal probiert, wie es aussieht. wenn die Daten teilweise vorsortiert bzw. komplett entgegengesetzt sortiert sind?

    Ne hab ich noch nicht aber wäre auch mal interessant.

    Ich glaube ich habe verstanden wo mein Problem lag . Ich arbeite gerade noch an der Umsetzung😌



  • @yahendrik sagte in Probleme mit Quicksort/Median Algorithmus:

    Hast du denn mal probiert, wie es aussieht. wenn die Daten teilweise vorsortiert bzw. komplett entgegengesetzt sortiert sind?

    #include <iostream>
    #include <chrono>
    #include <random>
    #include <algorithm>
    #include <functional>
    using namespace std;
    
    class stopwatch
    {
        chrono::time_point<chrono::high_resolution_clock> last_;
    public:
        void start()
        {
            last_ = chrono::high_resolution_clock::now();
        }
        chrono::milliseconds::rep elapsed() const
        {
            auto t = chrono::high_resolution_clock::now();
            return chrono::duration_cast<chrono::milliseconds>(t - last_).count();
        }
    };
    
    void print( int* numbers, int size )
    {
        for( auto i=0; i!=size; ++i )
            cout << numbers[i] << " ";
        cout << endl;
    }
    
    void swap( int* numbers, int i, int u )
    {
        auto tmp{ numbers[i] };
        numbers[i] = numbers[u];
        numbers[u] = tmp;
    }
    
    int median_of_the_three( int* numbers, int left, int right )
    {
        auto mid = (left + right) / 2;
        if( numbers[mid] < numbers[left] )
            swap( numbers[left], numbers[mid] );
        if( numbers[right] < numbers[left] )
            swap( numbers[left], numbers[right] );
        if( numbers[mid] < numbers[right] )
            swap( numbers[mid], numbers[right] );
        return numbers[right];
    }
    
    int partition( int* numbers, int left, int right, bool use_median_for_pivot )
    {
        auto pivot{ numbers[left] };
        if( use_median_for_pivot )
            pivot = median_of_the_three( numbers, left, right );
        
        auto i = left  -1;
        auto u = right +1;
        
        for(;;)
        {
            do
            {
                ++i;
            }while( numbers[i] < pivot );
            do
            {
                --u;
            }while( numbers[u] > pivot );
            
            if( i >= u )
                return u;
            swap( numbers, i, u );
        }
    }
    
    void quicksort( int* numbers, int left, int right, bool use_median_for_pivot )
    {
        if( left < right )
        {
            auto part_idx = partition( numbers, left, right, use_median_for_pivot );
            quicksort( numbers, left, part_idx, use_median_for_pivot );
            quicksort( numbers, part_idx +1, right, use_median_for_pivot );
        }
    }
    
    int main()
    {
        stopwatch sw{};
        mt19937 mt{ 1729 };
        uniform_int_distribution<int> dist{ 0, 100000 };
        constexpr int size{ 100000 }; // 100k
        
        {
            int* numbers = new int[size];
            generate( numbers, numbers+size, [&dist,&mt](){ return dist(mt); } );
            sort( numbers, numbers+size );
            cout << "Starte Quicksort ohne Median + vorsortiert: ";
            sw.start();
            quicksort( numbers, 0, size-1, false );
            cout << sw.elapsed() << "ms" << endl; // 1837ms --> Schön alle Schleifen durchrennen.
            delete[] numbers;
        }
        
        {
            int* numbers = new int[size];
            generate( numbers, numbers+size, [&dist,&mt](){ return dist(mt); } );
            sort( numbers, numbers+size, greater<int>() );
            cout << "Starte Quicksort ohne Median + absteigend vorsortiert: ";
            sw.start();
            quicksort( numbers, 0, size-1, false );
            cout << sw.elapsed() << "ms" << endl; // 1491ms --> Schön alle Schleifen durchrennen.
            delete[] numbers;
        }
        
        {
            int* numbers = new int[size];
            generate( numbers, numbers+size, [&dist,&mt](){ return dist(mt); } );
            cout << "Starte Quicksort ohne Median + unsortiert: ";
            sw.start();
            quicksort( numbers, 0, size-1, false );
            cout << sw.elapsed() << "ms" << endl; // 9ms --> Endlich werden Schleifen mal vorher abgebrochen.
            delete[] numbers;
        }
        
        cout << "================================================" << endl;
        
        {
            int* numbers = new int[size];
            generate( numbers, numbers+size, [&dist,&mt](){ return dist(mt); } );
            sort( numbers, numbers+size );
            cout << "Starte Quicksort mit Median + vorsortiert: ";
            sw.start();
            quicksort( numbers, 0, size-1, true );
            cout << sw.elapsed() << "ms" << endl; // 3ms --> Dank Median wird die zweite while Schleife viel, viel früher abgebrochen.
            delete[] numbers;
        }
        
        {
            int* numbers = new int[size];
            generate( numbers, numbers+size, [&dist,&mt](){ return dist(mt); } );
            sort( numbers, numbers+size, greater<int>() );
            cout << "Starte Quicksort mit Median + absteigend vorsortiert: ";
            sw.start();
            quicksort( numbers, 0, size-1, true );
            cout << sw.elapsed() << "ms" << endl; // 4ms --> Dank Median werden beide while Schleifen viel, viel früher abgebrochen. / Im Vergleich zu "Median + vorsortiert" brauchen die for und die erste while Schleife doppelt so lange.
            delete[] numbers;
        }
        
        {
            int* numbers = new int[size];
            generate( numbers, numbers+size, [&dist,&mt](){ return dist(mt); } );
            cout << "Starte Quicksort mit Median + unsortiert: ";
            sw.start();
            quicksort( numbers, 0, size-1, true );
            cout << sw.elapsed() << "ms" << endl; // 9ms --> Kaum ein Unterschied zu "ohne Median".
            delete[] numbers;
        }
    }
    
    
    

    Fazit:
    Quicksort ohne Median kannst du vergessen, wenn zu viel vorsortiert ist. Umso stärker die Zahlen sortiert vorliegen, desto stärker wirkt sich der Median aus.
    Wenn die Zahlen unsortiert sind, macht Median kaum einen Unterschied.



  • Und dann ist noch interessant, wie die Performance im Vergleich zu std::sort ist. 🙂


Anmelden zum Antworten