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

Besprechung Blatt 11 Binary Search Sortierverfahren Vorbereitung Blatt 12

Algorithmen und Datenstrukturen 12

Stefan Ploner

12. Juli 2012

Algorithmen und Datenstrukturen 12 Stefan Ploner


1 Besprechung Blatt 11Fragen

2 Binary SearchBinare Suche in ArraysBinare Suchbaume (Binary Search Tree)

3 SortierverfahrenAllgemeinHeapsortBubblesortInsertionsortMergesortQuicksort

4 Vorbereitung Blatt 12Hinweise









Fragen

Fragen zu Blatt 11?









Binare Suche in Arrays

Zur Erinnerung: Binary Search sucht nach einem Element in einersortierten Datenstruktur nach dem Divide and Conquer Prinzip.

Vorraussetzungen• Sortiert

• Zugriff uber Index in O(1) ⇒ Arrays




Algorithmus

• Array leer →

Element nicht enthalten

• sonst:

gesuchten Wert mit mittlerem Element vergleichen• Element gleich → gefunden• Element zu groß → gesuchtes Element liegt links• Element zu klein → gesuchtes Element liegt rechts

• beginne die Suche im eingegrenzten Array von Neuem




Algorithmus

• Array leer → Element nicht enthalten

• sonst:

gesuchten Wert mit mittlerem Element vergleichen• Element gleich → gefunden• Element zu groß → gesuchtes Element liegt links• Element zu klein → gesuchtes Element liegt rechts





Algorithmus


• sonst: gesuchten Wert mit mittlerem Element vergleichen

• Element gleich → gefunden• Element zu groß → gesuchtes Element liegt links• Element zu klein → gesuchtes Element liegt rechts





Algorithmus


• sonst: gesuchten Wert mit mittlerem Element vergleichen• Element gleich → gefunden• Element zu groß → gesuchtes Element liegt links• Element zu klein → gesuchtes Element liegt rechts





Algorithmus


• sonst: gesuchten Wert mit mittlerem Element vergleichen• Element gleich → gefunden• Element zu groß → gesuchtes Element liegt links• Element zu klein → gesuchtes Element liegt rechts





Bei der binaren Suche ist es egal, ob man Zahlen oderirgendwelche anderen Elemente durchsucht, fur die eine festeOrdnung definiert ist. (→Comparable-Interface)

Problem• die Suche ist damit in logarithmischem Aufwand

• aber: Einfugen in sortiertes Array hat Aufwand O(n)!




Bei der binaren Suche ist es egal, ob man Zahlen oderirgendwelche anderen Elemente durchsucht, fur die eine festeOrdnung definiert ist. (→Comparable-Interface)

Problem• die Suche ist damit in logarithmischem Aufwand

• aber: Einfugen in sortiertes Array hat Aufwand O(n)!



Binare Suchbaume (Binary Search Tree)

Binare Suchbaume - Aufbau

(verzeigerte) Baumstruktur, das heißt:

• ein Wurzelelement (vgl. mit Head in Listen)

• mehrere Kinder erlaubt (hier Binarbaum → max. 2!)

• wie bei verketteten Listen ist der Speicherverbrauch dynamischvon der momentanen Anzahl der Elemente abhangig.

Anordnung (uber Wert selbst oder “Key” oder Comparator):

• “kleinere” Kinder links

• “großere” (und wenn erlaubt gleiche) Kinder rechts

• Elemente steigen von links nach rechts an

Im folgenden sind keine doppelten Keys (bzw. Werte, wenn nachdiesen sortiert wird) erlaubt.






























Suchen

• Baum leer →


• sonst: gesuchtes Element mit Wurzel vergleichen• Element gleich → gefunden• Element zu groß → ges. Element liegt in linkem Unterbaum• Element zu klein → ges. Element liegt in rechtem Unterbaum

• beginne die Suche im Unterbaum von Neuem

Im Prinzip eine binare Suche auf einer verzeigerten Datenstruktur.(Zugriff auf die Kinder in O(1))




Suchen

• Baum leer → Element nicht enthalten

• sonst:

gesuchtes Element mit Wurzel vergleichen• Element gleich → gefunden• Element zu groß → ges. Element liegt in linkem Unterbaum• Element zu klein → ges. Element liegt in rechtem Unterbaum






Suchen


• sonst: gesuchtes Element mit Wurzel vergleichen

• Element gleich → gefunden• Element zu groß → ges. Element liegt in linkem Unterbaum• Element zu klein → ges. Element liegt in rechtem Unterbaum






Suchen








Suchen








Suchen








Einfugen

• beginne mit einer Suche nach dem Elementdiese bricht an 2 Stellen ab:

• Abbruch bei leerem Restbaum → Element an diese Stelleeinfugen

• Element gefunden - je nach Wunsch• Element verwerfen, da bereits enthalten• bei Sortierung uber Keys konnte Aktualisieren des Inhalts

sinnvoll sein




Einfugen




sinnvoll sein




Einfugen




sinnvoll sein




Einfugen




sinnvoll sein




Loschen

• beginne mit einer Suche nach dem Element

• Abbruch in 2 Fallen:• leerer Restbaum →


• Element gefunden →

Element loschen

Beim Loschen gibt es 3 Moglichkeiten, es darf kein Loch entstehen

• Element ist ein Blatt →

beim Loschen entsteht kein Loch, ok

• Element hat ein Kind →

Kind an Stelle des Elements hangen

• Element hat zwei Kinder →

Element durch ein innerstes Kindersetzen (siehe nachste Folie)




Loschen


• Abbruch in 2 Fallen:• leerer Restbaum → Element nicht enthalten• Element gefunden → Element loschen











Loschen













Loschen




• Element ist ein Blatt → beim Loschen entsteht kein Loch, ok

• Element hat ein Kind → Kind an Stelle des Elements hangen

• Element hat zwei Kinder → Element durch ein innerstes Kindersetzen (siehe nachste Folie)




Loschen

Beispiel: Loschen eines Elements mit 2 KindernDie 6 und die 9 sind die “innersten” Kinder - alle anderenUnterelemente sind sowohl von der Zahlenordnung als auch von derhorizontalen Position gesehen weiter von der 7 (Mitte) entfernt.

Quelle: http://en.wikipedia.org/wiki/File:Binary_search_tree_delete.svg

Daher bleibt die Suchbaumeigenschaft beim Ersetzen erhalten.


http://en.wikipedia.org/wiki/File:Binary_search_tree_delete.svg








Allgemein

• Aufwand eines Sortieralgorithmus:• average-case (durschnittl. Aufwand)• best-case (min. Aufwand)• worst-case (max. Aufwand)

• Eigenschaften eines Sortieralgorithmus:• sortiert stabil oder nicht stabil• sortiert in-place oder nicht in-place• ist nicht adaptiv (Aufwand immer gleich)

oder adaptiv (Aufwand profitiert von teilw. sortierten Daten)

• sehr gute Referenz: http://sorting-algorithms.com

Anmerkung: in Java sind Intervallgrenzen meist in der Form[inklusiv , exklusiv) angegeben!


http://sorting-algorithms.com


Allgemein


• Eigenschaften eines Sortieralgorithmus:

• sortiert stabil oder nicht stabil• sortiert in-place oder nicht in-place• ist nicht adaptiv (Aufwand immer gleich)







Allgemein


• Eigenschaften eines Sortieralgorithmus:• sortiert stabil oder nicht stabil

• sortiert in-place oder nicht in-place• ist nicht adaptiv (Aufwand immer gleich)







Allgemein


• Eigenschaften eines Sortieralgorithmus:• sortiert stabil oder nicht stabil• sortiert in-place oder nicht in-place

• ist nicht adaptiv (Aufwand immer gleich)oder adaptiv (Aufwand profitiert von teilw. sortierten Daten)






Allgemein









Allgemein









Allgemein









Heapsort

Heapsort

Algorithmus (vgl. Herausnehmen aus einem Heap, Ubung 10)

• statt das Maximum herauszunehmen, wird es an die hinterstePosition getauscht

• der Heap wird um eins kurzer und seine Struktur muss wiebeim Herausnehmen wiederhergestellt werden

• dahinter wird die sortierte Reihung ruckwarts aufgebaut

Eigenschaften

• sortiert nicht stabil

• sortiert in-place

• average-/best-/worst-case O(n log n)⇒ nicht adaptiv



Heapsort

Heapsort





Eigenschaften






Heapsort

Heapsort





Eigenschaften






Bubblesort

Bubblesort

Algorithmus

• von vorne alle Elemente durchgehen,ist ein Element kleiner als sein Vorganger: tauschen

• wiederholen, bis kein Tausch mehr notig ist

Eigenschaften

• sortiert stabil


• average-/worst-case O(n2)

• best-case O(n) (Eingabedaten fast sortiert)⇒ adaptiv



Bubblesort

Bubblesort

Algorithmus



Eigenschaften

• sortiert stabil



• best-case

O(n) (Eingabedaten fast sortiert)⇒ adaptiv



Bubblesort

Bubblesort

Algorithmus



Eigenschaften

• sortiert stabil






Insertionsort

Insertionsort

Algorithmus

• von vorne alle Elemente durchgehen

• jedes Element solange mit seinem Vorganger tauschen,bis dieser kleiner ist

Eigenschaften

• sortiert stabil






Insertionsort

Insertionsort

Algorithmus

• von vorne alle Elemente durchgehen

• jedes Element solange mit seinem Vorganger tauschen,bis dieser kleiner ist

Eigenschaften

• sortiert stabil






Mergesort

Mergesort (Sortieren durch Mischen )

Algorithmus

• Liste rekursiv halbieren

• Teile ruckwarts mit Reißverschlussverfahren zusammenfugen

Eigenschaften

• sortiert stabil

• sortiert normalerweise nicht in-place




Mergesort

Mergesort (Sortieren durch Mischen )

Algorithmus

• Liste rekursiv halbieren

• Teile ruckwarts mit Reißverschlussverfahren zusammenfugen

Eigenschaften

• sortiert stabil





Quicksort

QuicksortAlgorithmus

• Pivotelement auswahlen

• Liste aufteilen: (Restlisten noch unsortiert)

kleinere Elemente < Pivotelement < großere Elemente

• wiederholen bis Restlisten leer

Eigenschaften



• average-/best-case O(n log n)

• worst-case O(n2) (Pivotelement immer schlecht gewahlt)⇒ adaptiv

• durchschnittlich schnellster Sortieralgorithmus



Quicksort

QuicksortAlgorithmus

• Pivotelement auswahlen

• Liste aufteilen: (Restlisten noch unsortiert)

kleinere Elemente < Pivotelement < großere Elemente

• wiederholen bis Restlisten leer

Eigenschaften



• average-/best-case O(n log n)

• worst-case O(n2) (Pivotelement immer schlecht gewahlt)⇒ adaptiv

• durchschnittlich schnellster Sortieralgorithmus









Hinweise

Wie teste ich meine Implementierung?

Sortierverfahren lassen sich sehr einfach testen, indem man sie mitdenen aus der API vergleicht.

• beliebigen Array erzeugen

• echte Kopie des Arrays erzeugen ( Arrays.copyOf() )

• Original mit eigenem Sortierverfahren testen

• es gibt eine Uberladung von java.util.Arrays.sort(), die genaudie gleichen Parameter annimmt.→ mit dieser die Kopie sortieren

• beide Arrays mit Arrays.toString() ausgeben und vergleichen

Erzeugt man keine echte Kopie, so wird 2x der selbe Array sortiertund das Ergebnis zeigt nur den letzten Algorithmus!

Details zu den Arrays Methoden in der API.



Hinweise

12.?

Zum Rumspielen mit binaren Suchbaumen den Link auf demUbungsblatt oder folgendes Java-Applet verwenden:http://www.site.uottawa.ca/~stan/csi2514/applets/avl/

BT.html (Haken bei AVL rausnehmen!)

Alles weitere bis Freitag Topf-Secret!


http://www.site.uottawa.ca/~stan/csi2514/applets/avl/BT.html

http://www.site.uottawa.ca/~stan/csi2514/applets/avl/BT.html


Hinweise

Noch Fragen?

Danke fur die Aufmerksamkeit!



Hinweise

Noch Fragen?

Danke fur die Aufmerksamkeit!


Documents

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