Hi,
hab wieder mal eine Frage zu meiner Facharbeit, da sie aber nichts mit meinem letzten Thread zu tuhen hat, habe ich mich entschlossen, einen neuen aufzumachen.
Diesmal geht es um
Quicksort. Ich habe ihn bereits programmiert und er sortiert auch so wie er soll, aber viel zu langsam!! Ich habe einfach mal ein Integer-Array mit hundert zufälligen Elementen erstellt und Quicksort durchlaufen lassen: Er benötigt sage und schreibe 8 Sekunden! Bubblesort braucht für exakt das gleiche Array (bzw. für die Kopie) nur ca. 2 - 3 sek. Hier mal der Quelltext, wobei er ja eigentlich funktionieren müsste:
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:
| procedure Sort(var value:Array of Integer; b,e:Integer);
procedure Exchange(var valueOne,valueTwo:Integer);
var
valuetemp :Integer;
begin
valuetemp:=valueOne;
valueOne:=valueTwo;
valueTwo:=valuetemp;
end;
var
pivot :Integer;
i :Integer;
j :Integer;
begin
if b<e then
begin
pivot:=value[(b+e) div 2];
i:=b;
j:=e;
repeat
while value[j]>pivot do dec(j);
while value[i]<pivot do inc(i);
if (i<=j) then
begin
exchange(value[j],value[i]);
inc(i);
dec(j);
end;
DrawQuick(value); QuickImage.Refresh until i>j;
if b<j then Sort(value,b,j);
if i<e then Sort(value,i,e);
end;
end; |
Das einzigste was ich mir vorstellen könnte, wäre das zeichnen des Säulendiagramms, aber dass kann eigentlich nicht die Ursache sein, denn das wird bei Bubblesort schließlich auch jedes mal gezeichnet.
Hoffentlich kennt einer von euch die Lösung, sonnst sieht es etwas komisch aus, wenn ich behaupte, Quicksort wär einer der schnellsten Algorithmen und gleichzeitig ist Bubblesort einer der langsamsten aber trotzdem schneller
Moderiert von 
Tino: Überflüssige Zeilenumbrüche entfernt.
