quick Sort

sveno · Beiträge: 40

Hallo.

Ich habe den bubblesort, shakersort, shellsort, selectionsort und insertionsort inzwischen erfolgreich programmiert und bin nun am quick sort. Aber da krieg ichs nicht hin. kann mir jemand sagen wo mein Fehler liegt?

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:

procedure quick_sort(var anfang, ende: integer);
var links, rechts, vergleichswert, zaehlerl, zaehlerr, anfangneu, endeneu: integer;
begin
 vergleichswert := (anfang+ende) DIV 2;
 links := anfang;
 rechts := ende;
 zaehlerr := 0;
 zaehlerl := 0;
 IF ende > 1 THEN
 begin
  WHILE rechts >= links DO
   begin
    WHILE sortfeld[links] < sortfeld[vergleichswert] DO
    begin
     inc(links);
     inc(zaehlerl);
    end;
    WHILE sortfeld[rechts]> sortfeld[vergleichswert] DO
    begin
     dec(rechts);
     inc(zaehlerr);
    end;
    tausche(sortfeld[rechts],sortfeld[links]);
    inc(links);
    dec(rechts);
   end;
   anfangneu := (links-zaehlerl);
   endeneu := (rechts+zaehlerr);
  quick_sort(anfangneu,rechts);

  quick_sort(links,endeneu);

 end;
end;

Gruss Sven

Moderiert von Christian S.: Code- durch Delphi-Tags ersetzt.
Moderiert von Christian S.: Topic aus Sonstiges verschoben am Fr 21.01.2005 um 23:29

Gausi · Verfasst: Sa 22.01.05 00:40

bin nicht sicher, ob das der einzige Fehler ist, aber die Grenzen für den rekursiven Aufruf sind falsch, soweit ich das jetzt überblicke.
Man muss ja den linken Teil und den rechten Teil der Folge rekursiv sortieren. Also von "anfang" bis "mitte" und von "mitte" bis "ende"

markieren

Delphi-Quelltext

1:
2:

quicksort(rechts{+1}, ende); // ende ist der Wert, mit dem die prozedur aufgerufen wurde
quick_sort(anfang,links{-1}); // anfang ist der Wert, mit dem die prozedur aufgerufen wurde

Du musst dich jetzt nur noch darum kümmern, dass das Vergleichselement in keiner der beiden Teilfolgen drin ist. Da kommt dann evtl. noch ein +1 oder -1 in die Grenzen rein, aber das kann ich nicht am Quelltext so schnell sehn.

Edit: Nochwas: Die Behandlung des Pivot-Elements dürfte Probleme machen: Man sollte das zuerst noch hinten vertauschen, und vor den beiden rekursiven Aufrufen wieder in die Mitte setzen.

_________________
We are, we were and will not be.

sveno · Beiträge: 40

Vielen Dank für deine Hilfe:) Was ist ein Pivot Element?

Ich denke mal das mein Algorhitmus ein völliges Chaos war und deswegen hab ichs gerade nochmal komplett neu versucht:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:

procedure TFrmbubble.BtquickClick(Sender: TObject);
var zeit, start: integer;
    cursor: TCursor;
begin
 cursor := screen.Cursor;
 Screen.Cursor := crHourGlass;
 try
  start := 1;
  sortfeld := zufallsfeld;
  starte_zeit(Zeit);
  quick_sort(start,anzahl);
  stoppe_zeit(Zeit);
  anzahl := SpEdAnzahl.Value;
  kopieresortfeldzustrgrd;
  lbmsquick.caption := inttostr(Zeit);
 finally
 Screen.Cursor := cursor;
 end;
end;

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:

procedure quick_sort(var anfang, ende: integer);
var links, rechts, vergleichswert: integer;
begin
 IF ende > anfang THEN
 begin
  links := anfang;
  rechts := ende;
  vergleichswert := (anfang + ende) DIV 2;
  WHILE links < rechts DO
  begin
   WHILE sortfeld[links] < sortfeld[vergleichswert] DO
    inc(links);
   WHILE sortfeld[rechts] > sortfeld[vergleichswert] DO
    dec(rechts);
   tausche(sortfeld[links],sortfeld[rechts]);
   inc(links);
   IF rechts > anfang THEN
    dec(rechts);
  end;

  quick_sort(anfang,rechts);

  quick_sort(links,ende);

 end;
end;

Dieser läuft nun schon vieeel besser als mein erster, er bricht nicht mehr ab und sortiert. Aber es sind noch vereinzelte wenige Ausreisser da, die nicht dahin gehören wo sie hin sollen. Weiss jemand woran das liegt?
Und ich hab noch eine Frage. In der Procedure TFrmbubble.BtquickClick muss ich zuerst den Start der Zahlenfolge, also 1 in einer Variable speichern damit compiliert werden kann. Warum kann ich das nicht direkt so schreiben: quick_sort(1,anzahl)

Gruss Sven

Moderiert von Christian S.: Code- durch Delphi-Tags ersetzt.

Gausi · Verfasst: Sa 22.01.05 12:56

Das Pivotelement ist das Element, mit dem verglichen wird. Hab mal meine Info3-Vorlesung genommen, und den dortigen Java-Code in Pascal übersetzt und die Variablen den deinen angepasst. So gehts:

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:

 procedure quick_sort(anfang, ende: integer);
var links, rechts, vergleichswert: integer;
    pivot:integer;
begin
    IF ende > anfang THEN
    begin
      vergleichswert := (anfang + ende) DIV 2;
      // Pivot-element ans Ende vertauschen
      tausche(sortfeld[ende],sortfeld[vergleichswert]);
      pivot:=sortfeld[ende];

      links := anfang;
      rechts := ende-1;
      repeat
          WHILE (sortfeld[links] <= pivot) 
                AND (links<ende) DO // links darf nicht übers ende rauslaufen
                     inc(links); 
          WHILE (sortfeld[rechts] >= pivot) AND (rechts>anfang) DO
              dec(rechts);
          if (links < rechts) then  
              tausche(sortfeld[links],sortfeld[rechts]);
      until (links >= rechts);
      //Pivot-element in die Mitte tauschen
      tausche(sortfeld[links],sortfeld[ende]);
      // rekursive Aufrufe
      quick_sort(anfang,links-1);
      quick_sort(links+1,ende);
 end;
end;

_________________
We are, we were and will not be.

sveno · Beiträge: 40

So, hab das Programm nach einer anderen Idee neu geschrieben:

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:

procedure quick_sort(var anfang, ende: integer);
var links, rechts, vergleichswert: integer;
begin
 IF ende > anfang THEN
 begin
  links := anfang;
  rechts := ende;
  vergleichswert := (anfang + ende) DIV 2;
  WHILE links <= rechts DO
  begin
   IF (sortfeld[links] >= sortfeld[vergleichswert]) AND (sortfeld[rechts] <= sortfeld[vergleichswert]) THEN
   begin
    tausche(sortfeld[links],sortfeld[rechts]);
    IF links = vergleichswert THEN
     vergleichswert := rechts ELSE
     IF rechts = vergleichswert THEN
      vergleichswert := links;
    IF links < ende THEN inc(links);
    IF rechts > anfang THEN dec(rechts);
   end ELSE
    IF sortfeld[links] >= sortfeld[vergleichswert] THEN dec(rechts) ELSE inc(links);
  end;

  quick_sort(anfang,rechts);

  quick_sort(links,ende);

 end;
end;

Jetzt läufts endlich korrekt

Soo, danke Gausi für deine Hilfe

Ich versuch mich jetzt am Merge-Sort

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme