Wenn man einmal durchgeblickt hat ist quicksort auch relativ einfach einzuprägen, da dieser ein recht simples System hat, und es ist der Schnellste Sortieralgorythmus, im Gegensatz zu anderen z.B. Bubblesort aber instabil
Quicksort ist definitiv nicht der schnellste Algorithmus, Worst Case ist O(n^2). Space Complexity kann auch O(n * log(n)) werden.
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.
Quicksort ist definitiv nicht der schnellste Algorithmus, Worst Case ist O(n^2). Space Complexity kann auch O(n * log(n)) werden.
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.
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:
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.
Könnten wir uns bitte auf den Begriff "Algorithmus" einigen? :|
Der schnellste Algorithmus ist der, der verschiedene Algorithmen kombiniert, um auf verschiedene Fälle reagieren zu können, siehe Timsort oder Introsort.
Hier sind die Sortieralgorithmen Insertionsort, Selectionsort, Bubblesort und Quicksort sehr leicht anhand von vielen praktischen Beispielen erklärt, kannst ja da mal durchblättern:
Es gibt aber noch viele weitere Sortieralgorithmen, alle mit ihren individuellen Vor- und Nachteilen.
Der schnellste mir bekannte Sortieralgorithmus, ist Radixsort, da dieser in O(n*m) sortiert und meistens nicht nur theoretisch, sondern auch tatsächlich schneller ist. Da n hierbei die Anzahl der Elemente ist und m die Anzahl der Zeichen.
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.
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.
Hier ist ein gutes Video das ich vor einem Jahr entdeckt habe. Hier werde 3 verschiedene Methoden verglichen. Ist zwar auf Englisch aber dafür gut erklärt.
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.
huh ?
Quote:
Originally Posted by snow
Quicksort ist definitiv nicht der schnellste Algorithmus, Worst Case ist O(n^2). Space Complexity kann auch O(n * log(n)) werden.
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.
Der schnellste mir bekannte Sortieralgorithmus, ist Radixsort, da dieser in O(n*m) sortiert und meistens nicht nur theoretisch, sondern auch tatsächlich schneller ist. Da n hierbei die Anzahl der Elemente ist und m die Anzahl der Zeichen.
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.
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.
Radix-Sort kann allerdings nicht in-place und stabil zur gleichen Zeit sein und ist daher in den meisten Fällen ungeeignet. Soweit ich weiß, lässt sich zeigen, dass es keinen in-place Algorithmus geben kann, der eine bessere Laufzeit als O(n*log2(n)) hat.
Edit: Ah ok, die Schranke bezieht sich auf vergleichsbasierte Verfahren.
Sortieralgorithmus
