ich brauche dringend hilfe.
ich soll ein programm programmieren, dass eine zufällig gezogene zahlenreihe (z.b. 10 zahlen von 1 bis 20) rekusiv sortiert. einen denkansatz habe ich schon. das programm soll ähnlich wie quicksort sein aber ohne, dass die zahlenreihe dabei geteilt wird. die erste zahl ist dabei die pivot-zahl. ich habe leider überhaukt keine ahung wie ich das so programmieren soll. könnt ihr mir helfen? vielleicht habt ihr auch noch ein paar andere ideen für rekusive(!) sortieralgorithmen?


Moderiert von Gausi: Topic aus Sonstiges verschoben am Sa 24.09.2005 um 12:42

Aaalso. Du willst Quicksort verwenden, aber ohne die Folge aufzuteilen. Also quasi Quicksort, aber bitte ohne Quicksort. Als Pivotelement kann man jedes beliebige nehmen - natütlich auch das erste. Aber die Folge muss trotzdem aufgeteilt werden. So funktiniert halt Quicksort.

Ein anderer Algorithmus, der oft auch rekursiv programmiert wird, ist Mergesort.

Zu allen Sortierverfahren dürfte man aber genug im Forum finden...Einfach mal suchen

okay ich habe nocheinmal nachgeguckt und habe herausgefunden, dass es nicht unbeding quicksort sein muss es war nur ein beistil und das mit dem ansatz ist nicht so wichtig. ich glaube mein problem ist einfach, dass ich zu blöd bin mir selber eine rekusive prozedur auszudenken.
kennt also jemand ein rekusiven sortieralgorithmuss, denn er hier posten kann und der möglichst leicht ist, damit ich ihn verstehe?

Moin!

Du kannst prinzipiell jeden iterativen Algorithmus auch rekursiv abbilden und umgekehrt; ist nur eine Frage des Aufwandes, den du dafür treiben willst. Ich habe schonmal eine interative Quicksort-Implementation gesehen (schauer), ja das gibt es!

Könnte mir noch am ehesten eine rekursive Bubble-Sort-Variante vorstellen. Und wie BS funktioniert, ist ja mal hinlänglich bekannt.

cu
Narses

Narses hat folgendes geschrieben:

...Ich habe schonmal eine interative Quicksort-Implementation gesehen (schauer), ja das gibt es!

Stimmt. Die sind ja auch schneller! Beweis siehe Anhang.

GigaNeko, Dein Lehrer ist in meinen Augen eine Pfeife! Wie willst Du den Sinn von Rekursivität begreifen, wenn Ihr solche dämlichen Aufgaben à la "Schreibe ein Zählprogramm, aber rekursiv!" bekommt. Diesbezügliche Hilferufe sind in letzter Zeit häufiger aufgetaucht. Das Quicksort-Verfahren ist zwar rekusiv definiert, das heisst aber noch lange nicht, das man es auch rekursiv implementieren muss: Denn dann müsste die Addition auch rekursiv implementiert sein ('Der Nachfolger einer natürlichen Zahl ist eine natürliche Zahl')...

Rekursive Lösungen sind genau dann (als erster Ansatz) die richtige Wahl, wenn es um die Lösung eines Problemes geht, dessen Definition rekursiv ist. Z.B.: Ackermannsche Funktion, und m.E. Fibbionacci und Fakultät. Die beiden Letzten sind allerdings so einfach iterativ darzustellen (mit beträchtlichen Performancsprüngen), das eine rekursive Implementierung keinen Sinn ergibt. Als erster Lösungsansatz reichen sie jedoch allemal. I.a. sind rekursive Algorithmen auch leichter zu begreifen, weil sie eben der mathematischen Definition, die i.a. rekursiv ist, am nächsten kommen.

• N! = Wenn n=1 dann 1 sonst N* (N-1)!

Ich würde das Problem der "Türme von Hanoi" als Aufgabe zum Begreifen der Rekursivität nehmen. Hier ist die rekursive Lösung so elegant, das der Charme der Rekursivität vermittelt werden kann. Vor allen Dingen sind die Türme ein wunderbarer Einstieg, weil das Problem kaum lösbar erscheint, mit dem rekursiven 3-Zeiler jedoch auf einmal popeleinfach ist!

Oder z.B. Hilbertkurven. Hier wird Rekusivität auch visuell dargestellt.

Aber, na ja. Dann eben Sortieralgorithmen. HeapSort wäre neben Quicksort imho eine Möglichkeit für einen (halbwegs sinnvollen) rekursiven Sortieralgo. Aber, Bubblesort auf 'rekursivisch' möchte ich sehen. Das wäre wirklich eine schöne Verarsche für den Lehrer. Bitte die Lösung posten!