myJava.rwp

Sortieralgorithmen

Übersicht und Vergleich verschiedener Sortieralgorithmen

Elementare Sortierverfahren machen keine Annahmen bei der Datenstruktur.

Sie haben daher eine hohe Komplexität, nämlich O(N²)

 

Verfahren: Selection Sort, Insertion Sort, Shell Sort, Bubble Sort

 
 

Spezielle Sortierverfahren nutzen bestimmte Eigenschaften von Datenstrukturen aus

und erreichen dadurch geringere Komplexität, z.B. O(N * log(N))

 

Verfahren: Quick Sort, Heap Sort, Merge Sort, Radix Sort

 
 

Die Laufzeitkomplexität messen wir durch

die Anzahl C von Schlüsselvergleichen (Comparisons) und

die Anzahl M von Item-Bewegungen (Movements)

 

Sortverfahren heißen stabil, wenn sie die Reihenfolge von Items mit gleichem Schlüssel nicht verändern.

Wenn z.B. eine Notenliste zunächst nach Alphabet und dann nach Note sortiert wird, soll anschließend Namen mit gleicher

Note trotzdem noch alphabetisch geordnet sein (= stabil)-

 

Speicherbedarf

Stabilität

Datenstruktur

Vorsortierung

Laufzeitverhalten

Anwendung

             

Selection Sort

in-situ-Verfahren

nicht gewährleistet

Array, Liste

keine Auswirkung

Cmin(N) = Cmax(N) =

günstig, wenn

       

auf die Laufzeit

Cav(N) = O(N²)

Item-Transporte

         

Mmin(N) = Mmax(N)=

aufwendig sind

         

Mav(N) = 3(N-1)

 

Insertion Sort

in-situ-Verfahren

ist gewährleistet

Array, Liste

wirkt positiv, wenn

Cmin(N) = O(N)

als Sub-Methode

       

der globale Sortier-

Cmax(N) = Cav(N)=O(N²)

bei Shell-Sort

       

zustand gut ist

Mmin(N) = O(N)

 
         

Mmax(N) = Mav(N) = O(N²)

 

Shell Sort

in-situ-Verfahren

nicht gewährleistet

Array

wirkt sich nur für die

O(N*log²(N)) für

nur noch von

       

Teilprozesse

Inkremente der Form

akademischem

       

positiv aus

2^p 3^q

Interesse

Bubble Sort

in-situ-Verfahren

ist gewährleistet

Array, Liste

wirkt positiv, wenn

Cmin(N) = O(N)

nur innerhalb anderer

       

der globale Sortier-

Mmin(N) = O(N)

Verfahren,

       

zustand gut ist

Cmax(N) = Mmax(N) =

z.B. Quicksort

         

Cav(N) =Mav(N) = O(N²)

 

Quicksort

in-situ-Verfahren,

nicht gewährleistet

Array

globale Vorsortierung

Cav(N) = Cmin(N) =

schnellstes internes

 

aber zusätzlich

   

wirkt sich eher

O(N log(N))

Sortierverfahren

 

Speicher zur

   

negativ aus

Cmax(N) = O(N²)

 
 

Verwaltung der

     

Mav(N) = Mmin(N) =

 
 

Teilaufträge not-

     

O(N log(N))

 
 

wendig (max O(N)

     

Mmax(N) = O(N²)

 
 

Speicherplätze

         

Heap Sort

in-situ-Verfahren

nicht gewährleistet

Array

es gibt Modifikationen

Cmax(N) = O(N log(N))

Einzige worst case-

       

die sie nutzen,

Mmax(N) = O(N log(N))

optimale in-situ-

       

z.B. Smooth Sort

 

Methode

Merge Sort

2 * N

ist gewährleistet

Array, Liste

wird beim natür-

Cav(N) = Cmin(N) =

worst case-optimale

       

lichen 2-Wege

Cmax(N) = O(N log(N))

Methode

       

MergeSort

Mav(N) = Mmin(N) =

 
       

ausgenutzt

Mmax(N) = O(N log(N))

 

Radix

in-situ-Verfahren

nicht gewährleistet

Array

keine Auswirkung

n=Schlüssel-Länge

schlecht für wenige

Exchange Sort

     

auf die Laufzeit

Cmax(N) = O(n * N)

Items mit langen

         

Mmax(N) = O(n * N)

Schlüsseln

Sortieren durch

O(N) zusätzlicher

ist gewährleistet

Array, Liste

keine Auswirkung

O(N * log(N))

Die Komplexität

Fachverteilen

Platz erforderlich

   

auf die Laufzeit

 

O(N * log(N)) gilt für

           

kurze Schlüssel und

           

wenige Ziffern im

           

Vergleich zur

           

Listenlänge