Quicksort mit 50% Wahrscheinlichkeit auf fehlerhafte Ausgabe



  • Hallo liebe Community,

    unten findet ihr ein selbst geschriebenes Quicksort. Ich brauche das zum Einen so und habe mich außerdem das erste Mal mit Vektoren beschäftigt.

    Grundsätzlich läuft das Quicksort auch wie erwünscht. Es besteht nur folgendes Problem: Bei ca. jedem zweiten Durchlauf passiert beim Auslesen ein Fehler, genauer gesagt steht dann an erster Stelle ein Zufallswert (Stellen 2-10 sind komplett korrekt). In der anderen Hälfte der Fälle, liefert das Programm absolut den richtigen Output.

    Ich finde den Fehler ums Verderben nicht. Hat jemand von euch eine Idee?

    #include <iostream>
    #include <vector>
    
    using namespace std;
    
    void quickSort(vector<int>&,int,int);
    
    int partition(vector<int>&, int,int);
    
    int main()
    {
    	vector<int> A = {6,10,13,5,8,3,2,25,4,11};
    	int p=0;
    	int q= A.size();
    
    	cout<<"======Original======="<<endl;
    	for(auto e: A)
    		cout<< e <<" ";
    	cout<< endl;    
    
    	quickSort(A,p,q);
    
    	cout<<"======Sorted======="<<endl;
    	for(auto e: A)
    		cout<< e <<" ";
    	cout<< endl;   
    }
    
    void quickSort(vector<int>&A, int p,int q)
    {
    	int r;
    	if(p < q)
    	{
    		r=partition(A, p, q);
    		cout << "geteilt\n";
    		quickSort(A,p,r);
    		quickSort(A,r + 1,q);
    	}
    }
    
    int partition(vector<int>&array, int bottom, int top)
    {
    	 int x = array[bottom];
    	 int i = bottom - 1;
    	 int j = top + 1;
    	 int temp;
    
    	 while (true){
    		do {
    				  j--;
    		   } while (x < array[j]);
    
    		  do {
    				 i++;
    		  } while (x > array[i]);
    
    		  if (i < j) { 
    				temp = array[i];    
    				array[i] = array[j];
    				array[j] = temp;
    				for(auto e: array)
    				   cout << e <<" ";
    				cout << endl; 
    		 } else {
    			return j;           // returns middle subscript  
    		 }
    	 }   
    
    }
    

    Danke und liebe Grüße
    InvisibleGhost



  • Dann wirst du wohl mindestens einen ungültigen Index verwenden. Benutze at() statt [], dann wird sich der Vector melden.



  • Deine Partition-Funktion sieht sehr verdächtig aus.

    Ersetze doch mal die eckigen Klammern array[] durch vector.at() - dann wird wird dir auch mitgeteilt, wenn du außerhalb des Arrays zugreifst.



  • Ich danke euch beiden vielmals für den Hinweis! Damit fällt auch sofort auf, dass es

    int q= A.size() - 1;
    

    und nicht

    int q= A.size();
    

    heißen muss. Wie gesagt, ich bin mit Vektoren noch unsicher.



  • while (x < array[j]);
    

    Und was ist damit?



  • Das habe ich natürlich durch

    while (x < array.at(j));
    

    ersetzt. Aber da spätestens an erster Stelle am Pivot-Element (sortierte Liste) der Vergleich scheitert, bekomme ich damit keinen fehlerhaften Speicherzugriff.



  • Was passiert denn hier.:

    do {
         i++;
    } while (x > array[i]);
    

    Wenn X das größte Element in dem vector ist.



  • Nicht viel, i steht dann einfach an der ersten Stelle des Vektors. Und das macht ja auch soweit Sinn, das ist nämlich der klassische Fall einer umgedreht sortierten Liste. Es wird dann einfach nur das Pivot Element mit dem ersten kleineren Element von rechts getauscht.



  • Und wann soll die Schleife beendet werden? Wenn du hier mit at(i) arbeiten würdest, würde dir dein Programm um die Ohren fliegen. Du brichst dann die Schleife nämlich erst ab wenn zufällig an der Stelle an der du liest ein Wert steht, der als Zahl interpretiert, größer oder gleich x ist.

    Edit : falsch sry. Im ersten schleifen Durchlauf bist du da bei array[bottom] ==x und brichst ab, weil x nicht größer als x ist.



  • vector<int> A = { 6,10,13,5,8,3,2,25,4,11 };
    	int p = 0;
    	int q = A.size();
    
    	quickSort(A, p, q);
    

    ->

    void quickSort(vector<int>&A, int p, int q)
    {
    	int r;
    	if (p < q)
    	{
    		r = partition(A, p, q);
    

    ->

    int partition(vector<int>&array, int bottom, int top)
    {
    	int x = array[bottom];
    	int i = bottom - 1;
    	int j = top + 1;
    	int temp;
    
    	while (true) {
    		do {
    			j--;
    		} while (x < array[j]);
    

    j = 11
    size = 10



  • unskilled schrieb:

    vector<int> A = { 6,10,13,5,8,3,2,25,4,11 };
    	int p = 0;
    	int q = A.size();
    
    	quickSort(A, p, q);
    

    ->

    void quickSort(vector<int>&A, int p, int q)
    {
    	int r;
    	if (p < q)
    	{
    		r = partition(A, p, q);
    

    ->

    int partition(vector<int>&array, int bottom, int top)
    {
    	int x = array[bottom];
    	int i = bottom - 1;
    	int j = top + 1;
    	int temp;
    
    	while (true) {
    		do {
    			j--;
    		} while (x < array[j]);
    

    j = 11
    size = 10

    Genau, danke! Wie schon oben beschreiben, lag der Fehler darin, dass q um eins zu groß ist.