Fehler in Quickselect Algorithmus



  • hi,
    bitte um feedback zu meinem quickselect algo...der algo funktioniert nicht wenn ich doublicates habe...

    #include <iostream> 
    #include <vector> 
    #include <algorithm> 
    #include <ctime> 
    using namespace std;
    
    int rand_partition(vector<int> &a, int left, int right) {
    	int pivotIndex = left + (rand() % (right - left));
    	//int m = left + (right - left) / 2; //... to test the algo...no rand at this point 
    	int pivot = a[pivotIndex];
    	int i = left;
    	int j = right;
    
    	do {
    		while (a[i] < pivot) i++; // find left element > pivot 
    		while (a[j] > pivot) j--; // find right element < pivot 
    
    		// if i and j not already overlapped, we can swap 
    		if (i < j) {
    			swap(a[i], a[j]);
    		}
    	} while (i < j);
    
    	return i;
    }
    
    // Returns the n-th smallest element of list within left..right inclusive (i.e. n is zero-based). 
    int quick_select(vector<int> &a, int left, int right, int n) {
    	if (left == right) {        // If the list contains only one element 
    		return a[left];  // Return that element 
    	}
    
    	int pivotIndex = rand_partition(a, left, right);
    
    	// The pivot is in its final sorted position 
    	if (n == pivotIndex) {
    		return a[n];
    	}
    	else if (n < pivotIndex) {
    		return quick_select(a, left, pivotIndex - 1, n);
    	}
    	else {
    		return quick_select(a, pivotIndex + 1, right, n);
    	}
    }
    
    int main() {
    
    	vector<int> vec= {1, 0, 3, 5, 0, 8, 6, 0, 9, 0};
    
    	cout << quick_select(vec, 0, vec.size() - 1, 5) << endl;
    
    	return 0;
    }
    


  • "Funktioniert nicht" ist keine Fehlerbeschreibung.
    Dein Algorithmus ist einfach falsch, er tauscht immer die gleichen Elemente und hängt somit in einer Endlosschleife.

    Um das Problem zu lösen, einfach Google frage. Gibt genug Sourcecode und Erklärungen zu Quicksort.



  • DarkShadow44 schrieb:

    "Funktioniert nicht" ist keine Fehlerbeschreibung.
    Dein Algorithmus ist einfach falsch, er tauscht immer die gleichen Elemente und hängt somit in einer Endlosschleife.

    Glaub ich nicht. Hab's nicht ausprobiert, aber ... wieso sollte der immer die selben Elemente tauschen?

    Was dagegen problematisch aussieht ist das fehlende Bounds-Checking in den i++/j++ Loops.



  • DarkShadow44 schrieb:

    Um das Problem zu lösen, einfach Google frage. Gibt genug Sourcecode und Erklärungen zu Quicksort.

    es geht um quickselect, nicht um quicksort.



  • asfdlol schrieb:

    DarkShadow44 schrieb:

    Um das Problem zu lösen, einfach Google frage. Gibt genug Sourcecode und Erklärungen zu Quicksort.

    es geht um quickselect, nicht um quicksort.

    Und?



  • hustbaer schrieb:

    DarkShadow44 schrieb:

    "Funktioniert nicht" ist keine Fehlerbeschreibung.
    Dein Algorithmus ist einfach falsch, er tauscht immer die gleichen Elemente und hängt somit in einer Endlosschleife.

    Glaub ich nicht. Hab's nicht ausprobiert, aber ... wieso sollte der immer die selben Elemente tauschen?

    Was dagegen problematisch aussieht ist das fehlende Bounds-Checking in den i++/j++ Loops.

    Ist aber so. Wenn a[i]=a[j]=pivot vertauscht er beide elemente immer wieder. Und läuft nicht weiter. Die bounds sind natürkich noch dazu problematisch...



  • Glaub ich nicht. Hab's nicht ausprobiert, aber ... wieso sollte der immer die selben Elemente tauschen?

    Weil der Algorithmus sich darauf verlässt dass nach dem swap eine Änderung eingetreten ist:

    do{
        while (a[i] < pivot) i++; //wenn swap nichts ändert 
        while (a[j] > pivot) j--; //dann brechen die Schleifen sofort ab
    
        if (i < j)
            swap(a[i], a[j]); //ändert nichts, beim nächste Durchlauf wird keine Varaible geändert und das Programm hängt für alle Ewigkeit
    } while (i < j);
    


  • Achjeh ich blindes Huhn!
    Ja, da müsste <= bzw. >= stehen.
    Huiiiiiiii.

    Danke für's Erklären!



  • sollte so ok sein? muss die funktion noch testen!

    int rand_partition(vector<int> &a, int left, int right) {
    	int pivotIndex = left + (rand() % (right - left));
    	//int m = left + (right - left) / 2; //... to test the algo...no rand at this point 
    	int pivot = a[pivotIndex];
    	int i = left;
    	int j = right;
    
    	do {
    		while (i < j && a[i] <= pivot) i++; // find left element > pivot 
    		while (i < j && a[j] > pivot) j--; // find right element < pivot 
    
    		// if i and j not already overlapped, we can swap 
    		if (i < j) {
    			swap(a[i], a[j]);
    		}
    	} while (i < j);
    
    	return i;
    }
    


  • Klar ist es. Das Programm hängt sich nicht mehr auf.
    Allerdings funktioniert der Algorithmus immer noch nicht. Aber da der Algorithmus aus dem Anfangspost nauch nicht funktioniert, nicht mal ohne Duplikate, passt das schon. 🙂

    Es sei denn das Programm soll gar nicht sortieren, aber dann kannst du das auch deutlich kürzer schreiben. 😃



  • DarkShadow44 schrieb:

    Es sei denn das Programm soll gar nicht sortieren, aber dann kannst du das auch deutlich kürzer schreiben. 😃

    Vielleicht liest Du einfach mal nach was Quickselect ist?



  • Vielleicht liest Du einfach mal nach was Quickselect ist?

    Hab ich. Und nun ?
    Teilweise sortiert werden muss auch hier werden. Und einfach mal ein <= einbauen ohne zu testen und hoffen dass es geht führt normalweise nicht zum Ziel.

    Folgendes Testprogramm:

    void quickTest(int start, int n)
    {
    	vector<int> vec;
    	vec.push_back(9);
    	vec.push_back(2);
    	vec.push_back(3);
    	vec.push_back(5);
    	vec.push_back(40);
    	vec.push_back(1);
    
    	cout << quick_select(vec, start, 5, n) << endl; 
    }
    
    int main()
    { 
    	quickTest(0, 0);
    	quickTest(0, 1);
    
    	quickTest(1, 0);
    	quickTest(1, 1);
    
        return 0; 
    }
    

    Mit alten Algorithmus:

    1
    2

    1
    1

    Mit neuem Algorithmus:

    1
    2

    2
    2

    Beides falsch.
    Oder wo ist mein Fehler ? 😕



  • Naja der 2. rekursive Abstieg ist noch falsch.
    Die Partition selbst müsste OK sein.
    Wobei ich nicht verstehe wieso die Bedingung nur in einer der beiden Schleifen geändert wurde.
    Ich würd das in beiden ändern.



  • hustbaer schrieb:

    Naja der 2. rekursive Abstieg ist noch falsch.
    Die Partition selbst müsste OK sein.
    Wobei ich nicht verstehe wieso die Bedingung nur in einer der beiden Schleifen geändert wurde.
    Ich würd das in beiden ändern.

    Stell dir vor, ich packe an beide enden ein element mit pivot-wert. Über die läufst du nun drüber. Danach hast du keine chance mehr das richtig hinzukriegen. Ich denke es ist schon sinnvoll sonzuu partitionieren, dass zum beispiel alles was kleiner oder gleich pivot ist links landet und der rest rechts.

    @Darkshadow44: die Empfehlung das mal nachzulesen war nur als Hilfestellung zur Erlangung von Kongruenz zwischen Tonfall und vorhandenem Fachwissen gedacht.

    Anders gesagt: wenn jemand sich an quickselect versucht, dann ist eine hilfestellung wie "dein quicksort sortiert nicht richtig, und wenn es das nicht soll könnte ich das auch mit weniger code" schon recht vielsagend, aber halt nicht für den der gefragt hat.



  • Anders gesagt: wenn jemand sich an quickselect versucht, dann ist eine hilfestellung wie "dein quicksort sortiert nicht richtig, und wenn es das nicht soll

    könnte ich das auch mit weniger code" schon recht vielsagend, aber halt nicht für den der gefragt hat.

    Stimmt schon, das war nicht richtig, tut mir leid. 😞
    Ich kann den Algorithmus ja selber nicht gut...

    Ich hätte jetzt folgendes gemacht:

    int rand_partition(vector<int> &a, int left, int right) { 
        int pivotIndex = left + (rand() % (right - left)); 
        //int m = left + (right - left) / 2; //... to test the algo...no rand at this point 
        int pivot = a[pivotIndex]; 
        int i = left; 
        int j = right-1; 
    
    	swap(a[pivotIndex], a[right]);
    
        do { 
            while (i < j  && a[i] <= pivot)
    			i++; // find left element > pivot 
            while (i < j && a[j] > pivot)
    			j--; // find right element < pivot 
    
            // if i and j not already overlapped, we can swap 
            if (i < j) { 
                swap(a[i], a[j]); 
            } 
        } while (i < j); 
    
    	if(a[i]>pivot)
    	{
    		swap(a[i], a[right]);
    		return i;
    	}
    
        return i+1;
    }
    

    Das funktioniert soweit, ist aber nicht wirklich schön...



  • Jester schrieb:

    hustbaer schrieb:

    Naja der 2. rekursive Abstieg ist noch falsch.
    Die Partition selbst müsste OK sein.
    Wobei ich nicht verstehe wieso die Bedingung nur in einer der beiden Schleifen geändert wurde.
    Ich würd das in beiden ändern.

    Stell dir vor, ich packe an beide enden ein element mit pivot-wert. Über die läufst du nun drüber. Danach hast du keine chance mehr das richtig hinzukriegen. Ich denke es ist schon sinnvoll sonzuu partitionieren, dass zum beispiel alles was kleiner oder gleich pivot ist links landet und der rest rechts.

    💡
    Danke.

    Also im Moment hab ich echt nen Lauf Quatsch zu schreiben. So viel Mist wie in den letzten 3 Tage schreib ich sonst nicht in 3 Wochen...


Anmelden zum Antworten