Quicksort - Problem



  • Ich bin Anfänger in C++.
    Ich soll für ein Referat ein Beispielprojekt mit einem Quicksort Algorithmus schreiben.

    Soweit bin ich gekommen:

    #include <iostream>
    #include <iomanip>
    #include <conio.h>
    
    using namespace std;
    
    int main() {
    
    	int wuerfel[10], swap;
    
    	for (int idx = 0; idx <= 9; idx++)
    	{
    		cout << "Geben Sie die " << idx+1 << ". gewuerfelte Zahl ein: ";
    		cin >> wuerfel[idx];
    	}
    
    	cout << endl << "unsortierte Zahlen: " << endl;
    
    	for (int idx = 0; idx <= 9; idx++)
    	{		
    		cout << wuerfel[idx] << " ";
    	}
    
    	cout << endl << endl;
    
    	int i = 0, j = 9;
    
        int x = wuerfel[(9 / 2)]; 
    
        while (i <= j) 
    	{
    		while (wuerfel[i] < x) i++;
    		while (wuerfel[j] > x) j--;
    
    		if (i <= j) 
    		{
    			swap = wuerfel[i];
    			wuerfel[i] = wuerfel[j];
    			wuerfel[j] = swap;
    			i++;
    			j--;
    		}
    
          }
    
    	cout << "sortierte Zahlen: " << endl;
    
    	for (int idx = 0; idx <= 9; idx++)
    	{		
    		cout << wuerfel[idx] << " ";
    	}
    
    	getch();
    	return 0;
    }
    

    Jedoch finde ich meinen Fehler nicht.
    Könnt ihr mir bitte helfen?



  • Was macht er denn falsch?



  • er sortiert es nicht richtig, warum?
    ich kann es mir nicht erklären.
    er hat vllt. 4 Zahlen von den 10 richtig sortiert.
    mehr aber nicht...
    ich glaube mir fehlt die rekursion, aber ich hab leider keine ahnung wie man die macht ^^
    es muss sich ja selbst nochmal unterteilen..





  • Haha, ob ich das noch nicht alles gelesen hätte. 😉

    Ich bin ratlos, suche schon seit Stunden.

    Wir haben im Unterricht noch nicht Void etc. behandelt, also keine Ahnung wie das geht.

    Gibt es eine Lösung für meinen Wissensstandart?



  • Benutz den Debugger, Bleistift und Papier...
    Einfach ein Bsp. machen welches nicht funktioniert und durchexerzieren.
    Simon



  • Auch das schon gemacht.
    Ich komm nicht auf den Fehler.

    Ich habe schon eigentlich alles durchprobiert.

    Da ich zu Verzweifelt bin, wende ich mich ja an euch. :o



  • Was soll das heißen, du kommst nicht auf den Fehler? Du weißt doch, dass Quicksort rekursiv ist, aber dein Programm nicht. Wenn ich das richtig sehe, hast du das Programm genauso geschrieben wie bei bellis Link, nur die Rekursion weggelassen.

    Was meinst du eigentlich damit, dass du "void etc." nicht kennen würdest? Falls du damit meinst, dass du nicht weißt, wie man eine Funktion schreibt, solltest du dich darum zuerst kümmern, und erst dann Quicksort in Angriff nehmen.



  • oder du schreibst den algorithmus iterativ statt rekursiv...

    wobei ich nicht weiss ob das geht, denn es ist nicht bewiesen dass jede rekursive funktionen auch iterativ formuliert werden kann (siehe ackermann funktion für eine normale zählschleife)



  • Richtig, das ist auch der Witz an der Sache.

    Also ich war mir nicht sicher, ob es die Rekursion ist.
    Diese versteh ich nicht. Also verstehe ich es richtig, mir fehlt die Rekursion damit das Programm richtig läuft?

    Zur Verständnis:
    Ich muss ein Referat über Bubblesort und Quicksort machen.
    In der Schule haben wir alles behandelt, was man in meinem Code sieht.
    Das "void etc." leider nocht nicht. TROTZDEM hat man mir aufgegeben ein Referat über Quicksort zu machen. Darum such ich jetzt eine andere Möglichkeit, welche mit meinem Wissen die Rekursion (von der Homepage da) ersetzt.



  • Skym0sh0 schrieb:

    oder du schreibst den algorithmus iterativ statt rekursiv...

    wobei ich nicht weiss ob das geht, denn es ist nicht bewiesen dass jede rekursive funktionen auch iterativ formuliert werden kann (siehe ackermann funktion für eine normale zählschleife)

    Sorry, ich bin Anfänger.
    Ein Iteratives Quicksort geht laut Wikipedia.
    Genau die Möglichkeit such ich,
    wie ich es ohne die Rekursion trotzdem umsetzen kann.

    Aber, wie würde mein Quicksort Projekt nun als Iteratives aussehen?



  • Hier stand mist.





  • Links bringen mir gar nichts.
    Ich google schon selber.
    Leider erklären sich Codes nicht von allein.

    Gibt es den keine Lösung für den Quicksort Algorithmus mit irgendwelche Schleifen etc.?



  • Doch, hinter dem zuletzt geposteten Link zum Beispiel. Allerdings ist deine Motivation fraglich. Die rekursive Formulierung ist um einiges einfacher zu verstehen und umzusetzen, keine Ahnung von Funktionen zu haben ist der falsche Grund für eine iterative Umsetzung.



  • @Bashar: Mir ist fraglich, ob du überhaupt alles gelesen hast was ich geschrieben habe.

    Ich mach es für die Schule. Ich muss ein Beispielprojekt mit Quicksort machen und darf nicht! irgendwelche neue Sachen einführen. Ich muss es nur mit Schleifen etc. lösen. Motivation? Die habe ich. Ich hab die ganze Nacht rumprobiert. Ich habe seit 30 Stunden nicht geschlafen. Ich bin langsam am verzweifeln.
    Und nochmal, ich bin Anfänger. Ich versteh nicht jeden Code der mir gepostet wird, sorry. :o



  • Leider ist Quicksort nunmal ein rekursiver Algorithmus und auch rekursiv am besten zu verstehen und zu erklären.
    Es gibt eine iterative Version, aber da hat man nur die Rekursion durch einen Stack erstetzt, um die Nachteile von rekursiven Aufrufen (möglicher Stacküberlauf) zu verhindern. Es ist somit eine Erweiterung bzw. fortgeschrittenere Implementierung und dementsprechend komplizierter. Insofern ist hier die Aufgabe sehr in Frage zu stellen, wenn du als Anfänger Anfängern Quicksort näher bringen sollst ohne Rekursion zu benutzen.

    Aber Glück für dich: Rekursion ist nichts Neues, da ihr mit Sicherheit schon Funktionsaufrufe hattet! Rekursion heißt einfach nur, dass eine Funktion sich selbst aufruft, ist also nur ein Spezialfall eines Funktionsaufrufes. Insofern hast du beim Lehrer zumindest eine Ausrede.



  • Wenn du void nicht kennst, dann mach daraus int und liefer 0 als Ergebnis deiner Funktion zurück. Ich seh jetzt nicht warum es an so einem kleinen Detail scheitern soll. Code wurde nun ja schon einige Male gepostet. Dann setzt dich hin und geh den Schritt für Schritt durch und überlege was er bewirkt. Keiner wird dir den Code nun kommentieren, falls du sowas erwarten solltest.



  • Rekursion ist absolut nicht schwer zu verstehen und Funktionen hattet ihr schon (int main() ist eine Funktion, wenn auch eine spezielle).

    Zu void: Das bedeutet einfach nur, dass deine Funktion keinen Wert mittels "return" zurückgibt.

    Kleines Rekursionsbeispiel:

    void forever()
    {
      forever();
    }
    

    Das ist eine rekursive Funktion, die immer nur sich selbst aufruft. Mehr ist Rekursion nicht.

    Natürlich ist das Beispiel sinnlos, weil es eine Endlosschleife ist, aber der Trick an Rekursion ist lediglich, dass man irgendwann einen Punkt erreicht hat, ab dem man die Rekursion abbricht.

    Anderes Beispiel für Rekursion:

    int factorial(int n)
    {
      if (n == 1)
        return 1;
      return n * factorial(n - 1);
    }
    

    Was macht factorial? Es berechnet die Fakultät einer Zahl (4! = 4 * 3 * 2 * 1), indem es immer wieder sich selbst aufruft, wobei die Zahl immer um eins verringert wird. Sobald allerdings 1 erreicht wird, bricht die Funktion ab.

    So, und jetzt schau dir nochmal den Pseudocode bei Wikipedia an und versuche die Rekursion, die dort abläuft, zu verstehen.



  • Graffiti schrieb:

    @Bashar: Mir ist fraglich, ob du überhaupt alles gelesen hast was ich geschrieben habe.

    Ich mach es für die Schule. Ich muss ein Beispielprojekt mit Quicksort machen und darf nicht! irgendwelche neue Sachen einführen. Ich muss es nur mit Schleifen etc. lösen.

    Dann bleibt als einzige "Lösung" deinem Lehrer zu sagen dass er ein Koffer ist.

    Wie schon mehrfach erwähnt wurde ist Quicksort ein rekursiver Algorithmus, und das Umwandeln eines solchen in einen Iterativen ist für Schüler die gerade erst programmieren lernen ganz sicher keine geeignete Aufgabe (weil viel zu schwer).

    Also ich sehe da folgende Möglichkeiten
    * du versuchst Quicksort ohne Rekursion zu implementieren und scheiterst
    * du sagst deinem Lehrer dass Quicksort intrinsisch rekursiv ist, und du ihn nicht umsetzen konntest, da ihr Rekursion noch nicht durchgenommen habt
    * du implementierst Quicksort MIT Rekursion, und erklärst deinem Lehrer warum
    * du gehst vor dem Referant zu deinem Lehrer, erklärst ihm die Sache, und bittest um ein neues Thema + neuen Termin für das Referat


Log in to reply