Register for your free account! | Forgot your password?

Go Back   elitepvpers > Coders Den > General Coding
You last visited: Today at 20:59

  • Please register to post and access all features, it's quick, easy and FREE!

Advertisement



Sortieralgorithmus

Discussion on Sortieralgorithmus within the General Coding forum part of the Coders Den category.

Reply
 
Old   #1


 
Moneypulation's Avatar
 
elite*gold: 138
Join Date: Apr 2012
Posts: 3,495
Received Thanks: 1,769
Arrow Sortieralgorithmus

Hey,

was ist der einfachste Sortieralgorithmus, den man auch auswendig lernen kann? Als Beispiel, um Zahlen nach der Größe zu sortieren.
Moneypulation is offline  
Old 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
warfley is offline  
Old 12/30/2014, 21:53   #3

 
snow's Avatar
 
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.
snow is offline  
Thanks
2 Users
Old 12/30/2014, 22:03   #4
 
Crossside's Avatar
 
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
}
}
Crossside is offline  
Old 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.
warfley is offline  
Old 12/30/2014, 23:08   #6

 
snow's Avatar
 
elite*gold: 724
Join Date: Mar 2011
Posts: 10,480
Received Thanks: 3,319
Quote:
Originally Posted by Crossside View Post
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.
snow is offline  
Old 12/31/2014, 00:50   #7
 
Zunft's Avatar
 
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.
Zunft is offline  
Thanks
1 User
Old 01/01/2015, 15:20   #8
 
Shadow992's Avatar
 
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
Shadow992 is offline  
Thanks
1 User
Old 01/04/2015, 20:21   #9

 
Delinquenz's Avatar
 
elite*gold: 0
Join Date: Jan 2009
Posts: 1,160
Received Thanks: 232
.
Delinquenz is offline  
Thanks
1 User
Old 01/05/2015, 15:33   #10
 
elite*gold: 0
Join Date: Feb 2009
Posts: 1,137
Received Thanks: 572
Quote:
Originally Posted by Delinquenz View Post
.
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.
warfley is offline  
Old 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.

supercracker13 is offline  
Old 01/05/2015, 16:51   #12
dotCom
 
Devsome's Avatar
 
elite*gold: 12400
The Black Market: 104/0/0
Join Date: Mar 2009
Posts: 15,865
Received Thanks: 4,375
Quote:
Originally Posted by moneypulation View Post
[...]
den man auch auswendig lernen kann?
[...]
Quote:
Originally Posted by warfley View Post
[...]
huh ?

Quote:
Originally Posted by snow View Post
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.
Kann mich dem nur anschließen.
Devsome is offline  
Old 01/06/2015, 03:06   #13

 
Delinquenz's Avatar
 
elite*gold: 0
Join Date: Jan 2009
Posts: 1,160
Received Thanks: 232
Quote:
huh ?
Wenn du dir mal aufmerksam den Vorschlag von warfley durchliest, wirst du feststellen, dass der Vorschlag nicht ernst gemeint ist
Delinquenz is offline  
Old 01/06/2015, 13:23   #14
 
elite*gold: 0
Join Date: Feb 2009
Posts: 1,137
Received Thanks: 572
Quote:
Originally Posted by Devsome View Post
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
warfley is offline  
Old 01/08/2015, 02:09   #15


 
MrSm!th's Avatar
 
elite*gold: 7110
Join Date: Jun 2009
Posts: 28,904
Received Thanks: 25,394
Quote:
Originally Posted by Shadow992 View Post
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.
MrSm!th is offline  
Thanks
1 User
Reply




All times are GMT +1. The time now is 20:59.


Powered by vBulletin®
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
SEO by vBSEO ©2011, Crawlability, Inc.
This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

Support | Contact Us | FAQ | Advertising | Privacy Policy | Terms of Service | Abuse
Copyright ©2024 elitepvpers All Rights Reserved.