AZreferate - Referate und hausaufgaben fur schule.
Referatesuche, Hausarbeiten und Seminararbeiten Kostenlose Online-Dokumente mit Bildern, Formeln und Grafiken. Referate, Facharbeiten, Hausarbeiten und Seminararbeiten findest für Ihre einfache Hausarbeiten.



BetriebstechnikBiographienBiologieChemieDeutschDigitaltechnik
ElectronicaEpochenFertigungstechnikGemeinschaftskundeGeographieGeschichte
InformatikKulturKunstLiteraturManagementMathematik
MedizinNachrichtentechnikPhilosophiePhysikPolitikProjekt
PsychologieRechtSonstigeSportTechnikWirtschaftskunde

Referat Sortieralgorithmen - Selection Sort, Insertion, Bubble Sort

projekt referate

projekt referate

Spezialgebiet aus Informatik

Sortieralgorithmen

Inhaltsverzeichnis

Einführung

Allgemeiner Programmcode

Selection Sort (Sortiern durch Auswahl)

Insertion Sort (Sortieren durch Einfügen)

Bubble Sort (Sortieren durch Austauschen)

Merge Sort (Sortieren durch Mischen)

Radix Exchange Sort (Sortieren durch rekursiven Bitvergleich)

Quick Sort (Sortieren durch Zerlegen)

Fallstricke und Fußangeln

Sortieren auf Datenträger

Nutzung des Hauptspeichers

Optimierungen

Kurzübersicht

Algorithmen mit Aufwand O(n2) mit unsortierten Daten

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


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] < f[min] then min := j; // innere Schleife

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).

Sortierverfahren mit quadratischen Aufwand sind schlecht und eignen sich nur für kleine Datenmengen. Ihre Rechtfertigung liegt einzig und allein in der einfachen Implementierung. Wie wir später sehen werden, gibt es wesentlich effizientere Sortierverfahren mit einem Aufwand von O(nžln(n)).

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

mittlerer-Aufwand:

Die äußere Schleife wird n-1 mal durchlaufen.

Die innere Schleife wird ½ * ½ (n-1) durchlaufen. (Im Mittel erwarten wir, daß das neue Element in die Mitte des soriterten Bereichs gehört.)

Daraus folgt der Aufwand .

worst-case-Aufwand:

Die äußere Schleife wird n-1 mal durchlaufen.

Die innere Schleife wird ½ (n-1) durchlaufen.

Daraus folgt der Aufwand .

best-case-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 .

worst-case-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 - 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] < f[j]

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 < rechts

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.

Daraus folgt der Aufwand .

worst-case-Aufwand:

w.o.

Sortierdauer


Bemerkung:

Die etwas seltsame Krümmung der Graphen entsteht dadurch, daß 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 < rechts) and (b >= 0)

then begin

i := links;

j := rechts;

repeat

while (Bit (f[i], b) = 0) and (i < j) do inc (i);

while (Bit (f[j], b) = 1) and (i < j) do dec (j);

swap (f[i], f[j]);

until i = j;


// Korrigiere Spezialfall, daß 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 T .

worst-case-Aufwand:

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, daß 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, daß 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 < rechts

then begin

i := links;

j := rechts;

x := f[(i+j) div 2]; // Wert des Trennelements

repeat

while f[i] < x do inc(i);

while f[j] > x do dec(j);

if i < j then swap (f[i], f[j]);

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, sodaß sich die Rekursionstiefe etwas verschlechtert: ~ 1,4 ld (n).

Daraus folgt der Aufwand .

worst-case-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ß, daß 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, muß man den zur Verfügung stehenden Speicher effizient nutzen. Man muß 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 muß 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 muß.

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



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



Referate über:


Datenschutz




Copyright © 2024 - Alle Rechte vorbehalten
AZreferate.com
Verwenden sie diese referate ihre eigene arbeit zu schaffen. Kopieren oder herunterladen nicht einfach diese
# Hauptseite # Kontact / Impressum