Entwickler-Ecke :: Thema anzeigen - Funktioniert mein Sortier-Algo wie beschrieben?

Hohar - Di 22.11.05 17:00
Titel: Funktioniert mein Sortier-Algo wie beschrieben?

Ich habe folgende Aufgabe gestellt bekommen:
Ein Sortierverfahren funktioniert nach folgendem prinzip:
Die zu sortierenden Elemente [Hier eine Zahlenfolge(52;63;2;45;23;8;10;95;11;3)] sind in einem Feld gespeichert. Ein Element T wird willkürlich ausgewählt. Über zwei Suchindizes wird das Feld von links nach rechts und von rechts nach links durchsucht, bis dabei je eine "Fehlstellung" entdeckt wird, d.h. ein Element von t größer bzw. rechts von t kleiner ist als t. Diese beiden Elemente werden dann vertauscht. Der SUchvorgang bricht ab, wenn sich die beiden Indizes treffen. Nach diesem Vorgang ist das Feld in zwei Teile zerlegt, wobei alle Elemente des linken Teils kleiner sind als t, die rechten größer als t (oder umgekehrt). Auf diese beiden Teile wird anschließend das gleiche Verfahren wieder angewendet.

Aufgabe: Schreibe eine Funktion zu diesem Sortierverfahren!

Ich habe mir hier nen Ausgangsquellcode von quicksort besorgt weil ich selber noch keine Erfahrungen mit quicksort gemacht habe. Deshalb hab ich beide Suchindizes bei den Namen (links, rechts) gelassen. Könnt ihr mir vll helfen und sagen ob in diesem Programm Fehler sind oder es so wie es da steht gar nicht gehen würde. Ich habe wirklich keine Ahnung von Delphi.

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:

  
procedure quick_sort(var anfang, ende: integer);
var links, rechts, t: integer;
begin
 IF ende > anfang THEN
 begin
  links := anfang;
  rechts := ende;
  t := (anfang + ende) DIV 2;
  WHILE links < rechts DO
  begin
   WHILE sortfeld[links] < sortfeld[t] DO
    inc(links);
   WHILE sortfeld[rechts] > sortfeld[t] 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;

Moderiert von Tino: Quote- durch Delphi-Tags ersetzt
Moderiert von Tino: Titel geändert.

digi_c - Di 22.11.05 17:50

Ich weiß nicht genau aber Quicksort oder Bublesort war das doch. Wenn du Qucksort als Ausgang genommen hast und es läuft wird es schon stimmen ;)

Hohar - Di 22.11.05 18:32

das Problem besteht darin ich habe kein Delphi ich muss es handschriftlich amchen habe also keine möglichkeit es zu überprüfen. Deshalb frage ich euch

Horst_H - Di 22.11.05 18:59

Hallo,

was Du da machst laesst sich leicht mit anderen Pascal Compilern auch erledigen.
http://www.webplain.de/turbopascal/downloads.php
Freepascal ist sehr Delphi kompatibel geworden (TStringList etc).

Gruss Horst.

Hohar - Di 22.11.05 20:04

das mit pascal versteh ich nicht kann mir nciht so einer helfen einfahc nur drübergucken ob amn offensichtliche fheler sieht? Es geht wirklich um mein Abi

alzaimar - Di 22.11.05 20:22

Ich glaube, Du rufst falsch auf mal sehen:
Ich sortiere eine Teilliste A zwischen L und R, und zwar so:
Ich definiere ein Pivotelement A[T] = (L+R)/2.
Dann teile ich die Liste in zwei Teile A[L...T-1] und A[T+1...R], und zwar so, das alle Elemente A[L]..A[T-1] < A[T] und alle Elemente A[T+1]..A[R] > A[T] sind. Wenn ich nun die beiden Teile sortiere, dann ist auch meine TeilListe A[L]..A[R] sortiert.

Du kannst mal bei http://www.sortieralgorithmen.de/ vorbeischauen, und unter Quicksort nachschauen. Es gibt diverse Implementierungen, aber ich meine, das eine davon Deiner entspricht.

Probiere es mal mit einer Liste [6,1,5,3,2,8,0]. Das nennt sich Handsimulation und ist ziemlich unbeliebt, da mit Arbeit verbunden. Dafür sieht man Denkfehler.

Hohar - Mi 23.11.05 08:01

naja bei der Seite scheinen die Algorithmen in ner anderen Sprache zu sien also nicht delphi da Blick ich erst recht nicht durch aber egal. Ich werde den Algo mal so zu Papier bringen und hoffen das ich was gutes bekomme, muss ihn bis morgen früh fertig haben. Wenn jemand noch was findet was wirklich flashc ist dann bitte sgat es mir. es hängt viel an dieser Arbeit. besten Dank

Horst_H - Mi 23.11.05 11:40

Hallo,

Hier [http://www.bastisoft.de/pascal/suso.html] kannst Du viele sortieralgorithmen zum direkten Abschreiben finden.
Oder hier [http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/sortalgo.htm] kannst Du Papier und Bleistift mit der Maus ersetzen.

Gruss Horst

Hohar - Mi 23.11.05 12:27

Super dnake Horst das hilft mir wieter :D Dann werde ich mich aml ransetzen und den für meine Bedürfnisse benennen und aufschrieben!