Quicksort ist zu langsam?

[tr909]

Moin.

Evtl. wäre ja mal jemand so nett einen Blick auf folgenden Quicksort zu werfen. Das sortieren funktioniert richtig, nur ist es sehr langsam.


Der Aufruf erfolgt mit QuickSort(0, length(SortString));
SortString ist ein String ;)

Code:

procedure TfrmSortAlg.QuickSort(l, r: integer);
var
  i, j: Integer;
  temp: char;
begin
  if (r > l) then
  begin
    i := l - 1;
    j := r;
    repeat
      repeat i := i + 1 until SortString[i] >= SortString[r];
      repeat j := j - 1 until SortString[j] <= SortString[r];
      if (j > i) then
      begin
        temp := SortString[i];
        SortString[i] := SortString[j];
        SortString[j] := temp;
      end;
    until (j <= i);
    temp := SortString[i];
    SortString[i] := SortString[r];
    SortString[r] := temp;
    quicksort(l, i - 1);
    quicksort(i + 1, r);
  end;
end;

Gruß
tr909

[Quake]

Was soll denn da sortiert werden? Die Zeichen in SortString?
Auf den ersten Blick würde ich sagen, das ist kein Quicksort. Viel zu viele Repeats und dann ruft sich die funktion noch selbst auf. Die Schleifen werden bestimmt eine Million mal aufgerufen oder?

[Sharky]

Hai tr909,

bei den Tutorials hat unser Chef-...Dingens etwas zu Sortieralgos geschrieben.
Eventuell ist das ja interessant für dich.

[Phoenix]

Zitat:

Zitat von Quake

Auf den ersten Blick würde ich sagen, das ist kein Quicksort. Viel zu viele Repeats und dann ruft sich die funktion noch selbst auf.

Was willst Du denn? Ist doch ein Quicksort.
Der Quicksort ist rekursiv, muss sich also selber aufrufen. Und vor dem rekursiven Aufruf wird der String in zwei Teile geteilt. Das Passiert normalerweise in einer extra Funktion, die hat er sich hier gespart und das Partition eben direkt in der Funktion gemacht.

Die Implementierung scheint auf den ersten Blick zu stimmen. Die Frage ist, wie gross ist Deine zu sortierende Datenmenge? Normalerweise ist Quicksort nämlich der im durchschnitt schnellste bekannte Sortieralgorithmus.

[tr909]

Zitat:

Zitat von Quake

Was soll denn da sortiert werden? Die Zeichen in SortString?

Genau.

Zitat:

Zitat von Quake

...und dann ruft sich die funktion noch selbst auf. Die Schleifen werden bestimmt eine Million mal aufgerufen oder?

Liegt daran, das das ein rekursiver Algorithmus ist ;)

Habe das anhand eines Pseudocodes geschreiben.

@Sharky
Ich gucke mal was schäffe geschrieben hat ;)


€Phoenix

Also zum testen habe ich mal

jkloazfhrndud88dkdkdmfnsdoiuwe4895b79348759034c5f0 345b9ß3

in einer Schleife 100000 mal sortieren lassen.

Folgende Ergebnisse habe ich erhalten

Selection Sort ca 900 ms
Insertion Sort ca 35 ms
Bubble Sort ca 30 ms
Quick Sort ca 800 ms


Gruß
tr909

[Quake]

Probier mal das hier

Delphi-Quellcode:

procedure QuickSort(l,r: integer);
var
  i,j: integer;
  TempChar: char;
begin
  i:=l;
  while i<r do
  begin
    j:=i;
    while j>l do
    begin
      if SortString[j]<SortString[j-1] then
      begin
        TempChar:=SortString[j];
        SortString[j]:=SortString[j-1];
        SortString[j-1]:=TempChar;
      end;
      dec(j);
    end;
    inc(i)
  end;
end;

Ich dachte immer das ist QuickSort !??! :gruebel:

[Matze]

Quicksort sollte so ungefair aussehen.

Von den Algorithmen ist bei mir immer Quicksort der schnellste. Versuche mal den Code von dem Link, den ich gerade gepostet habe, vielleicht geht das schneller.

[tr909]

ich werde es nachher mal ausprobieren.
Quicksort sollte ja eigentlich auch mit der schnellste sein.

Danke schonmal für die schnelle Hilfe

Gruß
tr909

[Kroko1999]

Zitat:

Zitat von Quake

Probier mal das hier

Delphi-Quellcode:

procedure QuickSort(l,r: integer);
var
  i,j: integer;
  TempChar: char;
begin
  i:=l;
  while i<r do
  begin
    j:=i;
    while j>l do
    begin
      if SortString[j]<SortString[j-1] then
      begin
        TempChar:=SortString[j];
        SortString[j]:=SortString[j-1];
        SortString[j-1]:=TempChar;
      end;
      dec(j);
    end;
    inc(i)
  end;
end;

Ich glaube zu wissen, dies ist Bubble-Sort!

Ich dachte immer das ist QuickSort !??! :gruebel:

[Quake]

Ok, dann nenne ich die Procedure um in QuakeSort. :lol: