Pascal: Programm Quicksort mit Rekursion und ohne!

[Nick89]

Liebe Community.

Ich hoffe sehr, dass mir hier jemand helfen kann. Eigentlich bin ich ziemlich gut in Informatik, aber hier übersteigt es auch meine Fähigkeiten (und vor allem auch die Fähigkeiten unseres kompletten Infokurses).

Ich wollte die Gunst der Stunde nutzen und mal ein bisschen was gutes für meine Info-Note tun . Es steht ja jedem frei im Internet nach Hilfe zu suchen. Jedenfalls wird unser Lehrer am Freitag fragen, wer ein komplettes Programm hat

UND dieses auch erklären kann. Heute hatte sich jemand zu eilig gemeldet, bei dem ists aufgeflogen, dass er das Programm aus dem Internet kopiert hat .

So, zur Aufgabe:

Wir sollen ein Zahlenfeld, das mit beliebigen Zahlen gefüllt wird, mit dem Sortierverfahren "Quicksort" sortieren. Dabei sollen wir das entsprechende Programm einmal nicht rekursiv und einmal rekursiv schreiben.

Bis Freitag würde mir erstmal der nicht rekursive Ansatz reichen.

Ich brauche aber nicht nur das Programm, sondern klar, ich muss es auch verstehen. Und das ist gar nicht so leicht .

Ich habe hier mal meinen Ansatz:

PROGRAM Quicksort;

USES Crt;

CONST

Max = 10;

VAR

Feld :ARRAY[1..Max] OF INTEGER;

Zahlenfeld :ARRAY[1..Max] OF INTEGER;

Index, Index2 :INTEGER;

Zwischenspeicher, Zufallszahl :INTEGER;

neuezahl, Tausch :BOOLEAN;

l, r :INTEGER;

PROCEDURE Eingabe;

BEGIN

FOR Index:= 1 TO Max DO

BEGIN

REPEAT

RANDOMIZE;

Zufallszahl := RANDOM(1000);

NeueZahl := TRUE;

FOR Index2:= 1 TO Index DO

BEGIN

IF Zufallszahl = Zahlenfeld[index2] THEN

BEGIN

neuezahl:= FALSE;

END;

END;

UNTIL NeueZahl = TRUE;

Zahlenfeld[index] := Zufallszahl;

END;

l := 1;

r := Max;

END;

PROCEDURE Quick (l, r: INTEGER);

VAR m, v, temp : INTEGER;

BEGIN

IF l < r THEN

BEGIN

m := (l + r) div 2;

v := Feld[m];

Index := l;

Index2 := r;

WHILE Index <= Index2 DO

BEGIN

WHILE Feld[index] < v DO

inc(Index);

WHILE Feld[index2] > v DO

dec(Index2);

IF Index <= Index2 THEN

BEGIN

temp := Feld[index];

Feld[index] := Feld[index2];

Feld[index2] := temp;

inc(Index);

dec(Index2);

END;

quick(l,Index2);

quick(Index,r);

END;

END;

END;

BEGIN

Eingabe;

Quick(l, r);

END.

Die Procedure Quick habe ich ca. so aus dem Internet gezogen. Ich habe versucht sie so gut wie möglich auf mein Programm zu übertragen.

Leider funktioniert es nicht. Ich weiß auch leider nicht, warum!

Ich verstehe auch schon nicht, warum die Procedure mit Variablenübergabe von l und r arbeitet. Die könnte man doch eigentlich pauschal festlegen, wie ichs ja auch in der Procedure Eingabe gemacht habe?

Ich gehe mal die Procedure Quick Zeile für Zeile durch und schaue, wie weit ich das jetzt verstehen kann :

PROCEDURE Quick (l, r: INTEGER);

(Verstehe hier schon nicht, wieso Variablenübergaben benutzt werden!)

VAR m, v, temp : INTEGER;

(Lokale Variablen, ist klar. "temp" als Zwischenspeicher beim Tauschen, m ist sozusagen die "Mitte des Zahlenfeldes" und v ist dann der entsprechende Wert, der in der m gespeichert ist, oder?)

BEGIN

IF l < r THEN

(l ist doch aber immer größer als r??)

BEGIN

m := (l + r) div 2;

(Div bedeutet doch Teilen ohne Rest? was passiert denn, wenn ich 1 + 10 /2 = 5,5 habe? Nimmt er dann 5 oder 6 als m?)

v := Feld[m];

Index := l;

Index2 := r;

WHILE Index <= Index2 DO

BEGIN

WHILE Feld[index] < v DO

inc(Index);

WHILE Feld[index2] > v DO

dec(Index2);

(Was bedeuten die Befehle dec() und inc()? Verkleinern und Vergrößern? Oben steht ja "While Index <= Index2 DO..." Index bleibt doch immer kleiner als Index2 (wie l auch immer kleiner als r bleibt)?)

IF Index <= Index2 THEN

BEGIN

temp := Feld[index];

Feld[index] := Feld[index2];

Feld[index2] := temp;

inc(Index);

dec(Index2);

(Den Abschnitt verstehe ich gar nicht. Mir ist schon klar, dass hier etwas getauscht wird. Oder ist es etwas so: In dem oberen Abschnitt werden also die Werte der Indices untereinander jeweils auf der linken Seite von "m" und auf der rechten Seite von "m" getauscht,

soweit es eben geht. Und wenn da alles mögliche sortiert wurde, wird "seitenübergreifend" geschaut und ggf. Werte von der linken Seite von "m" mit Werten von der rechten Seite von "m" getauscht, ja??)

END;

quick(l,Index2);

quick(Index,r);

(Auch keine Ahnung warum die Procedure hier noch 2x aufgerufen wird. Aber d.h., die Fassung hier ist rekursiv! Auch gut )

END;

END;

END;

Soweit dazu! Jetzt weiß ich auch nicht, wie ich die Procedure Quick dann im Hauptprogramm aufrufe! Ich denke Einfach "Quick(l, r);" ist nicht korrekt.

Kann ich bei der Ausgabe des sortierten Feldes dann einfach schreiben:

PROCEDURE Ausgabe;

BEGIN

FOR Index := 1 TO Max DO

WRITE (Feld[index])

END;

Ihr seht, ICH HABE MIR SCHON GEDANKEN GEMACHT! Aber ich komme ohne Hilfe leider nicht weiter.

Ich wäre euch wirklich sehr dankbar, wenn sich jemand die Zeit nehmen würde, mir zu helfen.

Liebe Grüße,

Nick:confused:

[flashpixx]

Eigentlich bin ich ziemlich gut in Informatik, aber hier übersteigt es auch meine Fähigkeiten [...]

Naja, dann verstehe ich Dein Problem nicht, wenn Du ziemlich gut bist.

Als generelle Lektüre empfehle ich zunächst: Quicksort ? Wikipedia

Wir sollen ein Zahlenfeld, das mit beliebigen Zahlen gefüllt wird, mit dem Sortierverfahren "Quicksort" sortieren. Dabei sollen wir das entsprechende Programm einmal nicht rekursiv und einmal rekursiv schreiben.

Der Quicksort ist ein Devide-and-Conquer Verfahren, so dass Du ein direktes iteratives Verfahren nicht exakt erzeugen kannst. Meistens werden andere Verfahren gegen Quicksort verglichen, um die praktisch die Komplexität zu bestimmen.

Bis Freitag würde mir erstmal der nicht rekursive Ansatz reichen. Ich brauche aber nicht nur das Programm, sondern klar, ich muss es auch verstehen.

D.h. jemand soll Dir bis Freitag Deine Hausaufgaben machen und Dir dann erklären, wie er es gemacht hat !? Sicherlich nicht !

Die Procedure Quick habe ich ca. so aus dem Internet gezogen. Ich habe versucht sie so gut wie möglich auf mein Programm zu übertragen.

Leider funktioniert es nicht. Ich weiß auch leider nicht, warum!

Das solltest Du auch lassen, sondern Dir selbst anschauen, wie der Quicksort funktioniert. Dann kannst Du es auch erklären.

Ich verstehe auch schon nicht, warum die Procedure mit Variablenübergabe von l und r arbeitet. Die könnte man doch eigentlich pauschal festlegen, wie ichs ja auch in der Procedure Eingabe gemacht habe?

Nein, denn diese ändern sich durch den rekursiven Aufruf für jeden Abstieg innerhalb der Rekursion. Zusätzlich solltest Du Deine Programmiersprache beherrschen. Gerade Pascal ist eine sehr einfache Sprache und die Frage nach "inc" bzw "dec" (Increment und Decrement) sollten Dir geläufig sein, wenn Du einen Algorithmus implementierst.

Schau Dir zunächst den Wikipediaartikel an, der Quicksort besteht aus 2 Teilen, Du unterteilst Dein Datenfeld (Devide) und führst die Sortieroption auf die beiden Teile durch (Conquer) und das nun rekursiv

Phil

[Nick89]

Meine Güte, unfreundlicher geht es auch wirklich nicht?!

Habe ich danach gefragt, dass mir hier irgendwer etwas für mich programmieren soll?! Ich will es ja einfach nur verstehen.

Und ich habe ja nicht sowas gesagt wie: So und so und jetzt macht mal!

Sondern ich hab konkrete Fragen zum Programm gestellt.

Ich dachte, ein Forum ist da um Hilfe zu bekommen bzw. sich auszutauschen. Für dein rummeckern hast du sicherlich ebenso viel Zeit benötigt, die du gebraucht hättest, um mir konstruktiv zu helfen.

Wenn du das nicht möchtest, dann behalt dein Senf doch einfach für dich?!

Das Prinzip von Quicksort habe ich schon verstanden. Die Befehle Inc und Dec habe ich mir mittlerweile auch angeschaut.

Und überleg mal, ich bin Schüler im Gk 12 und kein Informatiker!

Ich habe jetzt auch schon weiter an meinem Programm gearbeitet.

PROGRAM Quicksort;


USES Crt;


CONST

Max = 10;


VAR

Feld                                    :ARRAY[1..Max] OF INTEGER;

Zahlenfeld                              :ARRAY[1..Max] OF INTEGER;

Index, Index2                           :INTEGER;

Zwischenspeicher, Zufallszahl           :INTEGER;

neuezahl, Tausch                        :BOOLEAN;

l, r                                    :INTEGER;



PROCEDURE Eingabe;

   BEGIN

     FOR Index:= 1 TO Max DO

       BEGIN

         REPEAT

           RANDOMIZE;

           Zufallszahl := RANDOM(1000);

           NeueZahl := TRUE;


             FOR Index2:= 1 TO Index DO

               BEGIN

                 IF Zufallszahl = Zahlenfeld[Index2] THEN

                   BEGIN

                     neuezahl:= FALSE;

                   END;

               END;

           UNTIL NeueZahl = TRUE;

         Zahlenfeld[Index] := Zufallszahl;

       END;

     l := 1;

     r := Max;

   END;


PROCEDURE Quick (l, r: INTEGER);

VAR m, v, temp : INTEGER;

  BEGIN

    IF l < r THEN

      BEGIN

        m := (l + r) div 2;

        v := Feld[m];

        Index := l;

        Index2 := r;

        WHILE Index <= Index2 DO

           BEGIN

              WHILE Feld[Index] < v DO

                inc(Index);

              WHILE Feld[Index2] > v DO

                dec(Index2);

                IF Index <= Index2 THEN

                  BEGIN

                     temp := Feld[Index];

                     Feld[Index] := Feld[Index2];

                     Feld[Index2] := temp;

                     inc(Index);

                     dec(Index2);

                  END;

              quick(l,Index2);

              quick(Index,r);

          END;

      END;

  END;



PROCEDURE Ausgabe;

  BEGIN

     FOR Index := 1 TO Max DO

       BEGIN

         WRITE (Feld[Index]);

         WRITELN;

       END;

  END;


BEGIN

  Clrscr;

  Eingabe;

  Ausgabe;

  READLN;

  Quick(l, r);

  Ausgabe;

  READLN;

END.

[/php]

Funktioniert mittlerweile auch. Nur bei der Eingabe der Zufallszahlen gibt der mir auch negative Zahlen aus im 5-stelligen Bereich, obwohl ich es auf 1000 beschränkt habe. Im letzten Programm hat das so funktioniert. Entdeckt jemand einen Fehler? Komischerweise gibt er auch bei jedem Durchlauf die gleichen Zahlen aus...

Sehr merkwürdig.

Bearbeitet 25. Mai 2009 von grueni

[Nick89]

EDIT:

Okay, funktioniert doch nicht ganz, die 4 Stelle wird MANCHMAL (?!) nicht mitsortiert.

Ich habe es jetzt auch weitestgehen tatsächlich verstanden. Aber wo der Fehler liegt, weiß ich trotzdem nicht .