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?



  • @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. 🙂



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

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

    Fazit: std::sort haut alles weg. 😃

    #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::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 );
        }
    }
    
    constexpr int size{ 200000 }; // 100k
    
    struct unsorted { void operator()(){} };
    template<typename T, typename U >
    void sort_test( T sort_algo, U arrange_by, int* numbers, bool do_arrange, const string& what )
    {
        stopwatch sw{};
        mt19937 mt{ 1729 };
        uniform_int_distribution<int> dist{ 0, 200000 };
        generate( numbers, numbers+size, [&dist,&mt](){ return dist(mt); } );
        
        if( do_arrange )
        {
            arrange_by();
        }
        cout << what << " ==> ";
        sw.start();
        sort_algo();
        cout << sw.elapsed() << "us" << endl;
    }
    
    int main()
    {
        int* numbers = new int[size];
        
        auto vorsortieren_aufsteigend = [numbers] { sort(numbers, numbers+size); };
        auto vorsortieren_absteigend  = [numbers] { sort(numbers, numbers+size, greater<int>()); };
        
        auto sort_ = [numbers] { sort(numbers, numbers+size); };
        auto stable_sort_ = [numbers] { stable_sort(numbers, numbers+size); };
        auto quicksort_ohne_median = [numbers] { quicksort( numbers, 0, size-1, false );  };
        auto quicksort_mit_median  = [numbers] { quicksort( numbers, 0, size-1, true  );  };
        
        cout << endl << "============================================================" << endl;
        
        sort_test( sort_, vorsortieren_aufsteigend, numbers, true, "sort + vorsortieren_aufsteigend" );
        sort_test( stable_sort_, vorsortieren_aufsteigend, numbers, true, "stable_sort + vorsortieren_aufsteigend" );
        sort_test( quicksort_ohne_median, vorsortieren_aufsteigend, numbers, true, "quicksort_ohne_median + vorsortieren_aufsteigend" );
        sort_test( quicksort_mit_median, vorsortieren_aufsteigend, numbers, true, "quicksort_mit_median + vorsortieren_aufsteigend" );
        
        cout << endl << "============================================================" << endl;
        
        sort_test( sort_, vorsortieren_absteigend, numbers, true, "sort + vorsortieren_absteigend" );
        sort_test( stable_sort_, vorsortieren_absteigend, numbers, true, "stable_sort + vorsortieren_absteigend" );
        sort_test( quicksort_ohne_median, vorsortieren_absteigend, numbers, true, "quicksort_ohne_median + vorsortieren_absteigend" );
        sort_test( quicksort_mit_median, vorsortieren_absteigend, numbers, true, "quicksort_mit_median + vorsortieren_absteigend" );
        
        cout << endl << "============================================================" << endl;
        
        sort_test( sort_, unsorted{}, numbers, false, "sort + unsortiert" );
        sort_test( stable_sort_, unsorted{}, numbers, false, "stable_sort + unsortiert" );
        sort_test( quicksort_ohne_median, unsorted{}, numbers,false, "quicksort_ohne_median + unsortiert" );
        sort_test( quicksort_mit_median, unsorted{}, numbers, false, "quicksort_mit_median + unsortiert" );
        
        cout << endl << "============================================================" << endl;
        
        delete[] numbers;
    }
    
    


  • Vergessen, meine Messergebnisse zu posten (Mac mini (late 2012)):

    ============================================================
    sort + vorsortieren_aufsteigend ==> 383us
    stable_sort + vorsortieren_aufsteigend ==> 6124us
    quicksort_ohne_median + vorsortieren_aufsteigend ==> 7412477us
    quicksort_mit_median + vorsortieren_aufsteigend ==> 5931us

    ============================================================
    sort + vorsortieren_absteigend ==> 546us
    stable_sort + vorsortieren_absteigend ==> 7050us
    quicksort_ohne_median + vorsortieren_absteigend ==> 5846712us
    quicksort_mit_median + vorsortieren_absteigend ==> 7970us

    ============================================================
    sort + unsortiert ==> 12478us
    stable_sort + unsortiert ==> 17696us
    quicksort_ohne_median + unsortiert ==> 18679us
    quicksort_mit_median + unsortiert ==> 18483us

    ============================================================

    @wob: Was hast du für Ergebnisse?



  • std::sort verwendet den Introsort-Algorithmus, eine verbesserte Variante des Quicksort.



  • @Th69 Joa. Wusste auch, dass sort wohl am schnellsten ist, aber das es so viel schneller ist, hätte ich nicht gedacht.🙃



  • Ich habe erst jetzt verstanden das die Sequenz-Klasse als eine art Wrapperklasse für die Zahlenfolge dienen soll. Jetzt verstehe ich auch
    wieso das mit der Vererbung nicht hinhaut.
    Ich habe jetzt einiges geändert, aber das Programm ist leider immer noch an der selben Stelle fehlerhaft.

    @out
    Du hast oben ja den Median-Of-The-Three verwendet.
    Das soll so tatsächlich etwas schneller sein .
    Ich versuche die ganze zeit den "kompletten Median" der Zahlenfolge für den Quicksort zu finden, Und diese Methode müsste ein bisschen langsamer sein als der normale Quicksort. (Aber wir sollen es so machen)

    Ich könnte mir vorstellen dass das Problem darin besteht, dass der Median ja auch noch selbst wieder Splits durchführt.
    Diese müssen denke ich mal auf die normale Weise (also ohne vorherige Medianbestimmung) durchgeführt werden.
    Dafür habe ich die bool-variable "ausMedian" geschrieben. Damit die Split Methode weiß auf welche Art sie splitten soll.

    Aber leider ist es genauso wie vorher☹ ☹

    Download
    Das ist mein code:

    Darstellung.h

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

    Median.h

    
    #ifndef MEDIAN_H
    #define MEDIAN_H
    #include "Sequenz.h"
    
    
    #include <iostream>
    
    
    struct Median {
        Median();
        virtual ~Median();
    
        //Operatorueberladung
        pair<uint, uint> operator()(Sequenz* seq, uint l, int r);
    
    
    };
    
    #endif /* MEDIAN_H */
    
    
    

    QuickSort.h

    
    #ifndef QUICKSORT_H
    #define QUICKSORT_H
    
    
    #include "Sequenz.h"
    #include "Median.h"
    
    struct QuickSort {
        //Konstruktoren
        QuickSort();
        virtual ~QuickSort();
    
        pair<uint, uint> operator()(Sequenz* seq);
    
    };
    
    #endif /* QUICKSORT_H */
    
    
    

    Sequenz.h

    
    #ifndef SEQUENZ_H
    #define SEQUENZ_H
    using namespace std;
    //#include "Median.h"
    typedef unsigned int uint;
    
    
    #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&);
        int split(int l, int r, bool ausMedian);
        void swap(int l, int r);
        bool isSorted();
    
        //Operatorueberladung
        uint operator[](uint index);
    
        //Getter-Methoden
        uint get_n() const;
        string get_sortModus() const;
        //Setter-Methode
        void setSortModus(const string& moStr);
    
    protected:
        int* zahlenFolge;
        uint n;
        uint k;
    
    private:
        string sortModus;
        
    
    
    };
    
    #endif /* SEQUENZ_H */
    
    
    

    Darstellung.cpp

    
    #include "Darstellung.h"
    #include "QuickSort.h"
    
    Darstellung::Darstellung() {
    
        //Hier wird einfach nur eine Liste der Dateien erstellt
        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::auswahl() {
    
        //    bool printFlag = true;
    
    
        bool saveSort = false; //Bereits sortierte Zahlenfolgen sortieren
        while (true) {
    
            cout << "M: Median" << endl << "Q: QuickSort" << endl << "S: QuickSort/Median" << endl;
            Sequenz seq;
    
            char input;
            cin >> input;
            switch (input) {
                case 'M':
                {
                    printUeberschrift("median");
                    printMedian(&seq);
                    break;
                }
                case 'Q':
    
                    seq.setSortModus("QS");
                    printUeberschrift("sort");
                    printSort(saveSort, &seq);
    
                    //Die zuvor sortierten FOlgen ausgeben
                    saveSort = true;
                    cout << setw(80) << internal << "Zuvor sortierte Zahlenfolgen: " << endl;
                    printSort(saveSort, &seq);
                    saveSort = false;
    
                    break;
    
                case 'S':
                    printUeberschrift("sort");
                    seq.setSortModus("QSM");
                    printSort(saveSort, &seq);
                    
                    //Die zuvor sortierten FOlgen ausgeben
                    saveSort = true;
                    cout << setw(80) << internal << "Zuvor sortierte Zahlenfolgen: " << endl;
                    printSort(saveSort, &seq);
                    saveSort = true;
                    break;
                default:
                    cout << "Error" << endl;
                    break;
            }
    
        }
    }
    
    void Darstellung::printMedian(Sequenz* seq) {
    
        Median med;
        for (uint i = 0; i < 10; i++) {
    
            seq->leseZahlenfolge(dateiPfade[i]);
    
            pair<uint, uint> impPair2 = med(seq, 1, seq->get_n());
    
            
    
            uint median2 = seq->operator [](impPair2.first);
    
            const string T = "|  ";
            cout << left << setw(40) << (T + dateiPfade[i]);
            cout << left << setw(20) << (T + to_string(seq->get_n()));
            cout << left << setw(30) << (T + to_string(impPair2.second));
            cout << left << setw(30) << (T + to_string(median2));
            cout << T << endl;
    
    
        }
        printLine(119);
    }
    
    void Darstellung::printSort(bool saveSort, Sequenz* seq) {
    
    
        for (uint i = 0; i < 28; i++) {
    
            if (saveSort && seq->get_sortModus() == "QS") seq ->leseZahlenfolge("saveQuickSort\\" + dateiPfade[i]);
            else if (saveSort && seq->get_sortModus() == "QMS") seq ->leseZahlenfolge("saveQSMedian\\" + dateiPfade[i]);
            else seq->leseZahlenfolge(dateiPfade[i]);
            ////
            string isSorted = (seq->isSorted() ? "sortiert" : "nicht sortiert");
            ////    
            ////    //Folgen aus TestSuite2 ignorieren
            //    if (dateiPfade[i].find("TestSuite2") != std::string::npos) continue;
            ////    
            QuickSort quicksort;
            pair<uint, uint> impPair = quicksort(seq);
    
            //Ausgabe einer Zeile
            const string T = "|  ";
            cout << left << setw(40) << (T + dateiPfade[i]);
            cout << left << setw(20) << (T + to_string(seq->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 && saveSort && seq->get_sortModus() == "QMS") seq ->saveZahlenfolge("saveQSMedian\\" + dateiPfade[i]);
            else if (!saveSort && seq->get_sortModus() == "QS") seq ->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) << "|  Median";
            cout << "|" << endl;
        }
    
    
        printLine(breite);
    }
    
    
    

    Median.cpp

    
    #include "Median.h"
    
    
    Median::Median() {
    }
    
    Median::~Median() {
    
    }
    
    pair<uint, uint> Median::operator()(Sequenz* seq, uint l, int r) {
    
        bool ausMedian = true;
    
    
        uint k = (l + r) / 2 + ((l + r) % 2 > 0 ? 1 : 0); //aufrunden
    
        int pivot;
    
        clock_t start = clock();
    
        while (true) {
            pivot = seq->split(l, r, ausMedian);
            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*/
        }
    }
    
    
    
    
    

    QuickSort.cpp

    #include "QuickSort.h"
    
    #define _N_ seq->get_n()
    
    QuickSort::QuickSort() {
    }
    
    QuickSort::~QuickSort() {
    }
    
    pair<uint, uint> QuickSort::operator()(Sequenz* seq) {
    
        bool ausMedian = false;
        int l = 1;
        int r = _N_;
        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 = seq->split(l, r, ausMedian); /* 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);
    }
    

    Sequenz.cpp

    #include "Sequenz.h"
    #include "Median.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 l, int r) {
    
        int temp = zahlenFolge[l];
        zahlenFolge[l] = zahlenFolge[r];
        zahlenFolge[r] = temp;
    }
    
    
    int Sequenz::split(int l, int r, bool ausMedian) {
        
        Median med;
        
        int pivot;
        if (ausMedian) //ich komme aus der Median Methode 
    
            pivot = (l + r) / 2 + ((l + r) % 2 > 0 ? 1 : 0); //Pivotelement aufrunden 
    
        if (!ausMedian && this->sortModus == "QSM") //ich komme aus der Methode Quick Sort
    
            pivot = med(this, l, r).first - l;
    
        else {
            pivot = (l + r) / 2 + ((l + r) % 2 > 0 ? 1 : 0); //Pivotelement aufrunden 
        }
    
    
        swap(pivot, l);
        pivot = l;
    
    
        for (uint i = l + 1; i <= r; i++) {
            if (zahlenFolge[i] <= zahlenFolge[pivot]) {
                swap(i, (pivot + 1));
                swap(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;
    }
    
    uint Sequenz::operator[](uint index) {
        return this->zahlenFolge[index];
    }
    
    //Getter-Methoden
    
    uint Sequenz::get_n() const {
        return n;
    }
    
    string Sequenz::get_sortModus() const {
        return this->sortModus;
    }
    
    //Setter-Methode 
    
    void Sequenz::setSortModus(const string& moStr) {
        this->sortModus = moStr;
    }
    
    

    main.cpp

    using namespace std;
    
    #include "Sequenz.h"
    #include "Median.h"
    #include "QuickSort.h"
    #include "Darstellung.h"
    
    int main(int argc, char** argv) {
    
    
        Darstellung d;
        d.auswahl();
    
    
        //    //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;
    }
    
    
    


  • sorry wenn ich nerve😆 , aber ich habe den Fehler leider immer noch nicht gefunden😔
    Wäre echt nett wenn ihr mal drüber gucken könntet.

    Ich habe bei den Klassen Qucksort und Median übrigens den ()operator überladen weil ich mich an den c++ internen Algorithmen orientiert habe, also sowas wie @manni66 sagte.

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

    Wäre sowas auch möglich ohne vorher ein Objekt zu erstellen?

    Ich habe es im Code ja so geschrieben:

    Median med;
    med(sequenz, links, rechts);
    

    Das ist jetzt eher unwichtig aber würde den Code etwas schöner machen, weil mein Algorithmus dann im Original-Stil ausführbar wäre.



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

    Wäre sowas auch möglich ohne vorher ein Objekt zu erstellen?

    Du brauchst doch ein Objekt oder was willst du der Funktion sonst übergeben?


Anmelden zum Antworten