Startseite » Informatik » Referate » Detailseite
 

  • Datenschutz und Datensicherheit: PGP

    Was ist PGP: PGP ist ein Public Key Verschlüsselungsprogramm, ursprünglich von Philip Zimmermann entwickelt und arbeitet nach dem RSA - und IDEA(DES) - Verfahren. PGP steht für Pretty Good...Referat Datenschutz und Datensicherheit: PGP

    1116 Worte in "deutsch"  als "hilfreich"  bewertet

  • Datenschutz- und Verschlüsselungsverfahren

    Datenschutz - und Verschlüsselungsverfahren Datenschutz - Verschlüsselungsverfahren und elektronische Signatur werden zur Verschlüsselung von Nachrichten verwendet. Dabei...Referate Datenschutz- und Verschlüsselungsverfahren

    531 Worte in "deutsch"  als "hilfreich"  bewertet

  • DFÃœ-Skript-Befehlssprache

    DFÜ - Skript - Befehlssprache Zur Unterstützung bei der Skripterstellung für das DFÜ - Netzwerk Inhaltsverzeichnis 1.0 Übersicht 2.0 Grundstruktur eines...DFÜ-Skript-Befehlssprache Referat

    1461 Worte in "deutsch"  als "hilfreich"  bewertet

Einfache Sortieralgorithmen

1. Einfache Sortieralgorithmen

Sortieralgorithmen haben die Aufgabe unsortiert Datensätze und dergleichen in einen sortierten Endzustand zu verwandeln. Sortiert wird nach dem sogenannten "Schlüssel" Dieser kann sein eine ganzzahlige Zahl, ein Buchstaben oder ein String etc. Eine unbedingt notwendige Bedienung an den Schlüssel ist, dass er für jeden Datensatz unterschiedlich ist. Ein Unterschiedlicher Datensatz darf auf keinen Fall den selben Schlüssel besitzen.


Einfache Sortierverfahren eignen sich nur für kleine Datensätze (max. 500 DS).
Der Aufwand ist höchstens N².

Als Tafelbild eignet sich ein Beispiel eines Sortiervorganges, einer ungeordneten Liste, wie sie in den Unterlagen beschrieben werden. Auch ein Vergleich mit einem anderen ist denkbar !

1.1. Sortieren durch Minimumsuche (Maximumsuche)

Die Idee: Man sucht im ersten Schleifendurchgang, den niedrigsten Schlüssel. Diesen Datensatz vertauscht man nun mit dem ersten. Beim zweiten durchlauf sucht man nun wieder den DS mit dem niedrigsten Schlüssel jedoch ab den 2.DS. Findet man diesen so wird er nun mit dem zweiten DS vertauscht......Die Anzahl der Durchgänge ist die Anzahl der DS - 1, da beim Letzten gar nicht nach dem kleinsten gesucht werden muss.
Allgemein gesagt: nach i Schleifendurchgängen hat man ein Sortiertes Teilfeld der Länge i (von 1 bis i). Dieses Teilfeld ist auch am richtigen Platz. Deshalb sind nur anzahl - 1 Schritte notwendig.

Bei der Maximumsuche zählt man die DS von hinten nach vorne durch und sucht jeweils den DS mit dem größten Schlüssel.

Aufwand: Vergleich zweier Schlüssel und Organisatoinsarbeit
(z.B.: Indexerhöhung)
Vertauschung
Aufwand insgesamt: N²/2 Aktionen+N Vertauschungen
höchstmöglicher Aufwand: O(N):= N²

Der Aufwand hängt nur von der Anzahl der Datensätze ab nicht von deren Anordnung.

Bespiel des Sortiervorganges:
6
 7
 2
 1
 3
 9
 4
 5
 8
1
 7
 2
 6
 3
 9
 4
 5
 8
1
 2
 7
 6
 3
 9
 4
 5
 8
1
 2
 3
 6
 7
 9
 4
 5
 8
1
 2
 3
 4
 7
 9
 6
 5
 8
1
 2
 3
 4
 5
 9
 6
 7
 8
1
 2
 3
 4
 5
 6
 9
 7
 8
1
 2
 3
 4
 5
 6
 7
 9
 8
1
 2
 3
 4
 5
 6
 7
 8
 9



1.2. Sortieren durch Einordnen

Mit Hilfe einer Schleife (von 2 bis N) zählt man jeden Datensatz durch. Der Schlüssel des momentanen angesprochen Datensatz j wird mit seinen "Vorgängerschlüsseln" verglichen und jeder größere wird um einen Platz vorgeschoben. Diesen Durchgang zählt man j - 1 runter bis 1. Der Datensatz vom Platz j - 1 füllt dann die entstandene Lücke bei j.
Auch hier bekommt man nach dem j - ten Durchgang ein sortiertes Teilfeld mit j Datensätzen. Jedoch ist diese Feld nicht an seiner richtigen Position.

Aufwand: 1 Schlüsselvergleich
Organisation
Umspeicherung des vollständigen Datensatzbestandes
Aufwand insgesamt: mindestens N
im Mittel N²/4
höchstens n²/2 Aktionen

Der Aufwand hängt sehr stark von der Anordnung (Vorsortierung) ab. Je gründlicher der Datenbestand bereits sortiert ist, desto weniger wird der Aufwand. im bestem Falle mit dem minimalsten Aufwand.

Beispiel des Sortiervorganges:
6
 7
 2
 1
 3
 9
 4
 5
 8
6
 7
 2
 1
 3
 9
 4
 5
 8
2
 6
 7
 1
 3
 9
 4
 5
 8
1
 2
 6
 7
 3
 9
 4
 5
 8
1
 2
 3
 6
 7
 9
 4
 5
 8
1
 2
 3
 6
 7
 9
 4
 5
 8
1
 2
 3
 4
 6
 7
 9
 5
 8
1
 2
 3
 4
 5
 6
 7
 9
 8
1
 2
 3
 4
 5
 6
 7
 8
 9





















1.3. Sortieren durch Mischen

Beim Sortieren durch Mischen werden zwei bereits sortierte Datensatzbestände zu einem großen Datenbestand zusammengemischt. Der neuentstandene Datenbestand ist ebenfalls sortiert. Man hat je Datenbestand einen Index (x1 und x2). Nun vergleicht man den Schlüssel der beiden Datensätze. Der Datensatz mit dem niederen Schlüssel wird auf das neue Feld geschrieben. Zusätzlich wird der Index derjenigen Tabelle erhöht von der der Datensatz entnommen wurde. nun vergleicht man wieder beide,.....Hat man das Ende eines Datenbestandes erreicht, so entnimmt man nur den anderen Datenbestand die einzelnen Datensätze ohne sie zu vergleichen.

Aufwand: N Aktionen
Aufwand insgesamt: N*ldN Aktionen

Ein wesentlicher Nachteil ist der große Speicherplatzbedarf. Jedoch trotzdem eine bevorzugte Methode zum sortieren von verketteten Listen.

Beispiel des Sortiervorganges:
0
 3
 6
 8
 9
1
 2
 4
 5
 7










0
 3
 6
 8
 9
1
 2
 4
 5
 7
0








0
 3
 6
 8
 9
1
 2
 4
 5
 7
0
 1







0
 3
 6
 8
 9
1
 2
 4
 5
 7
0
 1
 2






0
 3
 6
 8
 9
1
 2
 4
 5
 7
0
 1
 2
 3





0
 3
 6
 8
 9
1
 2
 4
 5
 7
0
 1
 2
 3
 4




0
 3
 6
 8
 9
1
 2
 4
 5
 7
0
 1
 2
 3
 4
 5



0
 3
 6
 8
 9
1
 2
 4
 5
 7
0
 1
 2
 3
 4
 5
 6


0
 3
 6
 8
 9
1
 2
 4
 5
 7
0
 1
 2
 3
 4
 5
 6
 7

0
 3
 6
 8
 9
1
 2
 4
 5
 7
0
 1
 2
 3
 4
 5
 6
 7
 8
0
 3
 6
 8
 9
1
 2
 4
 5
 7
0
 1
 2
 3
 5
 5
 6
 7
 8
 9

848 Worte in "deutsch"  als "hilfreich"  bewertet