Jein, Quicksort ist der schnellste, es gibt keinen sortieralgorythmus der faktoriell schneller arbeitet, nur er ist in bestimmten Fällen langsamer als andere, Worst case wie du es so schön genannt hast.Quote:
Quicksort ist definitiv nicht der schnellste Algorithmus, Worst Case ist O(n^2). Space Complexity kann auch O(n * log(n)) werden.
Du solltest deinen Algorithmus auch mit mehr als 3 Werten prüfen. Du hast n Durchläufe (best, average und worst case), damit kannst du ein Array nicht vollständig sortieren.Quote:
Pseudocode:
array = {5,2,5}
for(var x=0;x<arraylenght-1;x++){
if(array[x]>array[x+1])
{
tmp = array[x]
array[x] = array[x+1]
array[x+1] = tmp
}
}
Könnten wir uns bitte auf den Begriff "Algorithmus" einigen? :|Quote:
Jein, Quicksort ist der schnellste, es gibt keinen sortieralgorythmus der faktoriell schneller arbeitet, nur er ist in bestimmten Fällen langsamer als andere, Worst case wie du es so schön genannt hast.
Wennschon dennschon:Quote:
program RndSort;
{$MODE OBJFPC}{$H+}
uses
SysUtils, Classes;
procedure RandomSort(lst1: TList);
var
rnd: Integer;
lst2: TList;
function Sorted(lst: TList): Boolean;
var i: Integer;
begin
Sorted:=True;
for i:=0 to lst.Count-2 do
if Integer(lst[i]^)>Integer(lst[i+1]^) then
begin
Sorted:=False;
break;
end;
end;
begin
lst2:=TList.Create;
try
repeat
While lst1.Count>0 do
begin
rnd:=Random(lst1.Count);
lst2.Add(lst1[rnd]);
lst1.Delete(rnd);
end;
lst1.AddList(lst2);
lst2.Clear;
until sorted(lst1);
finally
lst2.Free;
end;
end;
var
Liste: TList;
i: Integer;
maxCount: Integer;
tmpInt: PInteger;
begin
Randomize();
Liste:=TList.Create;
try
if ParamCount>0 then
MaxCount:=StrToInt(ParamStr(1))
else
ReadLn(MaxCount);
for i:=0 to MaxCount-1 do
begin
new(tmpInt);
tmpInt^:=Random(100);
Liste.Add(tmpInt);
end;
RandomSort(Liste);
for i:=0 to Liste.Count-1 do
WriteLn(IntToStr(Integer(Liste[i]^)));
finally
for i:=0 to Liste.Count-1 do
Dispose(PInteger(Liste[i]));
Liste.Free;
end;
end.
|
|
Quote:
den man auch auswendig lernen kann?
[...]
huh ?Quote:
Kann mich dem nur anschließen.Quote:
Merge sort - Wikipedia, the free encyclopedia ist der Boss, verdammt einfach aber verdammt effizient mit O(n * log(n)) im Average und Worst Case. Wer Rekursion nicht verstanden hat, hat aber nicht nur Rekursion nicht verstanden, sondern auch nicht den Merge Sort.
Timsort - Wikipedia, the free encyclopedia ist für reale Anwendungen optimiert, aber ein bisschen komplexer programmiert.
Insertion sort - Wikipedia, the free encyclopedia gibt es auch noch, ist relativ einfach zu implementieren.
Wenn du dir mal aufmerksam den Vorschlag von warfley durchliest, wirst du feststellen, dass der Vorschlag nicht ernst gemeint ist :)Quote:
huh ?
Das ist der random sort Algorithmus, setzt die Elemente in eine zufällige Reihenfolge bis es sortiert ist. Ich finde das kann man einfach lernenQuote:
Die innere Schleife beim String-Vergleich (bzw. der Berechnung des Schlüssels) hat nichts mit Radix-Sort zu tun (hast du ja auch in einem Satz gesagt) und hat deshalb sowieso nichts in der Bewertung des Algorithmus zu suchen. Normalerweise nimmt man da der Einfachheit halber ohnehin Zahlen und keine Strings, damit der Vergleich nicht nur theoretisch, sondern auch praktisch als atomarer Schritt gewertet werden kann. Daran ist nichts schwammig.Quote:
Rein theoretisch kann man dabei wieder auf O(n^2) kommen, da man aber meistens eine obere Grenze für die Zeichenlängen angeben kann, ist m konstant und damit fällt es aus der O-Notation raus.
Auf den ersten Blick erscheint das etwas "unfair" den anderen Sortieralgorithmen gegenüber, tatsächlich "missachtet" man aber bei allen Sortierverfahren aber die Tatsache, dass man wenn man zwei Strings vergleicht immer jedes Zeichen einzeln vergleichen muss (bei reinen Zahlen sieht das wieder anders aus). Daher kann man mit Recht sagen:
Radixsort sortiert Strings in O(n) und ist damit der schnellste Algorithmus zum Sortieren von Strings und Zahlen "immerhin" in maximal O(n*m), wobei m hier dann wieder beschränkt sein muss (weil man nicht unendlich viel Speicher hat), also käme man theoretisch wieder auf O(n), ist aber eine sehr "schwammige" Begründung".
Abgesehen davon ist er nicht schwer zu programmieren, da das Grundprinzip recht einfach ist.
Bucketsort ist auch ganz nett:
Bucketsort ? Wikipedia