2.3.1 Einleitung 2.3.2 Einfache Sortierverfahren 2.3.3 ...€¦ · Datenstrukturen und Algorithmen...

Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian Emmes, Sven Middelberg, Michael Kremer

2.3 Sortieren

2.3.1 Einleitung 2.3.2 Einfache Sortierverfahren 2.3.3 Höhere Sortierverfahren 2.3.4 Komplexität von Sortierverfahren 2.3.5 Spezielle Sortierverfahren

Stabilität von Sortieralgorithmen

•  Ein Sortieralgorithmus heißt stabil, wenn sich die relative Reihenfolge von gleichen Elementen während des Sortierens nicht ändert.

•  Beispiel:

1 1 2 2 1 3

stabil

nicht stabil

Counting-Sort

•  Annahme: R1, R2, ... , Rn ∈ 1,... ,k •  Idee: Bestimme zu jedem Ri die Zahl

der Elemente ≤Ri und sortiere Ri an die entsprechende Stelle

Counting-Sort: Algorithmus

•  CountingSort(A[1..n],C[1..n]) for i ← 1 to k do B[ i ] ← 0 for i ← 1 to n do B[ A[ i ] ] ← B[ A[ i ] ]+1 for i ← 2 to k do B[ i ] ← B[ i ] + B[ i−1 ] for i ← n downto 1 do C[ B[ A[ i ] ] ] ← A[ i ] B[ A[ i ] ] ← B[ A[ i ] ]−1

Eingabe: A[1..n] Ausgabe: C[1..n]

B ist mit 0en initialisiert

B[j] enthält die Anzahl der Elemente = j

B[j] enthält die Anzahl der Elemente ≤ j

B[j] enthält das j-te Element

Counting-Sort: Beispiel

1 4 1 3 4 4 6 3 A n=8, k=6

1 4 1 3 4 4 6 3

0 0 0 0 0 0

n=8, k=6

1 2 3 4 5 6

1 4 1 3 4 4 6 3

0 0 0 1 0 0

n=8, k=6

1 2 3 4 5 6

1 4 1 3 4 4 3

0 0 1 1 0 0

n=8, k=6

1 2 3 4 5 6

1 4 1 3 4 6 3

1 0 1 1 0 0

n=8, k=6

1 2 3 4 5 6

4 1 3 4 4 6 3

1 0 1 1 0 1

n=8, k=6

1 2 3 4 5 6

1 4 1 4 4 6 3

1 0 1 2 0 1

n=8, k=6

1 2 3 4 5 6

1 4 1 3 4 4 6 3

3 0 1 2 0 2

n=8, k=6

1 2 3 4 5 6

1 4 1 3 4 4 6 3

3 0 1 2 2

n=8, k=6

1 2 3 4 5 6

1 4 1 3 4 4 6 3

3 0 1 2 2

n=8, k=6

1 2 3 4 5 6

1 4 1 3 4 4 6 3

3 0 1 2 2

n=8, k=6

1 2 3 4 5 6

1 4 1 3 4 4 6 3

3 0 1 2 2

n=8, k=6

1 2 3 4 5 6

1 4 1 3 4 4 6 3

0 1 4 2 2

n=8, k=6

1 2 3 4 5 6

1 4 1 3 4 4 6 3

0 1 4 2 2

n=8, k=6

1 2 3 4 5 6

1 4 1 3 4 4 6 3

7 8 4 2 2

n=8, k=6

1 2 3 4 5 6

1 4 1 3 4 4 6 3

7 8 4 2 2

n=8, k=6

1 2 3 4 5 6

C 1 2 3 4 5 6 8 7

1 4 1 3 4 4 6 3

7 8 4 2 2

n=8, k=6

1 2 3 4 5 6

C 1 2 3 4 5 6 8 7

1 4 1 3 4 4 6 3

7 8 4 2 2

n=8, k=6

1 2 3 4 5 6

C 1 2 3 4 5 6 8 7

1 4 1 3 4 4 6 3

7 8 4 2 2

n=8, k=6

1 2 3 4 5 6

C 1 2 3 4 5 6 8 7

1 4 1 3 4 4 6 3

7 8 4 2 2

n=8, k=6

1 2 3 4 5 6

C 1 2 3 4 5 6 8 7

1 4 1 3 4 4 6 3

7 8 4 2 2

n=8, k=6

1 2 3 4 5 6

1 C 1 2 3 4 5 6 8 7

1 4 1 3 4 4 6 3

n=8, k=6

1 2 3 4 5 6

1 C 1 2 3 4 5 6 8 7

1 4 1 3 4 4 6 3

n=8, k=6

1 2 3 4 5 6

1 C 1 2 3 4 5 6 8 7

1 4 1 3 4 4 6 3

n=8, k=6

1 2 3 4 5 6

1 C 1 2 3 4 5 6 8 7

1 4 1 3 4 4 6 3

n=8, k=6

1 2 3 4 5 6

1 C 1 2 3 4 5 6 8 7

1 4 1 3 4 4 6 3

n=8, k=6

1 2 3 4 5 6

1 C 1 2 3 4 5 6 8 7

1 4 1 3 4 4 6 3

n=8, k=6

1 2 3 4 5 6

3 1 C 1 2 3 4 5 6 8 7

1 4 1 3 4 4 6 3

n=8, k=6

1 2 3 4 5 6

3 1 C 1 2 3 4 5 6 8 7

1 4 1 3 4 4 6 3

n=8, k=6

1 2 3 4 5 6

3 1 1 C 1 2 3 4 5 6 8 7

1 4 1 3 4 4 6 3

n=8, k=6

1 2 3 4 5 6

3 1 1 C 1 2 3 4 5 6 8 7

1 4 1 3 4 4 6 3

n=8, k=6

1 2 3 4 5 6

3 6 1 1 C 1 2 3 4 5 6 8 7

1 4 1 3 4 4 6 3

n=8, k=6

1 2 3 4 5 6

3 6 3 1 1 C 1 2 3 4 5 6 8 7

1 4 1 3 4 4 6 3

n=8, k=6

1 2 3 4 5 6

3 6 3 1 1 C 1 2 3 4 5 6 8 7

Counting-Sort: Aufwand

O(k+n)

Counting-Sort: Aufwand

•  Counting-Sort ist nur sinnvoll, wenn k = O(n) und damit T(n) = O(n)

•  Counting-Sort verwendet keine Vergleiche

•  Counting-Sort ist stabil

Radix-Sort

•  Annahme: R1, R2, ... , Rn ∈ 0,... ,kd−1 •  „d-stellige Zahlen zur Basis k“ •  „Wörter der Länge d aus einem

Alphabet der Größe k“

Radix-Sort

•  RadixSort(A[1..n]) for i ← 1 to d do „sortiere A stabil nach Stelle i“

Radix-Sort: Beispiel

Radix-Sort: Aufwand

•  RadixSort(A[1..n]) for i ← 1 to d do „sortiere A stabil nach Stelle i“

Radix-Sort: Aufwand

•  RadixSort(A[1..n]) for i ← 1 to d do „sortiere A stabil mit Counting-Sort nach Stelle i“

Radix-Sort: Aufwand

•  RadixSort(A[1..n]) for i ← 1 to d do „sortiere A stabil mit Counting-Sort nach Stelle i“

T(k,d,n)=O(d×(n+k))

Radix-Sort: Aufwand

•  Beachte: Ist k gegeben, so benötigt man zur Darstellung von n verschiedenen Elementen mindestens d ≥ logk(n) Stellen → T(n) = ΩΩ(n×log n)

Bucket-Sort

•  Annahme: R1, R2, ... , Rn gleichverteilt aus [0,1)

•  Idee: 1. Unterteile [0,1) in n „Buckets“

[0,1/n), [1/n,2/n), ... , [(n−1)/n,1) 2.  Füge die Ri in die Buckets ein (erwartet:

ein Element pro Bucket) 3.  Sortiere die Buckets 4. Hänge die Buckets aneinander

Bucket-Sort: Algorithmus

•  BucketSort(A[1..n]) new B[0..n−1] for i ← 1 to n do push(B[⎣n×A[ i ]⎦], A[ i ]) for i ← 0 to n−1 do sort(B[ i ]) c ← 1 for i ← 0 to n−1 do for j ← 1 to size(B[ i ]) do A[c] ← B[ i ][ j ] c ← c+1

Bucket-Sort: Beispiel

0.73 0.24 0.75 0.31 0.12 0.21 0.05 0.20 0.82 0.59

[0.9,1.0) [0.8,0.9) [0.7,0.8) [0.6,0.7) [0.5,0.6) [0.4,0.5) [0.3,0.4) [0.2,0.3) [0.1,0.2) [0.0,0.1) 0

0.73 0.24 0.75 0.31 0.12 0.21 0.05 0.20 0.82 0.59

[0.9,1.0) [0.8,0.9) [0.7,0.8) [0.6,0.7) [0.5,0.6) [0.4,0.5) [0.3,0.4) [0.2,0.3) [0.1,0.2) [0.0,0.1) 0

0.73 0.24 0.75 0.31 0.12 0.21 0.05 0.20 0.82 0.59

[0.9,1.0) [0.8,0.9) [0.7,0.8) [0.6,0.7) [0.5,0.6) [0.4,0.5) [0.3,0.4) [0.2,0.3) [0.1,0.2) [0.0,0.1) 0

0.73 0.24 0.75 0.31 0.12 0.21 0.05 0.20 0.82 0.59

[0.9,1.0) [0.8,0.9) [0.7,0.8) [0.6,0.7) [0.5,0.6) [0.4,0.5) [0.3,0.4) [0.2,0.3) [0.1,0.2) [0.0,0.1) 0

0.73 0.24 0.75 0.31 0.12 0.21 0.05 0.20 0.82 0.59

[0.9,1.0) [0.8,0.9) [0.7,0.8) [0.6,0.7) [0.5,0.6) [0.4,0.5) [0.3,0.4) [0.2,0.3) [0.1,0.2) [0.0,0.1) 0

0.73 0.24 0.75 0.31 0.12 0.21 0.05 0.20 0.82 0.59

[0.9,1.0) [0.8,0.9) [0.7,0.8) [0.6,0.7) [0.5,0.6) [0.4,0.5) [0.3,0.4) [0.2,0.3) [0.1,0.2) [0.0,0.1) 0

0.73 0.24 0.75 0.31 0.12 0.21 0.05 0.20 0.82 0.59

0.31 0.21

[0.9,1.0) [0.8,0.9) [0.7,0.8) [0.6,0.7) [0.5,0.6) [0.4,0.5) [0.3,0.4) [0.2,0.3) [0.1,0.2) [0.0,0.1) 0

0.73 0.24 0.75 0.31 0.12 0.21 0.05 0.20 0.82 0.59

0.31 0.21

[0.9,1.0) [0.8,0.9) [0.7,0.8) [0.6,0.7) [0.5,0.6) [0.4,0.5) [0.3,0.4) [0.2,0.3) [0.1,0.2) [0.0,0.1) 0

0.73 0.24 0.75 0.31 0.12 0.21 0.05 0.20 0.82 0.59

0.31 0.21

0.82 [0.9,1.0) [0.8,0.9) [0.7,0.8) [0.6,0.7) [0.5,0.6) [0.4,0.5) [0.3,0.4) [0.2,0.3) [0.1,0.2) [0.0,0.1) 0

0.73 0.24 0.75 0.31 0.12 0.21 0.05 0.20 0.82 0.59

0.31 0.21

[0.9,1.0) [0.8,0.9) [0.7,0.8) [0.6,0.7) [0.5,0.6) [0.4,0.5) [0.3,0.4) [0.2,0.3) [0.1,0.2) [0.0,0.1) 0

0.73 0.24 0.75 0.31 0.12 0.21 0.05 0.20 0.82 0.59

0.31 0.21

[0.9,1.0) [0.8,0.9) [0.7,0.8) [0.6,0.7) [0.5,0.6) [0.4,0.5) [0.3,0.4) [0.2,0.3) [0.1,0.2) [0.0,0.1) 0

0.73 0.24 0.75 0.31 0.12 0.21 0.05 0.20 0.82 0.59

0.31 0.21

[0.9,1.0) [0.8,0.9) [0.7,0.8) [0.6,0.7) [0.5,0.6) [0.4,0.5) [0.3,0.4) [0.2,0.3) [0.1,0.2) [0.0,0.1) 0

0.73 0.24 0.75 0.31 0.12 0.21 0.05 0.20 0.82 0.59

0.31 0.21

[0.9,1.0) [0.8,0.9) [0.7,0.8) [0.6,0.7) [0.5,0.6) [0.4,0.5) [0.3,0.4) [0.2,0.3) [0.1,0.2) [0.0,0.1) 0

0.73 0.24 0.75 0.31 0.12 0.21 0.05 0.20 0.82 0.59

0.31 0.21

[0.9,1.0) [0.8,0.9) [0.7,0.8) [0.6,0.7) [0.5,0.6) [0.4,0.5) [0.3,0.4) [0.2,0.3) [0.1,0.2) [0.0,0.1) 0

0.73 0.24 0.75 0.31 0.12 0.21 0.05 0.20 0.82 0.59

0.73 0.75

0.24 0.21 0.20

[0.9,1.0) [0.8,0.9) [0.7,0.8) [0.6,0.7) [0.5,0.6) [0.4,0.5) [0.3,0.4) [0.2,0.3) [0.1,0.2) [0.0,0.1) 0

0.73 0.24 0.75 0.31 0.12 0.21 0.05 0.20 0.82 0.59

0.73 0.75

0.20 0.21 0.24

[0.9,1.0) [0.8,0.9) [0.7,0.8) [0.6,0.7) [0.5,0.6) [0.4,0.5) [0.3,0.4) [0.2,0.3) [0.1,0.2) [0.0,0.1) 0

0.73 0.24 0.75 0.31 0.12 0.21 0.05 0.20 0.82 0.59

0.73 0.75

0.20 0.21 0.24

[0.9,1.0) [0.8,0.9) [0.7,0.8) [0.6,0.7) [0.5,0.6) [0.4,0.5) [0.3,0.4) [0.2,0.3) [0.1,0.2) [0.0,0.1) 0

0.73 0.24 0.75 0.31 0.12 0.21 0.05 0.20 0.82 0.59

0.73 0.75

0.20 0.21 0.24

[0.9,1.0) [0.8,0.9) [0.7,0.8) [0.6,0.7) [0.5,0.6) [0.4,0.5) [0.3,0.4) [0.2,0.3) [0.1,0.2) [0.0,0.1) 0

0.73 0.24 0.75 0.31 0.12 0.21 0.05 0.20 0.82 0.59

0.73 0.75

0.20 0.21 0.24

[0.9,1.0) [0.8,0.9) [0.7,0.8) [0.6,0.7) [0.5,0.6) [0.4,0.5) [0.3,0.4) [0.2,0.3) [0.1,0.2) [0.0,0.1) 0

0.73 0.24 0.75 0.31 0.12 0.21 0.05 0.20 0.82 0.59

0.73 0.75

0.20 0.21 0.24

[0.9,1.0) [0.8,0.9) [0.7,0.8) [0.6,0.7) [0.5,0.6) [0.4,0.5) [0.3,0.4) [0.2,0.3) [0.1,0.2) [0.0,0.1) 0

0.73 0.24 0.75 0.31 0.12 0.21 0.05 0.20 0.82 0.59

0.73 0.75

0.20 0.21 0.24

[0.9,1.0) [0.8,0.9) [0.7,0.8) [0.6,0.7) [0.5,0.6) [0.4,0.5) [0.3,0.4) [0.2,0.3) [0.1,0.2) [0.0,0.1) 0

0.73 0.24 0.75 0.31 0.12 0.21 0.05 0.20 0.82 0.59

0.73 0.75

0.20 0.21 0.24

0.05 n=10

0.73 0.24 0.75 0.31 0.12 0.21 0.05 0.20 0.82 0.59

0.59 0.73 0.75 0.31 0.12 0.82 0.20 0.21 0.24 0.05

Bucket-Sort: Analyse

•  Diskrete Zufallsvariable

•  Erwartungswert

•  Varianz

•  X=1 mit 50 % Wahrscheinlichkeit X=3 mit 50 % Wahrscheinlichkeit

•  Erwartungswert: E(X) = 1×0.5 + 3×0.5 = 2.0

•  Erwartungswert: E(X) = 1×0.75 + 3×0.25 = 1.5

•  Varianz: V(X) = (1−2)2×0.5 + (3−2)2×0.5 = 1.0

•  Varianz: V(X) = (1−1.5)2×0.75 + (3−1.5)2×0.25 = 0.75

•  Sei ni die Zahl der Elemente in Bucket i •  Wahrscheinlichkeit, dass ein Element in

Bucket i fällt ist p=1/n •  Wahrscheinlichkeit, dass genau k

Elemente in Bucket i fallen ist “Binomialverteilung”

•  Erwartungswert

•  Varianz

•  Sortieraufwand, z.B. Insertion-Sort

•  Erwarteter Sortieraufwand für Bucket i

•  Erwarteter Sortieraufwand für alle Buckets:

•  BucketSort(A[1..n]) new B[0..n−1] for i ← 1 to n do push(B[⎣n×A[ i ]⎦], A[ i ]) for i ← 0 to n−1 do sort(B[ i ]) c ← 1 for i ← 0 to n−1 do for j ← 1 to size(B[ i ]) do A[c] ← B[ i ][ j ] c ← c+1

O(n) erwartet

O(n) (!)

O(n) erwartet

Spezielle Sortierverfahren

•  Counting-Sort: O(n+k) •  Radix-Sort: O(d×(n+k)) •  Bucket-Sort: O(n) erwartet

2.3.1 Einleitung 2.3.2 Einfache Sortierverfahren 2.3.3 ...€¦ · Datenstrukturen und Algorithmen...

Documents

Kapitel 9: Sortierverfahren - Hochschule Konstanzbittel/ain_fprog/Vorlesung/09... · 2020. 9. 21. · Kapitel 9: Sortierverfahren §Problemstellung §Sortieren durch Einfügen §Sortieren

Algorithmen und Datenstrukturen 12 - CIP-Pool Informatiksu75heja/aud/ss2012/aud12.pdf · Besprechung Blatt 11 Binary Search Sortierverfahren Vorbereitung Blatt 12 1 Besprechung Blatt

FH-Hof Sortierverfahren Richard Göbel. FH-Hof Sortierverfahren - Anwendungen Sortierte Ausgabe von Daten Effiziente Algorithmen Suchen in sortierten Listen

OATH-LDAP€¦ · STROEDER.COM - 2 - 2018-03-10 Zur Person Michael Ströder , Freiberufler Schwerpunkte X.509-basierte PKI, angewandte Verschlüsselung,

The Perfect Shuffle · 2019. 5. 6. · Bitonic Sort Alle Sortierverfahren basieren auf dem Vergleich zweier Elemente. Durch mehrere Vergleiche ist es auch möglich Mengen mit mehr

1 4 Sortierverfahren 4.1 Einführung 4.2 Naive Sortierverfahren 4.2.1 InsertionSort (Sortieren durch Einfügen) 4.2.2 BubbleSort (Aufsteigen von Blasen)

Leitprogramm Sortierverfahren mit deckblatt · 2015. 3. 2. · Institut für Verhaltensforschung Departement für Informatik Leitprogramm Sortierverfahren Fach Informatik Stufe Gymnasium

Kapitel 6: Suchbäume und weitere Sortierverfahren 6.1 Binäre Bäume

· A Linear Operational Semantics for Termination and Complexity Analysis of ISOProlog ⋆ T. Stroder 1, F. Emmes , P. Schneider-Kamp 2, J. Giesl , and C. Fuhs 1 LuFG Informatik

Plateforme Nationale d’Action des emmes Haïtiennes pour la ... · NOVEMBRE ET DÉCEMBRE 2011 201227 FÉVRIER 28 FEVRIER AU 1ER MARS 2012 1er MARS ... Niveau Communal . 4 ACTIONS

Kapitel 10: Komplexitaet von Algorithmen und Sortierverfahren · 2018. 12. 19. · Komplexit at von Algorithmen Wir unterscheiden den Zeitbedarf und den Speicherplatzbedarf eines

Sortierverfahren und zufallszahlen

1 Vorlesung Informatik 2 Algorithmen und Datenstrukturen (09 - Weitere Sortierverfahren) Prof. Th. Ottmann

DVG1 - 12 - Sortierverfahren Sortierverfahren Vortrag: Ingo Gensch, Mathias Reich am: 11.12.2000

12. Such- und Sortierverfahren mit Arrays · Arrays . verkettete Strukturen • Nur sequentielles Durcharbeiten von vorn • Kein Direktzugriff auf einzelnes Datenelement (in der

2.3.1 Einleitung 2.3.2 Einfache Sortierverfahren 2.3.3 Höhere Sortierverfahren … · 2015. 4. 9. · Datenstrukturen und Algorithmen Prof. Dr. Leif Kobbelt, Thomas Ströder, Fabian

1 Kap. 7 Sortierverfahren Kap. 7.0 Darstellung, Vorüberlegungen = {(x, )} mit < internes Sortierenexternes Sortieren pa t pa t nicht in AS Darstellung

7. Parallele Algorithmen für FPGA-Implementierungen · Odd-Even-Transposition-Sort für 8 Elemente. Ein sinnvolles Werkzeug bei der Entwicklung und dem Beweis von Sortierverfahren

1 Kapitel 6: Suchbäume und weitere Sortierverfahren 6.1 Binäre Bäume Die Klasse BinTree mit Traversierungsmethoden 6.2 Suchbäume 6.2.1 AVL Bäume 6.3 HeapSort

Sortierverfahren Susanne Freitag. Vorkenntnisse der Schüler (12. Klasse GK) Begrifflichkeiten: Algorithmus, Rekursion, usw. Begrifflichkeiten: Algorithmus,