Dr. Michael Brinkmeier - Startseite TU Ilmenau · Algorithmen und Datenstrukturen Dr. Michael Brinkmeier Technische Universit¨at Ilmenau Fakult¨at Informatik und Automatisierung

Algorithmen und Datenstrukturen

Dr. Michael Brinkmeier

Technische Universitat IlmenauFakultat Informatik und Automatisierung

Fachgebiet Automaten und Formale Sprachen

4.7.2007

Dr. Michael Brinkmeier (TU Ilmenau) Algorithmen und Datenstrukturen 4.7.2007 1 / 21

Sortieren in Linearzeit



Die Schranke fur das vergleichsbasierte Sortieren kann umgangen werden!

Unter Umstanden konnen die Schlussel nicht als atomares Objektaufgefasst werden, sondern als Index.⇒ die untere Schranke gilt nicht.

Beispiel: Die Schlusselmenge ist [m] := {0, 1, . . . ,m − 1}.

Gegeben: n Schlussel a1, . . . , an aus [m].

Praziser: Gegeben sind n Datenobjekte

(a1, d1), . . . , (an, dn)

mit Schlusseln a1, . . . , an aus [m].

Ziel: Sortiere die Liste stabil!



Idee

Lege m Stapel (Stacks) mit Nummern 0, . . . ,m − 1 an.

Durchmustere die Eingabeobjekte, j = 1, . . . , n.

Lege Objekt (aj , dj) auf Stapel Nummer aj .

Wenn alle Objekte auf die Stapel verteilt sind, lese die Objekte in der

”richtigen Reihenfolge“ aus den Stapeln aus.

Realisierung der Stapel: Array B[0 . .m − 1] von Zeigern auf Listen, diedie Stapel darstellen.



Annahme: Die Eingabeobjekte stehen in einer linearen Liste A

(Array wird in Liste”ubersetzt“).

• a1 Frank • a2 Tom • an Karin

Array B[0 . .m − 1] von m Listen:

0: • 0 Gerd

1: • 1 Louis • 1 Tom

...

i : • i Karin • i Frank • · · ·

...

m − 1: •


Eingabeliste:

a5 2 a 5 b 3 a 1 a

1 b 6 a 5 c

A:

b2

Nach Transport in das Listenarray:

5 c 5 b

1 b

b2

1 a

2 a

a5

a

1:

2:

3:

5:

6:

4:

3 a

0:B:

6

NB: Identische Schlussel in umgekehrter Reihenfolge.Dr. Michael Brinkmeier (TU Ilmenau) Algorithmen und Datenstrukturen 4.7.2007 6 / 21

Listenarray:

5 c 5 b

1 b

b2

1 a

2 a

a5

a

1:

2:

3:

5:

6:

4:

3 a

0:B:

6

Nach Auslesen:

A:

1 b 2 a b2 3 a

5 b 5 c

1 a a5

6 a


Bucketsort (Fachsortieren)

1 Bearbeite die Elemente der Liste A nacheinander.

Fuge das Listenelement vorn in Liste B[i ] ein.

NB: Die Reihenfolge von Elementen mit demselben Schlussel wirdumgedreht.

2 Bearbeite die Listen B[m − 1], B[m − 2], . . . B[1], B[0] in dieser(absteigenden) Reihenfolge.

Fur i : lies B[i ] von vorn nach hinten.Fuge das Element vorn in die Ausgabeliste ein.

NB: Die Reihenfolge wird erneut umgedreht ⇒ ZweimaligesUmdrehen ⇒ Stabilitat



Korrektheit: klar.

Laufzeit:

Anlegen von B: O(1)

Initialisieren mit nil-Zeigern: Θ(m).

Verteilen auf die Listen: Θ(n)

Zusammenfugen: Θ(m) + Θ(n)

(Jeden Listenanfang ansehen!)

Gesamt: Θ(m + n).

Linearzeit und linearer Platz, falls m ≤ cn, c konstant.



Alternative

Bei B[i ]-Listen Endezeiger benutzen, hinten anfugen.

In (2): Teillisten konkatenieren.

Vorteil: in Phase (2) O(m) Zeigerbewegungen, Zeit O(m)

Nachteil: Zusatzlicher Speicherplatz O(m) fur Endezeiger.

Gunstig insbesondere wenn m ≪ n ist.


Satz (Bucketsort)

n Objekte mit Schlusseln aus [m] konnen in Zeit Θ(n + m) und mitZusatzplatz Θ(n + m) sortiert werden.

Wenn die Eingabe als lineare Liste gegeben ist, genugt zusatzlicher Platzfur m Zeiger.

Das Sortierverfahren ist stabil.


Erweiterungen

Frage

Was soll man tun, wenn die Anzahl der Schlussel deutlich großer als n ist?

Antwort: Radixsort (oder Mehrphasen-Bucketsort)

Das verfahren ist in verschiedenen Situationen anwendbar:

Die Schlussel haben die Form x = (x1, . . . , xk) ∈ Uk , U = [m], m ≤ n.

Lexikographische Sortierung, d.h.

(x1, . . . , xk) < (y1, . . . , yk)

⇐⇒ ∃j , 1 ≤ j ≤ k : x1 = y1 ∧ . . . ∧ xj−1 = yj−1 ∧ xj < yj

Schlussel x in U ⊆ {0, 1, . . . ,mk − 1}, m ≤ n(nach Ziffern in m-adischer Darstellung)


Erweiterungen

k (moglicherweise verschiedene) Universen (U1, <1), . . . , (Uk , <k)

Schlussel x = (x1, . . . , xk) ∈ U1 × · · · × Uk

Beispiele:Daten: {1, . . . , 31} × {1, . . . , 12} × {1801, . . . , 2090}Spielkarten: {♦,♥,♠,♣} × {2, . . . , 10,Bube,Dame,Konig,As}

Lexikographische Ordnung.

Σ<∞ mit lexikographischer Ordnung (verschiedene Schlussellangen).Dabei: Sigma ist Alphabet (z.B. ASCII-Alphabet).


Radixsort

Wir betrachten Schlussel der Form x = (x1, . . . , xk) ∈ Uk , U = [m].

Idee

Sortiere k-mal mittels Bucketsort

und zwar gemaß der Komponenten in Reihenfolge k, k − 1, . . . , 1(d.h. die

”am wenigsten signifikante“ Komponente zuerst)

Eingabe: Liste A: Eintrage mit Schlusseln (x1, . . . , xk) aus [m]k .

Methode: Fur l = k, k − 1, . . . , 1 tue:sortiere A mittels Bucketsort fur U = [m]benutze aus Schlussel (x1, . . . , xk) den Wert xl als Sortierschlussel

Zeit insgesamt: Θ(k · (n + m))Zusatzplatz: Array mit m Zeigern.(Falls Eingabe in Arrayform: Zusatzplatz Θ(m + n).)


Radixsort - Ein Beispiel

U = {A,B,C,D}

Eingabe A:

Nach Runde l = 3:

Nach Runde l = 2:

Nach Runde l = 1:


Radixsort

Satz (Radixsort)

Der skizzierte Algorithmus Radixsort sortiert n Objekte mit Schlusseln aus[m]k in Zeit Θ(k(n + m)) und Platz Θ(m) (bzw. Θ(n + m) fur Arrays).

Das Verfahren ist stabil.

Beweis (Skizze)

Wir beweisen nur die Korrektheit.

Man zeigt durch Induktion uber l = k, k − 1, . . . , 1 die folgendeSchleifeninvariante:

Nach Schleifendurchlauf fur l ist die Liste A gemaß den Teilschlusseln(xl , xl+1, . . . , xk) ∈ [m]k−l+1 lexikographisch sortiert.

Fur den Induktionsschritt l + 1 → l benutzt man, dass (das einfache)Bucketsort stabil ist, und daher die schon hergestellte Ordnung bezuglichder weniger signifikanten Komponenten nicht zerstort wird.


Die anderen Situationen

Das Verfahren fur U1 × · · · × Uk (Situation 3) ist im wesentlichendasselbe, nur benotigt man verschiedene B-Arrays (oder Arrayabschnitte)in den einzelnen Bucketsort-Durchgangen.

Zeit: O(kn + |U1| + · · · + |Uk |)

Platz: O(n + max1≤i≤k |Ui |).


Sortierung mittels m-adischer Darstellung

Zur zweiten Situation Die Schlussel sind Zahlen in {0, 1, . . . ,mk − 1}:

Idee: Reprasentiere Zahlen in m-adischer Darstellung (mit k Ziffern) undwende Radixsort ziffernweise an.


Sortierung mittels m-adischer Darstellung - Ein Beispiel

Sei m = 10 (d.h. Dezimaldarstellung)

��

��

��

��

��

��

��

��

��

��

��

��

��

436 617 729

l

=3l

531 729 617 312 425 436

=1l

=2

531 312 425 436 617 729

312 617 425 729 531 436

312 425 531

So kleine m sind nicht typisch.

Sinnvoll: m ≈ n, m Zweierpotenz.

Dann ist eine”Ziffer“ xl ein Segment der Binardarstellung von x , die leicht

aus x zu extrahieren ist.


Radixsort

Satz (Radixsort)

Radixsort sortiert n Objekte mit Schlusseln aus [mk ] in Zeit Θ(k(n + m))und Platz Θ(m) (bzw. Θ(n + m) fur Arrays).

Das Verfahren ist stabil.


Sortierung von Strings

n Strings a1, . . . , an mit Buchstaben aus Σ konnen in

Zeit O(L + |Σ| · lmax) und (Zusatz-)Platz O(n + |Σ| + lmax)

sortiert werden, wobei L = |a1| + · · · + |an| die Summe der Langen allerStrings und lmax = max{|a1|, . . . , |an|} die Lange des langsten

Eingabestrings ist.

Beweis: Modifikation von Bucketsort, siehe Literatur.


Documents

Dr. Michael Brinkmeier - Startseite TU Ilmenau · Algorithmen und Datenstrukturen Dr. Michael Brinkmeier Technische Universit¨at Ilmenau Fakult¨at Informatik und Automatisierung