> Home
> Algorithmen
> Datenstrukturen
> Probleme
> Highlights
> Themen
> Mindmaps
> Aufgaben
> Programmierung
> Facharbeit
> Abitur
> Projekte
> Informatik-AG
> News
> Impressum
> email
|
|
Sortieralgorithmen
Sortieralgorithmen gehören zu den am häufigsten in der Informatik vorkommenden
Algorithmen.
Entsprechend intensiv hat man sich mit der Problematik des
Sortierens beschäftigt.
Definition
Unter Sortieren versteht man die Umordnung einer Folge von Objekten
a1, a2, ..., an mit n>= 1
in eine Folge
ai1, ai2, ..., ain,
so dass für eine gegebene Ordnungsrelation
aij<=aij+1 für j=1,...,n-1
gilt.
In der sortierten Folge können im Sinne der Ordnungsrelation gleichrangige
Objekte vorkommen. Man spricht von einem stabilen Sortierverfahren, wenn
die relative Reihenfolge dieser gleichrangigen Objekte durch den Sortiervorgang
nicht verändert wird.
Objekte
Die oben genannte Definition behandelt Objekte allgemeiner Art und eine
Ordnungsrelation, die für diese Objekte erklärt ist. Bei den im Folgenden
dargestellten Algorithmen, möchten wir davon ausgehen, dass die Objekte durch
die Elemente eines Array (Datenstruktur Feld) repräsentiert werden.
Die folgende Abbildung stellt ein zehnelementiges Array mit Einträgen des
Datentyps positive ganze Zahl dar.
| Index: |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
| Inhalt: |
13 |
102 |
55 |
3 |
22 |
1024 |
333 |
7 |
11 |
507 |
Algorithmen
Im Folgenden sollen zunächst einige naive Sortieralgorithmen vorgestellt werden,
deren Laufzeit quadratisch, also O(n2) ist,
wenn n die Länge der Eingabe ist.
Minsort
Bei diesem Algorithmus wird die Idee der Minimumsuche verwendet.
Zunächst wird das Minimum der gesamten Folge gesucht. Dieses Minimum wird danach
mit dem ersten Element ausgetauscht. Dann wird die Minimumsuche auf die um das
erste Element verkürzte Folge angewendet. Das hier gefundene Minimum wird mit
dem zweiten Element ausgetauscht. So verfährt man immer weiter, verkürzt die Folge
für die Minimumssuche, während die sortierte Folge immer größer wird.
Der Algorithmus lässt sich entsprechend folgendermaßen formulieren:
function minsort(array a)
for i from 1 to n-1 do
min := a[i]
pos := i
for j from i+1 to n do
begin
if a[j]<= min then
begin
min := a[j]
pos := j
end
tausche(a[i],a[pos])
end
end of function minsort
Bubblesort
Bubblesort ist ebenfalls ein naiver Algorithmus, der nach einem einfachen Prinzip arbeitet.
Die Folge wird vom Anfang bis zum Ende durchlaufen und dabei immer paarweise benachbarte Folgenglieder verglichen.
Stehen sie in falscher Reihenfolge, so wird getauscht.
Das wird so lange wiederholt, bis bei einem Durchlauf kein Tausch mehr vorgenommen wurde.
Dann ist die Folge sortiert und das Verfahren kann beendet werden.
function bubblesort(array a)
repeat
getauscht := false
for i from 1 to n-1 do
begin
if a[i]< a[i+1] then
begin
vertausche(a[i],a[i+1])
getauscht := true
end
end
until getauscht = false
end of function bubblesort
Es gibt noch zahlreiche andere Sortieralgorithmen mit quadratischer Laufzeit,
die alle leicht zu implementieren sind.
Als einen Algorithmus mit deutlich besserem Laufzeitverhalten im Mittel stellen
wir nun Quicksort vor. Dieser Algorithmus erreicht die theoretisch beste Laufzeit von
O(n log n) im average-case, im worst case verhält er sich ebenfalls quadratisch.
Quicksort ist ein rekursives Verfahren das das divide and conquer Prinzip umsetzt.
Quicksort
procedure quicksort(array a, int links, rechts)
if rechts-links >=1 then begin
wähle ein Element p aus a[links..rechts]
notiere index von p als q
ordne a[links..rechts] so um, dass alle Elemente
die kleiner als p sind links angeordnet werden und alle Elemente
die größer als p sind rechts eingeordent werden.
quicksort(links,q-1)
quicksort(q+1,rechts)
end
end of procedure quicksort
Es gibt verschiedenen Möglichkeiten das mittlere Element p (Pivotelement) zu wählen.
Die einfachste (deterministische) Variante wäre p:=a[links]. Im worst case gilt dann in
jedem rekursiven Aufruf q=links (oder q=rechts), so dass im ersten Aufruf von quicksort
n-1 Vergleiche notwendig sind, im zweiten Durchlauf entsprechend n-2 Vergleiche usw.
Wir kommen damit zu einer worst case Komplexität von ((n-1)n)/2, also O(n2).
Die Analyse der average-Komplexität ist sehr viel aufwendiger und kann der entsprechenden Literatur entnommen werden.
Sie beträgt, wie bereits erwähnt, O(n log n).
|
|