Aufgabe mit einer Sortierfunktion

[forumnewbie]

Hi! Nächste Aufgabe bei der ich Hilfe brauche.
Folgendes ist gegeben:

int part(int array[], int length);
Am Anfang ist das Pivotelement = array[0]. Nach der Ausführung dieser Funktion gilt folgendes: array[0]...array <=(kleiner-gleich) Pivotelement und array[i+1]...array[length-1] > Pivotelement. Und i ist der Rückgabewert dieser Funktion.

Fragen:
a) Was bewirkt diese Funktion, wenn das Array folgende Elemente beinhaltet: array[] = {3,5,4,1,6,2}?
b) Mithilfe dieser Funktion soll eine rekursive Sortierfunktion programmiert werden. Und man muss das Verhalten dieser neuen Sortierfunktion für das array[] angeben.
c) Die Funktion int part(int array[], int length) programmieren.

Meine Antwort zu der Frage a): Die Ziffer 3 ist das Pivotelement. Nach der Ausführung dieser Funktion stehen alle Elemente, die <3 sind links und >3 rechts. Nach der Ausführung müsste das Array so aussehen: {1,2,3,4,5,6}
Welchen Wert hat aber die Variable i und warum reicht array< Pivotelement nicht aus (ohne GLEICH)?
Bei b) habe ich leider im Moment keine Ideen wie ich das machen kann, weil ich den Rückgabewert von der Funktion part noch nicht verstehe.
Außerdem kann ich rekursive Funktionen zwar lesen und verstehen, aber ich verstehe nicht, wie man eine rekursive Funktion erfinden kann? Gibt es da einen Trick oder eine richtige Herangehensweise?
Frage c) versuche ich zu machen, wenn ich a) und b) verstanden habe.

Danke!

[nufan]

Ich will dir jetzt auch nicht zu viel verraten ^^ Aber der beschriebene Algorithmus nennt sich "Quicksort". Dieser Suchbegriff sollte dir die Aufgabe wesentlich erleichtern.

[forumnewbie]

Danke für den Tipp. Die Lösung findet man ziemlich schnell im Netz, wenn man weiß wonach man suchen muss.
Ich versuche gerade den Algorithmus zu verstehen - ich habe mehrere Seiten gefunden, wo der Algorithmus erklärt wird. Das sollte ich hinkriegen.

Was ich leider nicht verstehe, wie man selbst eine rekursive Funktion erstellt. Wenn man eine rekursive Lösung sieht, dann versteht man diese (meistens ), aber wie kann man selbst darauf kommen? Kennt jemand zufällig eine Seite, wo man das üben kann oder kann jemand mir vielleicht einen Tipp geben?

Danke!

[Xin]

Was ich leider nicht verstehe, wie man selbst eine rekursive Funktion erstellt. Wenn man eine rekursive Lösung sieht, dann versteht man diese (meistens ), aber wie kann man selbst darauf kommen? Kennt jemand zufällig eine Seite, wo man das üben kann oder kann jemand mir vielleicht einen Tipp geben?

Hast Du Dich mal mit Bäumen beschäftigt?

Ich denke, wenn es darum geht, einen Baum auszugeben oder sich an dessen Blättern entlang zu hangeln, versteht man den Ablauf einer rekursiven Funktion recht gut.

Ansonsten ergibt sich die Rekursion eher automatisch, wenn man ein Problem löst, dass rekursiv lösbar ist: Du suchst schließlich eine Lösung und stellst fest, dass Du nachdem Du das oberste Problem gelöst hast, wieder das gleiche Problem lösen musst - diesmal nur mit den Daten, die Du vom vorherigen Problem erhältst.
Keiner geht hin und versucht Probleme rekursiv zu lösen, weil er Rekursion mag... Du studierst ja auch nicht, weil Du so gerne im Klassenzimmer sitzt, sondern weil Du ein Problem lösen musst: Dein Geld irgendwann mit etwas zu verdienen, was Dich nicht total anödet. Da ist ein Studium eine akzeptable Lösung.

[nufan]

Danke für den Tipp. Die Lösung findet man ziemlich schnell im Netz, wenn man weiß wonach man suchen muss.
Ich versuche gerade den Algorithmus zu verstehen - ich habe mehrere Seiten gefunden, wo der Algorithmus erklärt wird. Das sollte ich hinkriegen.

Vielleicht hilft dir das:
http://www.proggen.org/doku.php?id=algo:quicksort

Was ich leider nicht verstehe, wie man selbst eine rekursive Funktion erstellt. Wenn man eine rekursive Lösung sieht, dann versteht man diese (meistens ), aber wie kann man selbst darauf kommen? Kennt jemand zufällig eine Seite, wo man das üben kann oder kann jemand mir vielleicht einen Tipp geben?

Prinzipiell kannst du jede Wiederholung als Rekursion darstellen. Sinnvoll ist sie vor allem, wenn du auf vorherige Ergebnisse zurückgreifen musst, oder Verzweigungen innerhalb der Wiederholung hast, die als Schleife nur schwer darstellbar wären.
Du kannst dir auch das mal durchlesen:
http://www.proggen.org/doku.php?id=c:tutorial:recursion
Und hier ein Anwendungsbeispiel mit steigernder Komplexität:
http://www.proggen.org/doku.php?id=algo:knapsack

[forumnewbie]

Mit Bäumen kenne ich mich noch nicht aus. Werde mir das angucken, aber erst nach der Prüfung.

So, also ich habe eine Lösung, die jedoch nicht der gewünschten entspricht, da ich in meiner Lösung die Indexnummer der most-left und most-right Elemente übergebe.

Hier meine komplette Lösung:

Code: Alles auswählen

#include <stdio.h>

void swap(int *a, int *b)
{
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}
int partition(int array[], int l, int r, int array_length)
{
    int x = array[r], i = l-1, j = r;
    while(1)
    {
        while(array[++i]<x && i<array_length);
        while(array[--j]>x && j>=0);

        if(i<j){
             swap(&array[i], &array[j]);
        }else{
            swap(&array[i], &array[r]);
            return i;
        }
    }
}

void quick_sort(int array[], int l, int r, int array_length)
{
    if(l<r)
    {
        int pivot = partition(array, l, r, array_length);
        quick_sort(array, l, pivot-1, array_length);
        quick_sort(array, pivot+1, r, array_length);
    }
}


int main()
{
    int array[] = {30,20,50,40,10};
    int array_length = 5, i;
    quick_sort(array,0,4, array_length);
    for(i=0;i<array_length;i++) printf("%d ", array[i]);

    return 0;
}

Kann mir jemand bitte zeigen, wie das ohne most-left und most-right funktioniert? Also nur mit void quick_sort(int array[], int array_length) und int partition(int array[], int array_length).

Diese Aufgabe soll sogar ohne PC gelöst werden - die schwerste, die ich bis jetzt gesehen habe (die ohne Computer gelöst wird). Ich hoffe, dass die Prüfung nicht extrem schwer sein wird. Sie wird aber mit Sicherheit schwer - hat die höchste Durchfallquote bei den Wirtschaftsinformatikern (von allen Prüfungen).

[forumnewbie]

Ich habe jetzt zahlreiche C-Programme mit Quicksort gesehen und überall wird noch die Index des ersten Elements und des letzten an die Funktionen quicksort und partition übergeben und damit gearbeitet. Verstehe ich vielleicht diese Aufgabe falsch? Darf man einen Funktionskopf erweitern, wenn man mit dem neuen die Aufgabe lösen kann?

Danke.

[forumnewbie]

Hat sich erledigt. Das ist die einfache Version von Quicksort, bei der sich die Elemente nicht wiederholen. Das steht nicht in der Aufgabestellung (man kann es nur an dem Array erkennen) und wenn man diesen Algorithmus noch nicht kennt, dann kann man sehr lange suchen, da man diese einfache Version in der Praxis nicht anwendet und ich auch nicht gewusst habe, dass es so was gibt.

[Xin]

Hat sich erledigt. Das ist die einfache Version von Quicksort, bei der sich die Elemente nicht wiederholen. Das steht nicht in der Aufgabestellung (man kann es nur an dem Array erkennen) und wenn man diesen Algorithmus noch nicht kennt, dann kann man sehr lange suchen, da man diese einfache Version in der Praxis nicht anwendet und ich auch nicht gewusst habe, dass es so was gibt.

Ich habe den QS einmal kapiert und das ist lange her, als ich den Compiler/Interpreter debuggt habe (das war mein Problem), der den QS ausführte. Inzwischen schon wieder verdrängt?!

Es gibt zwei QS? ^^