Zum Inhalt springen

Pascal: Programm Quicksort mit Rekursion und ohne!


Nick89

Empfohlene Beiträge

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:

Link zu diesem Kommentar
Auf anderen Seiten teilen

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

Link zu diesem Kommentar
Auf anderen Seiten teilen

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 von grueni
Link zu diesem Kommentar
Auf anderen Seiten teilen

Dein Kommentar

Du kannst jetzt schreiben und Dich später registrieren. Wenn Du ein Konto hast, melde Dich jetzt an, um unter Deinem Benutzernamen zu schreiben.

Gast
Auf dieses Thema antworten...

×   Du hast formatierten Text eingefügt.   Formatierung wiederherstellen

  Nur 75 Emojis sind erlaubt.

×   Dein Link wurde automatisch eingebettet.   Einbetten rückgängig machen und als Link darstellen

×   Dein vorheriger Inhalt wurde wiederhergestellt.   Editor leeren

×   Du kannst Bilder nicht direkt einfügen. Lade Bilder hoch oder lade sie von einer URL.

Fachinformatiker.de, 2024 by SE Internet Services

fidelogo_small.png

Schicke uns eine Nachricht!

Fachinformatiker.de ist die größte IT-Community
rund um Ausbildung, Job, Weiterbildung für IT-Fachkräfte.

Fachinformatiker.de App

Download on the App Store
Get it on Google Play

Kontakt

Hier werben?
Oder sende eine E-Mail an

Social media u. feeds

Jobboard für Fachinformatiker und IT-Fachkräfte

×
×
  • Neu erstellen...