Startseite » Informatik » Referate » Detailseite
 

  • Suchen - Searching

    1 Suchen (Searching) Das Suchen verkörpert die meistbenutzte Operation neben dem Anlegen. Sogar das Löschen ist eine Erweiterung des Suchens, denn bevor etwas gelöscht werden kann, muss es...Referat Suchen - Searching

    1483 Worte in "deutsch"  als "hilfreich"  bewertet

  • SQL (Datenbank)

    INDEX UND SELECT IN SQL 1. Beispiel DATENBANK create table Ware (Artikel# SmallInt, Bezeichnung CHAR(20), Preis SmallInt, ME CHAR(3), Bestand SmallInt );...Referate SQL (Datenbank)

    1418 Worte in "deutsch"  als "hilfreich"  bewertet

  • Einführung in Word 97

    Microsoft Word 97 ist ein modernes Programm zur Textverarbeitung. Jedoch kann man Word nicht nur zum schreiben von Texten verwenden. Es ist außerdem noch geeignet, um zu zeichnen, Rechnen,...Einführung in Word 97 Referat

    2155 Worte in "deutsch"  als "hilfreich"  bewertet

Sortieralgorithmen


Inhaltsverzeichnis

Einführung

Das Sortieren von Daten ist ein klassisches Problem der Informatik. Die Verwaltung von Datenbanken jedweder Ausprägung erfordert häufig den Einsatz eines effizienten Sortieralgorithmus. Das Wesentliche an einem Sortierverfahren ist natürlich seine Geschwindigkeit. Darum wird jeder der vorgestellten Algorithmen bezüglich seines Aufwands abgeschätzt werden. Die Aufwandsabschätzung ist eher abstrakt und nicht von konkreten Daten oder technischen Systemen abhängig. Darum darf man in der Realität folgende Punkte nicht aus den Augen verlieren:

    Welche Daten sollen sortiert werden? (Integer - Zahlen, Gleitkomma - Zahlen, Zeichenketten, ...) Wie groß ist die Anzahl der zu sortierenden Datensätze? Nach welchen Kriterien soll sortiert werden (z.B. aufsteigend, absteigend, Reihenfolge der Buchstaben eines Zeichensatzes, ...)? => Eine Vergleichsfunktion wird benötigt. Haben die Daten bereits eine (teilweise) Ordnung (zum Beispiel sind sie bis auf Ausnahmen schon sortiert, ...)? Auf welchen Medien soll sortiert werden (Hauptspeicher, Medien mit wahlfreiem Zugriff (Festplatten) oder sequentiellen Zugriff (Bänder))? Wieviel Speicher steht zur Verfügung? Sind doppelte Datensätze erlaubt (z.B. zweimal "Fritz Maier", ...)?

In den nachfolgenden Kapiteln sollen nun Sortierverfahren für den Hauptspeicher betrachtet werden.

Allgemeiner Programmcode

Die folgenden Programmzeilen werden für alle behandelten Sortieralgorithmen verwendet.

Definitionen und Deklarationen

const HighMax = 999999; // Maximale Daten - Arraygröße
type TArray = array [0..HighMax] of integer; // Typ des Daten - Arrays

Hilfs - Procedure

procedure Swap (var i, j: integer);
// Vertauscht die beiden Zahlen i und j
var h: integer;
begin
h:= i;
i:= j;
j:= h;
end;


Selection Sort (Sortiern durch Auswahl)

Beschreibung

    Aus den vorhandenen Daten wird der kleinste Datensatz herausgesucht und mit dem ersten Datensatz vertauscht. Dieses Verfahren wird nun für die übriggebliebenen, noch unsortierten Daten ebenfalls angewandt.

Programmcode

procedure SelectionSort ( var f : TArray; HighIndex : integer ) : string;
var i, j, min : integer;
begin
for i := 0 to HighIndex - 1 // äußere Schleife
do begin
min := i;
for j := i+1 to HighIndex do if f[j] Swap (f[i], f[min]);
end;
end; // SelectionSort

Aufwandsabschätzung

mittlerer - Aufwand:
    Die äußere Schleife wird n - 1 mal durchlaufen. Die innere Schleife wird im Durchschnitt (n - 1)/2 mal durchlaufen.
Daraus folgt der Aufwand
.
worst - case - Aufwand:
Der maximale Aufwand beträgt ebenfalls O(n2).

Sortierdauer



Insertion Sort (Sortieren durch Einfügen)

Beschreibung

    Die Elemente werden der Reihe nach in eine bereits sortierte Folge eingetragen. Dazu wird in der bereits sortierten Folge die richtige Stelle zum Einfügen von rechts her gesucht und gleichzeitig die bereits eingetragenen Elemente um eins nach rechts verschoben. Das neue Element wird dann an der auf diese Weise freigewordenen Position eingefügt.

Programmcode

procedure InsertionSort ( var f : TArray; HighIndex : integer ) : string;
var i, j, v : integer;
begin
for i := 1 to HighIndex // äußere Schleife
do begin
v := f[i];
j := i;
while (j>0) and (f[j - 1]> v) // innere Schleife (zum Einfügen)
do begin
f[j] := f[j - 1];
dec (j)
end;
f[j] := v
end;
end; // InsertionSort

Aufwandsabschätzung

    Die äußere Schleife wird n - 1 mal durchlaufen. Die innere Schleife wird ½ * ½ (n - 1) durchlaufen. (Im Mittel erwarten wir, dass das neue Element in die Mitte des soriterten Bereichs gehört.)
Daraus folgt der Aufwand
.

    Die äußere Schleife wird n - 1 mal durchlaufen. Die innere Schleife wird ½ (n - 1) durchlaufen.
Daraus folgt der Aufwand
.

    Die äußere Schleife wird n - 1 mal durchlaufen. Die innere Schleife wird 1 mal durchlaufen, da jedes neue Element schon am richtigen Platz steht, d.h. das Array war schon aufsteigend sortiert.
Daraus folgt der Aufwand
.

Sortierdauer



Bubble Sort (Sortieren durch Austauschen)

Beschreibung

    Die Daten werden in einer doppelten Schleife abgearbeitet. Die innere Schleife umspannt jeweils den gesamten unsortierten Bereich: Dieser wird iterativ durchgearbeitet. Wenn ein Element größer ist als sein rechter Nachbar, so werden sie miteinander vertauscht. Nach jedem äußeren Schleifendurchlauf wurde der sortierte Bereich am Ende der Daten um mindestens 1 erhöht.

Programmcode

procedure BubbleSort ( var f : TArray; HighIndex : integer ) : string;
var i, j : integer;
begin
for i := HighIndex downto 1 // äußere Schleife
do for j := 0 to i
do if f[j]> f[j+1] then swap (f[j], f[j+1]); // innere Schleife
end; // BubbleSort

Aufwandsabschätzung

mittlerer - Aufwand:
    Die äußere Schleife wird n - 1 mal durchlaufen. Die innere Schleife wird im Durchschnitt (n - 1)/2 mal durchlaufen.
Daraus folgt der Aufwand
.
Der maximale Aufwand beträgt ebenfalls O(n2), da beide Schleifen auch im schlechtesten Fall genauso oft durchlaufen werden. Der Unterschied ist nur die Anzahl der benötigten Tauschvorgänge (im besten Fall ist gar keiner nötig).

Sortierdauer



Merge Sort (Sortieren durch Mischen)

Beschreibung

    Das Verfahren arbeitet rekursiv nach dem Divide & Conquer[1] - Prinzip. Die Folge wird rekursiv bis zur trivilaen Teilfolge der Länge 1 zerteilt (Divide). Diese Teilfolgen werden jeweils durch Merging vereint, die vereinten wiederum. etc. bis zur sortierten Gesamfolge (Conquer). Es wird ein zusätzliches Hilfsfeld Ziel von der gleichen Größe wie die zu sortierende Gesamtfolge benötigt.

Programmcode

procedure MergeSort ( var f : TArray; HighIndex : integer ) : string;

var Ziel : TArray; // Hilfsfeld zum Einsortieren für die Procedure Merge

procedure Merge ( links, mitte, rechts : integer );
var h, i, j, k : integer;
begin
i := links; // Index des linken Teilfeldes
j := mitte + 1; // Index des rechten Teilfeldes
k := links; // Index des (sortierten) Hilfsfeldes

repeat
if f[i] then begin ziel[k] := f[i]; inc (i); end
else begin ziel[k] := f[j]; inc (j); end;
inc (k);
until (i> mitte) or (j> rechts);

if i> mitte
then for h := j to rechts do ziel [k+h - j] := f[h]
else for h := i to mitte do ziel [k+h - i] := f[h];

for h := links to rechts do f[h] := Ziel [h]; // zurückkopieren ins Datenfeld
end; // subproc Merge

procedure rMergeSort (links, rechts : integer);
// rekursiver Teil des MergeSorts
var mitte : integer;
begin
if links then begin
mitte := (links + rechts) div 2;
rMergeSort (links, mitte ); // sortieren des linken Teils
rMergeSort (mitte+1, rechts); // sortieren des rechten Teils
Merge (links, mitte, rechts); // zusammenmischen der beiden Teile
end;
end; // SubProc MergeSort

begin // MergeSort
rMergeSort (0, HighIndex);
end; // MergeSort

Aufwandsabschätzung

Aufwand:
    Die Datenmenge wird in n Teile zerlegt. Dazu sind insgesamt ld(n) Rekursionsschritte notwendig. Im Durchschnitt werden n/2 Elemente miteinander gemischt.

Sortierdauer



Bemerkung

Die etwas seltsame Krümmung der Graphen entsteht dadurch, dass die gemessene Zeit sehr klein ist (nicht einmal eine Sekunde) und die Datenmenge groß. Dadurch ist jede Betriebssystemaktivität wie z.B. Seitenauslagerungen zu sehen.

Radix Exchange Sort (Sortieren durch rekursiven Bitvergleich)

Beschreibung

    Die Daten werden mit einem rekursiven Verfahren (Divide & Conquer) anhand ihrer Bitstruktur sortiert. Daten mit gesetztem n - ten Bit kommen in die rechte Hälfte, die anderen in die linke; für beide Hälften wird das Verfahren rekursiv aufgerufen.

Programmcode

procedure RadixExchangeSort ( var f : TArray; HighIndex : integer ) : string;

function Bit ( z, b : integer ) : integer;
// liefert das Bit mit der Nummer b einer positiven Integerzahl
begin
result := ((z shr b) and 1) // Rausschneiden des Bits b aus der Zahl z
end;

procedure rRadixExchangeSort ( links, rechts, b : integer);
// rekursiver Teil des RadixExchangeSorts
var i, j : integer;
begin
if (links = 0)
then begin
i := links;
j := rechts;
repeat
while (Bit (f[i], b) = 0) and (i while (Bit (f[j], b) = 1) and (i swap (f[i], f[j]);
until i = j;

// Korrigiere Spezialfall, dass alle Elemente nur in d. rechten Hälfte waren:
if Bit (f[rechts], b) = 0 then inc (j);

rRadixExchangeSort (links, j - 1, b - 1);
rRadixExchangeSort (j, rechts, b - 1);
end;
end; // rRadixExchangeSorts

begin // RadixExchangeSorts
rRadixExchangeSort (0, HighIndex, 30);
end; // RadixExchangeSorts

Aufwandsabschätzung

Aufwand:
    In jeder Ebene der Rekursion wird jedes Element betrachtet, d.h. n - Elemente. Die Rekursionstiefe hängt vom Wertebereich (signifikanten Bits) des Schlüssels ab, bei Integerzahlen im Bereich 1 - 100.000 beträgt die Rekusionstiefe ld (100.000) ≈ 17.
Daraus folgt der Aufwand
, wobei N der Wertebereich ist. Da im Allgemeinen der Wertebereich wesentlich größer ist als die Anzahl der Elemente ⇒
.
w.o.

Sortierdauer




Quick Sort (Sortieren durch Zerlegen)

Beschreibung

    Das Verfahren arbeitet nach dem Divide & Conquer - Prinzip. Aus einer zu sortierenden Teilfolge wird ein Element ausgewählt. Die Folge wird so umsortiert, dass das ausgewählte Element an seine insgesamt (bezogen auf den Sortiervorgang der vollständigen Datenfolge) richtige endgültige Position zu liegen kommt. Nach dem Umordnen dürfen links vom ausgewählten Element nur mehr kleinere Elemente stehen und rechts nur mehr größere. Dann wird für die Folgen links und rechts vom ausgewählten Element das Verfahren rekursiv aufgerufen. Das korrekte Umordnen wird dadurch erreicht, dass von links her Elemente gesucht werden, die in die rechte Hälfte gehören, und von rechts her solche, die in die linke Hälfte gehören. Dann werden diese falsch plazierten Elemente vertauscht. Das Umordnen endet, wenn die beiden Suchvorgänge an der endgültigen Position des ausgewählten Elements zusammenstoßen.

Programmcode

procedure QuickSort ( var f : TArray; HighIndex : integer ) : string;

procedure rQuickSort ( links, rechts : integer);
// rekursiver Teil des QuickSorts
// Als Trennelement wird das jeweils mittlere Element der Teilfolge ausgewählt.
var i, j, x : integer;
begin
if links then begin
i := links;
j := rechts;
x := f[(i+j) div 2]; // Wert des Trennelements
repeat
while f[i] while f[j]> x do dec(j);
if i until i>= j;
rQuickSort (links, j - 1 );
rQuickSort (j+1, rechts);
end;
end; // rQuicksort

begin // QuickSort
rQuickSort (0, HighIndex);
end; // QuickSort

Aufwandsabschätzung

Aufwand:
    In jeder Ebene der Rekursion wird jedes Element betrachtet, d.h. n - Elemente. Die Rekursionstiefe hängt davon ab welches Element als Trennelement gewählt wurde. Im besten Fall wird immer genau das tatsächlich mittlere gewählt, dann ist die Rekursionstiege ld (n). Normalerweise wird das gewählte Trennelement nicht genau das mittlere sein, sodass sich die Rekursionstiefe etwas verschlechtert: ~ 1,4 ld (n).
Daraus folgt der Aufwand
.
Wenn zufällig immer das kleinste oder das größte Element als Trennelement auswählt wird, beträgt die Rekursionstiefe n/2 und somit der Aufwand
.

Sortierdauer



Fallstricke und Fußangeln

Sortieren auf Datenträger

Solange alle Daten im Hauptspeicher Platz haben, stimmen die obigen Aufwandsabschätzungen. In vielen Fällen sind die Datenmengen aber so groß, dass sie nur in großen Dateien auf Datenträgern Platz finden.
Meist wird nach einem Schlüssel (Kundennummer, Namen, ...) sortiert und die übrigen Daten (Adresse, ...) werden mitkopiert. Die Aufgabe vereinfacht sich stark, wenn es möglich wird, den Schlüssel sowie den Verweis auf den dazugehörigen Datensatz (Record - Nummer) im Speicher unterzubringen.
In jedem Fall erfordert der langsame Zugriff auf Dateien ganz andere Lösungsstrategien für Sortierverfahren.

Nutzung des Hauptspeichers

Um auch größere Datenmengen effizient sortieren zu können, muss man den zur Verfügung stehenden Speicher effizient nutzen. Man muss also versuchen, einen möglichst großen Teil des Hauptspeichers für das Programm zu reservieren, um möglichst wenig auf den sehr viel langsameren (Faktor 1000 und mehr) Sekundärspeicher (Festplatte, ...) zurückgreifen zu müssen.

Optimierungen

Bei der Aufwandsabschätzung zählt man die Größenordnung der geleisteten Arbeit. Allerdings kann der Einsatz gezielter Optimierungen (natürlich unter Verwendung von Kenntnissen über die interne Verarbeitung durch den Compiler und Hardware) die Abschätzung völlig auf den Kopf stellen.
Es muss daher immer sorgfältig betrachtet werden, ob nicht weitergehende Annahmen (zum Beispiel in Hinblick auf Struktur und Umfang der zu erwarteten Datenmenge) im Einzelfall gezielte Optimierungen erlauben.

Beispiele

    MergeSort: Für die Subprocedure Merge wird das Hilfsarray Ziel benötigt. Deklariert man das Hilfsarray als lokale Variable innerhalb von Merge anstatt global zu Merge, benötigt der Algorithmus die zehnfache Zeit, da nun bei jedem Aufruf (also insgesamt n*ld(n) - mal) die Variable Ziel (400 KB!) neu am Stack angelegt und anschließend wieder vernichtet werden muss. QuickSort: Wird statt der globalen Procedure swap das Vertauschen von zwei Variablen schon innerhalb des Sortieralgorithmus implementiert, so verbessert sich die Performance um ca. 30%, da nun die Procedureaufrufe für swap entfallen. usw.

Kurzübersicht

Algorithmen mit Aufwand O(n2) mit unsortierten Daten



Algorithmen mit Aufwand O(n ln(n)) mit unsortierten Daten



[1] Teile und Erobere: Zerteile das Problem bis es nur mehr trivial ist und löse nunmehr die trivialen Probleme.

2066 Worte in "deutsch"  als "hilfreich"  bewertet