iteratives Quicksort in Turbo-Pascal!

Amadeus · Hält's aus hier Beiträge: 2

Hallo Commmunity.

Ich bin neu hier und hoffe, mir kann hier geholfen werden.
Ich bin in der 12. und wir haben in Informatik die Aufgabe bekommen, Quicksort rekursiv und iterativ (also nicht rekursiv) zu programmieren. Mit der Version, die eine Rekursion benutzt hatte ich keine Probleme. Beim iterativen Verfahren komme ich allerdings nicht weiter.

Ich habe hier einen Lösungsansatz gefunden, aber der scheint in Turbo-Pascal nicht zu funktionieren, weil die Befehle wie push()/stackinit nicht erkannt werden

:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:

PROGRAM Quicksort;

USES Crt;

CONST
Max = 10;

VAR
Feld                                    :ARRAY[1..Max] OF INTEGER;
Index, Index2                           :INTEGER;
Zwischenspeicher, Zufallszahl           :INTEGER;
Tausch                                  :BOOLEAN;
l, r                                    :INTEGER;


PROCEDURE Eingabe;
   BEGIN
     FOR Index:= 1 TO Max DO
       BEGIN
         WRITELN ('Geben Sie bitte einen Inhalt für den Index ',Index,' ein:');
         READLN (Feld[Index]);
       END;
   END;


PROCEDURE Quick;
Var m, v, Zwischen :INTEGER;
BEGIN
  l := 1;
  r := Max;
  stackinit;
  push (l);
  push (r);
  REPEAT
    IF l <= r THEN
    BEGIN
      m := (l + r) div 2;
      v := Feld[m]
      Index := links;
      Index2 := rechts;
      WHILE Index <= Index2 DO
        BEGIN
          WHILE Feld[Index] < v DO
            inc(Index);
          WHILE Feld[Index2] > v DO
            dec(Index2);
            IF Index <= Index2 THEN
              BEGIN
                Zwischen := Feld[Index];
                Feld[Index] := Feld[Index2];
                Feld[Index2] := Zwischen;
                inc(Index);
                dec(Index2);
              END;
      IF (Index – l) > (r - Index) THEN
        BEGIN
          push (l);
          push (Index - 1);
          l := Index + 1;
        END
        ELSE
          BEGIN
            push (Index + 1);
            push (r);
            r := Index – 1;
          END
          ELSE
            BEGIN
              r := pop;
              l := pop;
            END;
  UNTIL stackempty;
END;


PROCEDURE Ausgabe_a;
  BEGIN
     WRITE ('Das Zahlenfeld, dass sortiert werden soll:');
     WRITELN;
     FOR Index := 1 TO Max DO
       BEGIN
         WRITE (Feld[Index],'  ');
       END;
  END;

PROCEDURE Ausgabe_b;
  BEGIN
     WRITELN;
     WRITELN;
     WRITE ('Das sortierte Zahlenfeld:');
     WRITELN;
     FOR Index := 1 TO Max DO
       BEGIN
         WRITE (Feld[Index],'  ');
       END;
  END;


BEGIN
  Clrscr;
  Eingabe;
  Clrscr;
  Ausgabe_a;
  READLN;
  Quick;
  Ausgabe_b;
  READLN;
END.

Hier noch meine rekursive Version:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:

PROGRAM Quicksort;

USES Crt;

CONST
Max = 10;

VAR
Feld                                    :ARRAY[1..Max] OF INTEGER;
Index, Index2                           :INTEGER;
Zwischenspeicher, Zufallszahl           :INTEGER;
neuezahl                                :BOOLEAN;
l, r                                    :INTEGER;


PROCEDURE Eingabe;
   BEGIN
     FOR Index:= 1 TO Max DO
       BEGIN
         WRITELN ('Geben Sie bitte einen Inhalt für den Index ',Index,' ein:');
         READLN (Feld[Index]);
       END;
   END;


PROCEDURE Quick (l, r  :INTEGER);
VAR m, v, Zwischen  :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
                     Zwischen := Feld[Index];
                     Feld[Index] := Feld[Index2];
                     Feld[Index2] := Zwischen;
                     inc(Index);
                     dec(Index2);
                  END;
              quick(l, Index2);
              quick(Index, r);
          END;
      END;
  END;


PROCEDURE Ausgabe_a;
  BEGIN
     WRITE ('Das Zahlenfeld, dass sortiert werden soll:');
     WRITELN;
     FOR Index := 1 TO Max DO
       BEGIN
         WRITE (Feld[Index],'  ');
       END;
  END;

PROCEDURE Ausgabe_b;
  BEGIN
     WRITELN;
     WRITELN;
     WRITE ('Das sortierte Zahlenfeld:');
     WRITELN;
     FOR Index := 1 TO Max DO
       BEGIN
         WRITE (Feld[Index],'  ');
       END;
  END;

BEGIN
  Clrscr;
  Eingabe;
  Clrscr;
  Ausgabe_a;
  l := 1;
  r := Max;
  READLN;
  Quick(l, r);
  Quick(l, r);
  Ausgabe_b;
  READLN;
END.

Könnte mir jemand einen Lösungsansatz liefern? Ich bin echt aufgeschmissen

.
Unverschämtheit, was unser Info-Lehrer da von uns verlangt. Bei uns im Kurs hat keiner eine Ahnung, weil er nichts richtig erklärt (wahrscheinlich kann er's nicht mal selbst!).

Ich hoffe, ihr könnt mir helfen. Ich wäre euch sehr dankbar!

Liebe Grüße, Amadeus

Moderiert von Christian S.: Code- durch Delphi-Tags ersetzt
Moderiert von Narses: Überflüssige Zeilenumbrüche/Leerzeilen entfernt.

Horst_H · Verfasst: So 07.06.09 20:48

Hallo,

wo hast Du denn den Code-Schnipsel her.
Du verwendest StackInit und Push und Pop und diese Prozeduren/Funktionen sind nirgendwo deklariert oder eine Unit, die das bewerktstelligen könnte, eingebunden.

Also erstelle Dir doch einfach einen Stack als eine Klasse oder als record.

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:

type
  TStackinhalt = integer; {zum Beispiel}
  tStack = record 
             StackInhalt : Array of [0..99] of TStackinhalt;{In Delphi ein dynamisches array möglich}
             TopOfStack  : integer;{-1..99= Low(StackInhalt)-1..High(StackInhalt)// oft TOS genannt}
             IsEmpty     : boolean;
           end;

procedure Stackinit(MeinStack:tStack);
begin
With MeinStack do
  begin
  TopOfStack := 0;
  IsEmpty := (TopOfStack= 0);{true;}
  end;
end;
          
procedure StackPush(MeinStack:tStack,Wert:TStackInhalt);
begin
With MeinStack do
  begin
  Stackinhalt[TopOfStack]:= Wert;
  inc(TopOfStack);
  If TopOfStack > High(StackInhalt) then
    Gib_Alarm;(oder vergrößere das Feld dynamisch }
  IsEmpty := false;
  end;
end;   
function StackPop(MeinStack:tStack;var Wert:TStackInhalt):boolean;
begin
With MeinStack do
  begin
  Dec(TopOfStack);
  IsEmpty := TopOfStack = 0;
  IF IsEmpty then
    {Hier will jemand mehr abholen , als er hineingegeben hat } 
    begin
    Stackpop := false; 
    exit;
    end;
  Stackinhalt[TopOfStack]:= Wert;
  Stackpop := true; 
  end;
end;

Gruß Horst

alzaimar · Verfasst: So 07.06.09 21:46

Wenn Du verstanden hast, wie der rekursive Quicksort funktioniert, dann sollte Dir die iterative Variante nicht schwerfallen.

1. Stell Dir eine Art 'ToDo'-Liste vor. Diese ToDo-Liste enthält die noch zu sortierenden Teillisten.
2. Die ToDo-Liste enthält zunächst nur ein Element [0,N-1] wobei N die Länge der zu sortierenden Liste ist.
3. Solange die ToDo-Liste nicht leer ist, führe die folgenden Schritte aus:
3.1. Entferne das oberste Element der ToDo-Liste ==> [L,R]. Dieses Intervall bezeichnet die zu sortierende (Teil)-Liste
3.2. Wenn L >= R, fahre mit 3 fort.
3.3. Wenn L = R-1, vertausche Element[L] mit Element[R], falls E[L]>E[R] und fahre mit 3 fort.
3.4. Führe die Partitionierung der TeilListe [L,R] in in zwei Teillisten [L,M] und [M+1,R] durch (Pivotelement wählen, durchlaufen, vertauschen etc.).
3.5 Füge die beiden Zeillisten [L,M] und [M+1,R] in die ToDo-Liste ein.

_________________
Na denn, dann. Bis dann, denn.

Amadeus · Hält's aus hier Beiträge: 2

Also, danke erstmal für die sehr schnellen Antworten.
Aber doch, die irevative Variante fällt mir sehr schwer!

Gibt es irgendeinen Weg, der auch ohne dieses Stack-Gedöns funktioniert? Also, ich weiß einfach nicht, was unser Lehrer erwartet. Wir sind im Grundkurs Informatik! Weder bekamen wir erklärt, was Elemente sind, noch Stacks, und und und.

Also, wenn man das auf eine noch verständlichere Weise hinbekäme, wäre das göttlich

!

Danke danke danke für eure Hilfe!

LG Amadeus

Moderiert von Narses: Überflüssige Zeilenumbrüche/Leerzeilen entfernt.

Narses · Verfasst: Mo 08.06.09 01:49

Moin und

im Forum!

Amadeus hat folgendes geschrieben :

Gibt es irgendeinen Weg, der auch ohne dieses Stack-Gedöns funktioniert?

Der Stack ist eine Möglichkeit, die von user profile icon

alzaimar genannte "To-Do-Liste" abzubilden. Da gibt es sicher auch noch andere Varianten, aber ganz ohne einen Speicher, der die noch zu verrichtende Arbeit nachhält, wird das nicht gehen (das geht auch beim rekursiven Ansatz nicht, nur da wird das über den automatisch verwalteten Stack gemacht). :nixweiss:

Amadeus hat folgendes geschrieben :

Also, ich weiß einfach nicht, was unser Lehrer erwartet. Wir sind im Grundkurs Informatik! Weder bekamen wir erklärt, was Elemente sind, noch Stacks, und und und.

Tja, entweder der Lehrer hat tatsächlich nix dazu erklärt, dann könnte ich mir vorstellen, dass du/ihr es einfach nicht schaffen sollt - eine didaktisch eher zweifelhafte Methode, "Aufmerksamkeit" zu erzeugen...

Oder aber er hat es erklärt, und du hast es (warum auch immer) nicht mitbekommen... :zwinker:

In diesem Fall frage ich mich dann immer wieder, warum man ein Fach wählt, für das man sich nicht interessiert (noch dazu Informatik, was keine Pflichtbindung abdeckt)... :gruebel:

cu
Narses

_________________
There are 10 types of people - those who understand binary and those who don´t.

Delphi-Laie · Verfasst: Di 30.06.09 22:47

Die Zuhilfenahme des Sedgewicks Algorithmenbuches und längeres Probieren führten zu u.a. (bei mir) funktionierendem Code für ein nichtrekursives Quicksort. Scheint tatsächlich (= "gefühlt") noch etwas schneller als mit der Rekursion zu sein.

Alle Einzelvariablen sind irgendwelche Integerwerte, und p muß ein ausreichend dimensioniertes Integer-Array sein.

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:

l:=1;r:=Elementeanzahl;p:=2;
  repeat
  if r>l then
    begin

    //Begin Partitionierung
    i:=l;j:=r;
    x:=Menge[j];//Pivot
    while i<=j do
      begin
      while Menge[i]<x do inc(i);
      while Menge[j]>x do dec(j);
      if (i<j) {and (Menge[i]>Menge[j])} then tausche(i,j);
      if i<=j then
        begin
        inc(i);
        dec(j)
        end
      end;
    //Ende Partitionierung

      {ab hier wird folgendes simuliert bzw. nachgebildet:
      Quicksort(l,j);
      Quicksort(i,r)}

    if (j-l)>(r-i) then //linke Teilmenge größer als rechte und wird abgelegt, i ist das linkeste Element
      begin
      stack[p]:=l;
      stack[succ(p)]:=j;
      l:=i
      end
    else //rechte Teilmenge größer als linke  wird abgelegt, j ist das rechteste Element
      begin
      stack[p]:=i;
      stack[succ(p)]:=r;
      r:=j
      end;
    inc(p,2)
    end
  else //r>l
    begin
    dec(p,2);
    l:=stack[p];
    r:=stack[succ(p)]
    end
  until p=0

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme