|
You last visited: Today at 20:59
Advertisement
Sortieralgorithmus
Discussion on Sortieralgorithmus within the General Coding forum part of the Coders Den category.
12/30/2014, 21:42
|
#1
|
elite*gold: 138
Join Date: Apr 2012
Posts: 3,495
Received Thanks: 1,769
|
Sortieralgorithmus
Hey,
was ist der einfachste Sortieralgorithmus, den man auch auswendig lernen kann? Als Beispiel, um Zahlen nach der Größe zu sortieren.
|
|
|
12/30/2014, 21:45
|
#2
|
elite*gold: 0
Join Date: Feb 2009
Posts: 1,137
Received Thanks: 572
|
Bubblesort ineffizient aber einfach
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
|
|
|
12/30/2014, 21:53
|
#3
|
elite*gold: 724
Join Date: Mar 2011
Posts: 10,480
Received Thanks: 3,319
|
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.
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.
|
|
|
12/30/2014, 22:03
|
#4
|
elite*gold: 0
Join Date: Dec 2013
Posts: 2,095
Received Thanks: 506
|
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
}
}
|
|
|
12/30/2014, 22:49
|
#5
|
elite*gold: 0
Join Date: Feb 2009
Posts: 1,137
Received Thanks: 572
|
Quote:
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.
|
|
|
12/30/2014, 23:08
|
#6
|
elite*gold: 724
Join Date: Mar 2011
Posts: 10,480
Received Thanks: 3,319
|
Quote:
Originally Posted by Crossside
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
}
}
|
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.
|
|
|
12/31/2014, 00:50
|
#7
|
elite*gold: 0
Join Date: Mar 2013
Posts: 3,184
Received Thanks: 1,317
|
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.
|
|
|
01/01/2015, 15:20
|
#8
|
elite*gold: 77
Join Date: May 2008
Posts: 5,430
Received Thanks: 5,876
|
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.
Bucketsort ist auch ganz nett:
Bucketsort ? Wikipedia
|
|
|
01/04/2015, 20:21
|
#9
|
elite*gold: 0
Join Date: Jan 2009
Posts: 1,160
Received Thanks: 232
|
.
|
|
|
01/05/2015, 15:33
|
#10
|
elite*gold: 0
Join Date: Feb 2009
Posts: 1,137
Received Thanks: 572
|
Quote:
Originally Posted by Delinquenz
.
|
Wennschon dennschon:
Randomsort:
Code:
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.
|
|
|
01/05/2015, 15:54
|
#11
|
elite*gold: 0
Join Date: Nov 2010
Posts: 700
Received Thanks: 507
|
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.
|
|
|
01/05/2015, 16:51
|
#12
|
dotCom
elite*gold: 12400
Join Date: Mar 2009
Posts: 15,865
Received Thanks: 4,375
|
Quote:
Originally Posted by moneypulation
[...]
den man auch auswendig lernen kann?
[...]
|
Quote:
Originally Posted by warfley
[...]
Code:
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
|
Kann mich dem nur anschließen.
|
|
|
01/06/2015, 03:06
|
#13
|
elite*gold: 0
Join Date: Jan 2009
Posts: 1,160
Received Thanks: 232
|
Quote:
Wenn du dir mal aufmerksam den Vorschlag von warfley durchliest, wirst du feststellen, dass der Vorschlag nicht ernst gemeint ist
|
|
|
01/06/2015, 13:23
|
#14
|
elite*gold: 0
Join Date: Feb 2009
Posts: 1,137
Received Thanks: 572
|
Quote:
Originally Posted by Devsome
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 lernen
Und ans Ziel kommt der auch, manchmal sogar ziemlich schnell
|
|
|
01/08/2015, 02:09
|
#15
|
elite*gold: 7110
Join Date: Jun 2009
Posts: 28,904
Received Thanks: 25,394
|
Quote:
Originally Posted by Shadow992
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.
Bucketsort ist auch ganz nett:
Bucketsort ? Wikipedia
|
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.
|
|
|
All times are GMT +1. The time now is 20:59.
|
|