Transcript

5/12/2018 Java16 - Suchen Und Sortieren - slidepdf.com

http://slidepdf.com/reader/full/java16-suchen-und-sortieren 1/14

  16. Suchen und Sortieren 

16.  Suchen und Sortieren

Lernziele☺   Algorithmen für lineare und binäre Suche erklären und anwenden können.

☺  Die Begriffe Komplexität und Ordnung eines Algorithmus kennen.

☺   Algorithmen für die Sortierverfahren Bubble-Sort, Insertion-Sort und Quick-Sort erklären können.

16.1  Suchverfahren

Das Suchen von Informationen in Informationsbeständen gehört zu den häufigsten Aufgaben, die mitComputersystemen ausgeführt werden. Oft ist die gesuchte Information eindeutig durch einen Schlüsselidentifizierbar. Schlüssel sind in der Regel positive ganze Zahlen (z.B. Artikelnummer, Kontonummer etc.)oder alphabetische Schlüssel (z.B. Nachname, Firmenname usw.). Von dem Schlüssel gibt es meist eineReferenz auf die eigentlichen Informationen.

Die Suchverfahren können Kategorien zugeordnet werden:

  Elementare Suchverfahren: Es werden nur Vergleichsoperationen zwischen den Schlüsselnausgeführt. 

  Schlüssel-Transformationen (Hash-Verfahren):  Aus dem Suchschlüssel wird mit arithmetischenOperationen direkt die Adresse von Datensätzenberechnet.

  Suchen in Texten: Suchen eines Musters in einer Zeichenkette. 

16.1.1  Lineare Suche

Die l ineare bzw. sequentielle Suche wird immer dann angewendet, wenn die Schlüssel in ungeordneterFolge in einer Liste abgelegt sind.

Lineare Suche: Die Elemente der Liste werden der Reihe nach mit dem Suchschlüssel verglichen, bis daspassende Element gefunden wird oder das Ende der Liste erreicht ist.

Beispiel:Feld: a[ ]Feldlänge: n =14

Suchschlüssel: k = 57

13 6 8 16 5 59 47 33 57 19 29 4227

2 3 4 5 6 7 8 9 10 11 12 1310Index:

a[ i ]

Suchschlüssel gefunden an Position i = 10

lineare Suche

 

C. Endreß 1 / 14 10/2008

5/12/2018 Java16 - Suchen Und Sortieren - slidepdf.com

http://slidepdf.com/reader/full/java16-suchen-und-sortieren 2/14

  16. Suchen und Sortieren 

 Als Ergebnis der Suche kann entweder die Position des gesuchten Elements zurückgegeben werden oderauch nur die Information ob das gesuchte Element in der Liste enthalten ist.

Das Struktogramm zeigt eine Funktion, die bei erfolgreicher Suche die Schlüsselposition zurückgibt, derenWert zwischen 0 und (n – 1) liegt. Ist das gesuchte Element nicht im Feld enthalten, liefert die Funktion denWert n zurück.

lineareSuche( int a[ ], int n, int k )

int i = 0

while( i < n && k != a[ i ] )

i = i + 1

return i

 Aufwandsbetrachtung

Unter der Komplexität eines Algorithmus versteht man den zu seiner Durchführung erforderlichen Aufwandan Betriebsmitteln wie Rechenzeit und Speicherplatz.

Die asymptotische Zeitkomplexität wird als Ordnung bezeichnet und durch ein großes O ausgedrückt: O(n). Wenn ein Algorithmus Eingabedaten des Umfangs n verarbeitet, und der Zeitaufwand linear ist,besitzt der Algorithmus die Ordnung n. Seine Zeitkomplexität ist dann proportional n.

Für die lineare Suche in einer Liste gilt: Enthält die Liste n Elemente, dann werden im schlechtesten Fall n  

Schlüsselvergleiche für eine erfolgreiche Suche benötigt. Nimmt man an, dass die Verteilung der Schlüsselgleichwahrscheinlich ist, dann ist zu erwarten, dass für eine erfolgreiche Suche im Mittel

∑=

+=⋅

n

1i2

1ni

n

Schlüsselvergleiche durchzuführen sind.

Lineare Suche:  O(n) = n 

16.1.2  Binäre Suche

Liegen die Schlüssel geordnet in einer linearen Liste vor, kann eine binäre Suche durchgeführt werden.In einem sortierten Feld kann man deutlich schneller suchen.

Binäre Suche: Man vergleicht zunächst den Suchschlüssel mit dem Element in der Mitte des Feldes. Ist derSuchschlüssel kleiner als das mittlere Element, setzt man die Suche im unteren Teilfeld fort. Ist derSuchschlüssel größer als das mittlere Element, wird die Suche im oberen Teilfeld fortgeführt. Imausgewählten Teilfeld vergleicht man nun den Suchschlüssel wieder mit dem mittleren Element des

Teilfeldes. Gegebenenfalls muss das Teilfeld erneut halbiert und die Suche nach dem beschrieben Verfahrenfortgesetzt werden, bis das gesuchte Element gefunden ist oder nur noch ein Element übrig bleibt.

C. Endreß 2 / 14 10/2008

5/12/2018 Java16 - Suchen Und Sortieren - slidepdf.com

http://slidepdf.com/reader/full/java16-suchen-und-sortieren 3/14

  16. Suchen und Sortieren 

Beispiel 1: Suchschlüssel im Feld vorhanden

Feld: a[ ]Feldlänge: n =14

Suchschlüssel: k = 8

Teilfeldgrenzen: low, highTeilfeldmitte: m

Beispiel 2: Suchschlüssel ist nicht im Feld vorhanden

6 8 13 16 19 27 29 33 47 52 57 595

Index:

2

2 3 4 5 6 7 8 9 10 11 12 1310

low = 0, high = 13m = 6

Suchschlüssel gefunden an Position i = 3

low = 0, high = 5m = 2

2 5 6 8 13 16

low = 3, high = 5m = 4

8 13 16

low = 3, high = 3m = 38

Feld: a[ ]Feldlänge: n =14

Suchschlüssel: k = 54

Teilfeldgrenzen: low, highTeilfeldmitte: m

6 8 13 16 19 27 29 33 47 52 57 5952

2 3 4 5 6 7 8 9 10 11 12 1310Index:

low = 0, high = 13

m = 6

Suchschlüssel nicht gefunden

low = 7, high = 13m = 10

low = 11, high = 11m = 11

low = 11, high = 13m = 12

27 29 33 47 52 57 59

52 57 59

52

C. Endreß 3 / 14 10/2008

5/12/2018 Java16 - Suchen Und Sortieren - slidepdf.com

http://slidepdf.com/reader/full/java16-suchen-und-sortieren 4/14

  16. Suchen und Sortieren 

Der Suchalgorithmus kann sowohl rekursiv als auch iterativ formuliert werden. Die folgenden Struktogrammezeigen mögliche Formulierungen einer rekursiven sowie einer iterativen Funktion binSuche .

int binSuche( int a[ ], int k, int low, int high )

int m = (low + high) / 2 

low <= high  ja  nein

k = a[ m ]  ja  nein 

return m k < a[ m ]

 ja  nein 

return binSuche(a, k, low, m - 1) return binSuche(a, k, m + 1, high) 

return -1

Rekursive Formulierung der binären Suche

int binSuche( int a[ ], int n, int k )

int m 

int low = 0 

int high = n - 1

while( low <= high)

m = ( low + high ) / 2

k = a[ m ] ja  nein

return m

k > a[ m ] ja nein

low = m + 1 high = m - 1

return -1 

Iterative Formulierung der binären Suche

 AufwandsbetrachtungEntscheidend für den Aufwand ist die Anzahl der notwendigen Halbierungen, die natürlich von der Anzahlder Feldelemente abhängt. Im schlechtesten Fall sind so viele Halbierungen vorzunehmen, bis nur noch einElement zu betrachten ist. Der Aufwand für eine binäre Suche ist durch die maximale Anzahl derHalbierungen des Feldes begrenzt.

  Anzahl der Halbierungen 0 1 2 3 4 5 6 7 k 

Länge des zubetrachtenden Teilfeldes n n/2 n/4 n/8 n/16 n/32 n/64 n/128 n/2k 

 

C. Endreß 4 / 14 10/2008

5/12/2018 Java16 - Suchen Und Sortieren - slidepdf.com

http://slidepdf.com/reader/full/java16-suchen-und-sortieren 5/14

  16. Suchen und Sortieren 

Da die Mindestgröße des zu betrachtenden Teilfeldes 1 sein muss, ergibt sich die folgende Ungleichung:

12

nk

≥ .

Löst man diese Ungleichung durch Logarithmieren nach k auf, ergibt sich für die Anzahl der Halbierungen:

)n(logk 2≤  

Das gesuchte Element ist also nach maximal log2(n) Halbierungsschritten gefunden.

Binäre Suche: O(n) = log2 (n)

16.2  SortierenIn vielen Anwendungen muss eine Folge von Objekten in eine bestimmte Reihefolge gebracht werden. AlsBeispiel sei hier auf ein Telefonverzeichnis hingewiesen, in dem die Einträge alphabetisch nach Namen zusortieren sind. Bei kaufmännisch-administrativen Anwendungen werden beispielsweise 25 % derComputerzeit für Sortiervorgänge benötigt. Daher wurde intensiv nach effizienten Sortieralgorithmengesucht, die sich nach folgenden Kriterien klassifizieren lassen:

  Zeitverhalten

  Interne vs. externe Sortierung, d.h. passen die zu sortierenden Schlüssel alle in den Arbeitsspeicher odernicht.

   Arbeitsspeicherverbrauch, d.h. wird zusätzlicher Speicherplatz außer dem Platz für die Schlüsselbenötigt.

  Stabiles vs. instabiles Verhalten, d.h. die Reihenfolge von Elementen mit gleichem Sortierschlüssel wirdwährend des Sortierens nicht vertauscht. Stabilität ist oft erwünscht, wenn die Elemente bereits nacheinem zweitrangigen Schlüssel geordnet sind (z.B. Name, Vorname)

  Sensibilität bezogen auf die Eingabeverteilung, d.h. verändert sich das Zeitverhalten, wenn dieEingabefolge bereits sortiert oder vollständig unsortiert ist.

   Allgemeines vs. spezielles Verhalten, d.h. wird nur eine lineare Ordnung auf der Menge der Schlüsselvorausgesetzt oder müssen die Schlüssel von spezieller Gestalt sein.

  Anhand dieser Kriterien ist für ein gegebenes Sortierproblem eine geeignete Auswahl zu treffen. DasHauptkriterium ist natürlich das Zeitverhalten. Dazu gilt folgender Satz:

Kein Sortierverfahren kommt mit weniger als n log2( n )  Vergleichen zwischen Schlüsseln aus.

C. Endreß 5 / 14 10/2008

5/12/2018 Java16 - Suchen Und Sortieren - slidepdf.com

http://slidepdf.com/reader/full/java16-suchen-und-sortieren 6/14

  16. Suchen und Sortieren 

Die folgende Abbildung gibt einen Überblick über bekannte Sortierverfahren, die nach ihrem Zeitverhaltenklassifiziert sind.

16.2.1  Bubble-Sort

Bubble-Sort:  Durchlaufe das Feld in aufsteigender Richtung. Betrachte dabei immer zwei benachbarte

Elemente. Wenn die zwei benachbarten Elemente nicht in aufsteigender Ordnung sind, vertausche sie. Nachdem ersten Durchlauf ist auf jeden Fall das größte Element am Ende des Feldes.

Wiederhole den obigen Verfahrensschritt so lange, bis das Feld vollständig sortiert ist. Dabei muss jeweilsdas letzte Element des vorherigen Durchlaufs nicht mehr betrachtet werden, da es schon seine endgültigePosition gefunden hat.

Beispiel:

Für kleine n (n < 500) Für große n (n >= 500)

Schlüsselvergleiche: O(n) = n2

(für zufällig sortierte Folgen)

Sortieren durch Auswahl(selection sort) 

Sortieren durch Austauschen(bubblesort, exchange sort) 

Sortieren durch Einfügen (insertion sort) 

Mischsortieren(mergesort) 

Sortieren mit einer Halde(Heapsort) 

Quicksort

Schlüsselvergleiche: O(n) = n log2(n)

Elementare Verfahren Schnelle Verfahren

Sortierverfahren

320 178 86 207 59

178 320 86 207 59

178 86 320 207 59

178 86 207 320 59

178 86 207 59 320

1. Durchgang

0 1 2 3 4

C. Endreß 6 / 14 10/2008

5/12/2018 Java16 - Suchen Und Sortieren - slidepdf.com

http://slidepdf.com/reader/full/java16-suchen-und-sortieren 7/14

  16. Suchen und Sortieren 

178 86 207 59 320

86 178 207 59 320

86 178 207 59 320

86 178 59 207 320

2. Durchgang

3. Durchgang

86 178 59 207 320

86 178 59 207 320

86 59 178 207 320

86 59 178 207 320

59 86 178 207 320

4. Durchgang

Der Name Bubble-Sort rührt daher, dass man das Wandern des größten Elements ganz nach rechts mit dem Aufsteigen von Luftblasen vergleichen kann.

Der Algorithmus kann folgendermaßen mit einem Struktogramm formuliert werden:

void bubbleSort( int a[ ], int n )

int temp 

for( int i = n - 1; i > 0; i-- )

for( int k = 0; k < i; k++ )

a[ k ] > a[ k + 1 ] ja  nein

temp = a[ k ]

a[ k ] = a[ k + 1 ]

a[ k + 1 ] = temp

 

Bubble-Sort

C. Endreß 7 / 14 10/2008

5/12/2018 Java16 - Suchen Und Sortieren - slidepdf.com

http://slidepdf.com/reader/full/java16-suchen-und-sortieren 8/14

  16. Suchen und Sortieren 

 Aufwandsbetrachtung

Strukturell besteht der Bubble-Sort-Algorithmus aus einem Kern, der in zwei Schleifen eingebettet ist. DieLaufzeit des Kerns hängt natürlich davon ab, ob eine Vertauschung durchzuführen ist oder nicht. Imgünstigsten Fall (best case ) ist das Feld bereits sortiert und es findet keine Vertauschung von Elementenstatt. Im ungünstigsten Fall (worst case ) erfolgt jedoch bei jedem Kerndurchlauf eine Vertauschung.

Wenn wir eine zufällige Verteilung der Daten annehmen, können wir davon ausgehen, dass in etwa derHälfte aller Kerndurchläufe eine Vertauschung durchzuführen ist. Der Kern wird also bei zufälliger Verteilungeine mittlere Laufzeit haben, die etwa die Hälfte der zur Vertauschung von zwei Elementen benötigtenRechenzeit ausmacht. Der Wert dieser Rechenzeit ist natürlich abhängig von der Plattform, auf der der

 Algorithmus abläuft, sowie von dem Datentyp der Elemente. Strings oder Objekte benötigen eine wesentlichlängere Rechenzeit zur Vertauschung als elementare Datentypen.

Unter der oben gemachten Annahme einer mittleren Rechenzeit für den Algorithmuskern lässt sich dieKomplexität des Algorithmus nach folgender Überlegung berechnen:

Beim ersten Durchlauf durch das Feld läuft die Laufvariable k der inneren Schleife von 0 bis n-2. Die innereSchleife wird also n-1 mal durchlaufen. Beim zweiten Durchlauf wird die innere Schleife nur noch n-2 maldurchlaufen. Beim dritten Durchlauf sind es nur noch n-3 Läufe durch die innere Schleife. Beim letztenDurchlauf wird die innere Schleife schließlich nur noch einmal durchlaufen. Daraus ergibt sich für die SummeS der Läufe durch den Kern:

∑−

=

=++++−+−+−=1n

1i

i123...)3n()2n()1n(S  

Zur Berechnung der Summe verdoppeln wir beide Seiten der Gleichung:

)1n()2n()3n(321

123)3n()2n()1n(S2

−+−+−++++

+++++−+−+−=⋅

K

K

 

n)1n(S2 ⋅−=⋅  

2

n)1n(S

⋅−=  

  Aus der oben hergeleiteten Formel folgt, dass der Bubble-Sort-Algorithmus ein quadratischesLaufzeitverhalten aufweist.

Bubble Sort: O(n) = n2

 

16.2.2  Insertion-Sort

Insertion-Sort ist ein Sortierverfahren, das so arbeitet wie wir Spielkarten auf der Hand sortieren.

Insertion-Sort: Die erste Karte ganz links ist sortiert. Wir nehmen die zweite Karte und stecken sie, jenach Größe, vor oder hinter die erste Karte. Damit sind die beiden ersten Karten relativ zueinander sortiert.Wir nehmen die dritte Karte und schieben sie solange nach links, bis wir an die Stelle kommen, an der sie

passt. Dort stecken wir sie hinein. Für alle weiteren Karten verfahren wir der Reihe nach ebenso.

C. Endreß 8 / 14 10/2008

5/12/2018 Java16 - Suchen Und Sortieren - slidepdf.com

http://slidepdf.com/reader/full/java16-suchen-und-sortieren 9/14

  16. Suchen und Sortieren 

In einem Array funktioniert das natürlich nicht ganz so leicht wie in einem Kartenspiel, da wir nicht einfachein von rechts kommendes Element dazwischen schieben können. Dazu müssen zunächst alleübersprungenen Elemente nach rechts aufrücken, um für das einzusetzende Element Platz zu machen.

0 1 2 3 4

320 178 86 207 101

1. Durchlauf 320 86 207 101

178

178 320 207 101

86

86 178 320 101

207

86 178 207 320

101

86 101 178 207 320

2. Durchlauf 

3. Durchlauf 

4. Durchlauf 

sortiertes Feld

Insertion-Sort

void insertionSort( int a [ ], int n )

unsortiertes Feld

int element, i, j

for( i = 1; i < n; i++ )

element = a[ i ]

 j = i

while( j > 0 && element < a[ j - 1 ] )

a[ j ] = a[ j - 1 ]

 j = j - 1

a[ j ] = element

C. Endreß 9 / 14 10/2008

5/12/2018 Java16 - Suchen Und Sortieren - slidepdf.com

http://slidepdf.com/reader/full/java16-suchen-und-sortieren 10/14

  16. Suchen und Sortieren 

 Aufwandsbetrachtung

Beim Insertion-Sort-Verfahren hwird jedoch die innere Schleife ü

aben wir zwei ineinander verschachtelte Schleifen zu analysieren. Hierbeiber eine zusätzliche Bedingung (element < a[ j – 1 ]) gesteuert. Bei zufällig

 ⎠⎜⎝ 1i 1 j

2ins1ins

 

verteilten Daten können wir davon ausgehen, dass diese Bedingung im Mittel bei der Hälfte des zudurchlaufenden Indexbereichs erfüllt ist, die Schleife also im Durchschnitt auf halber Strecke abgebrochen

werden kann. Bezeichnen wir die Laufzeit der inneren Schleife mit cins2 und die Laufzeit der äußeren Schleifemit cins1, so ergibt sich die folgende Formel für das Laufzeitverhalten von Insertion-Sort:

∑ ∑−

⎟ ⎞

⎜⎛ 

+=1n 2 / i

cc)n(t  = =

∑=

⎟ ⎠

 ⎞⎜⎝ 

⎛ ⋅+=

1i2ins1ins c

2i

c)n(t  −1n

  ( ) ∑=

⋅+−=−n

1i

2ins1ins i

2

c1nc)n(t  

1

(( )

)4

c1nc)n(t 2ins1ins ⋅+−=  1nn −⋅

wir wieder asymptotisch quadra alten.  Auch hier haben tisches Verh

Insertion-Sort: O(n) = n2

16.2.3  Quicksort

n wurde 1960 von C.A.R. Hoare erfunden ist eines der schnellstenlder, die weitgehend unsortiert sind.

e wird durch

  Das Quicksort-VerfahreSortierverfahren für Fe

  Der Grundgedanke von Quicksort verfolgt die Divide-and-Conquer-Strategie: eine FolgZerlegen in kleinere Teilfolgen sortiert.

Qu i tierenden Feld ein als Pivotelement  (Angelpunkt) bezeichnetescksort: Zu Beginn wird in dem zu sorElement beliebig gewählt. In einem Durchlauf werden dann die Feldelemente so miteinander vertauscht,dass am Ende des Durchlaufs das Pivotelement das Feld in ein linkes Teilfeld und ein rechtes Teilfeld zerlegt.

  Alle Elemente des linken Teilfeldes sind kleiner oder gleich dem Pivotelement, die Elemente des rechtenTeilfeldes sind größer oder gleich dem Pivotelement. Damit hat das Pivotelement seine endgültige Position indem Feld eingenommen. Mit den beiden Teilfeldern wird nun in gleicher Weise verfahren, bis ein Teilfeld nurnoch ein oder gar kein Element mehr enthält und somit sortiert ist.

C. Endreß 10 / 14 10/2008

5/12/2018 Java16 - Suchen Und Sortieren - slidepdf.com

http://slidepdf.com/reader/full/java16-suchen-und-sortieren 11/14

  16. Suchen und Sortieren 

Beispiel:

Das Feld a[ ] mit 10 Elementen ist zu sortieren. In der Folge wird das Element in derFeldmitte (a[m] = 60) als Pivotelement für eine Aufteilung der Folge in zwei Teilfolgenausgewählt.

 Als nächstes wird die Folge von links durchsucht, bis ein Element gefunden wird, das größerals das Pivotelement oder das Pivotelement selbst ist. Das ist bereits bei a[0] = 76 der Fall.

  Von rechts wird die Folge durchsucht, bis ein Element gefunden wird, das kleiner als dasPivotelement oder das Pivotelement selbst ist. Die Suche hält bei a[8] = 49 an. Die Elementea[0] und a[8] werden anschließend vertauscht.

Die Suche wird von links mit dem Index 1 und von rechts mit dem Index 7 fortgesetzt. Dienächsten Elemente, die vertauscht werden sind im linken Teilfeld a[3] = 88 und im rechtenTeilfeld a[5] = 41.

Der linke Suchindex wird auf 4 gesetzt. Der rechte Index erhält ebenfalls den Wert 4. DieSuchbereiche überschneiden sich damit und der Durchlauf wird beendet. Das Pivotelement hatseinen endgültigen Platz erreicht. Im linken Teilfeld befinden sich nur noch Werte, die kleinerals der Pivot a[4] sind. Die Werte im rechten Teilfeld sind größer als der Pivot.

Die beiden Teilfelder werden nun rekursiv nach demselben Verfahren sortiert.

Sortierung des lin ken Teilfelds a[0] . . . a[3]:

Rekursions-ebene 1

 Als Pivot wird a[1] festgelegt. Die Suche von linksergibt, dass a[0] größer als das Pivotelement ist.Der rechte Index läuft bis zum Pivotelement, dakein Element im rechten Feld kleiner als der Pivotist. a[0] und der Pivot a[1] werden getauscht.

Die Suchbereiche überschneiden sich, dasPivotelement hat seine endgültige Position imFeld bei a[0] erreicht. Das linke Teilfeld ist leer.Das rechte Teilfeld a[1]...a[3] wird in dernächsten Rekursionsebene bearbeitet

0 91 82 73 4 5 6

76 7 58 88 60 41 82

Suche

77 49 86

von links

76 867 58 88 60 41 82 77 49

Suche

von rechtsElemente vertauschen

0 91 82 73 4 5 6

0 91 82 73 4 5 6

49 867 58 88 60 41 82 77 76

49 867 58 41 60 88 82 77 76

Überschneidung beim Durchsuchen

0 91 82 73 4 5 6

0 1 2 3

49 7 58 41

7 49 58 41

0 1 2 3

C. Endreß 11 / 14 10/2008

5/12/2018 Java16 - Suchen Und Sortieren - slidepdf.com

http://slidepdf.com/reader/full/java16-suchen-und-sortieren 12/14

  16. Suchen und Sortieren 

Rekursions-ebene 2

Das Pivotelement wird aus der Feldmitte (a[2])gewählt. Das Element a[3] des rechten Feldeswird mit dem Pivot vertauscht, da es kleiner ist.

Es kommt wieder zu einer Überschneidung derSuchbereiche von links und rechts. Der Durchlauf wird abgebrochen. Das linke Teilfeld a[1]...a[2]wird in der nächsten Rekursionsebene sortiert.

Rekursions-ebene 3

Das Element a[1] wird als Pivot gewählt. DieElemente werden vertauscht.

Da das linke Teilfeld nur ein Element enthält, istes sortiert. Das rechte Teilfeld ist leer. Damit istdie gesamte Teilfolge a[0]...a[3] links des erstenPivotelements a[4] sortiert.

Die Sortierung des rech ten Teilfeldes a[5] . . . a[9] erfolgt analog: 

Rekursions-ebene 1

Die Suchbereichüberschneidung beendet denDurchlauf. Das linke Teilfeld besteht nur noch auseinem Element (a[5]) und ist deshalb sortiert. DasElement a[6] befindet sich ebenfalls an seiner

endgültigen Position. Das rechte Teilfelda[7]...a[9] wird in der nächsten Rekursionsebenesortiert.

Rekursions-ebene 2

 Als Pivot wird wieder die Feldmitte gewählt (a[8])

Das Pivotelement hat seinen Platz erreicht. Dielinke Teilfolge wird wieder rekursiv sortiert.

1 2 3

49 58 41

1 2 3

49 5841

1 2

49 41

41 49

1 2

9875 6

8688 82 77 76

9875 6

8676 82 77 88

8676 82 8877

9875 6

7 8 9

82 88 86

82 86 88

7 8 9

C. Endreß 12 / 14 10/2008

5/12/2018 Java16 - Suchen Und Sortieren - slidepdf.com

http://slidepdf.com/reader/full/java16-suchen-und-sortieren 13/14

  16. Suchen und Sortieren 

Rekursions-ebene 3

a[7] wird als Pivot gewählt. Die Suchbereicheüberschneiden sich. Die Elemente sind sortiert

Fertig sortierte Folge:

Der Quicksort-Algorithmus arbeitet rekursiv:

 AufwandsbetrachtungWenn wir eine zentrierte Lage des Pivots unterstellen, erfolgt eine fortlaufende Halbierung der Teilfelder, sodass das Feld mit log2 n Halbierungen sortiert ist. Um jedes Element mit dem Pivot zu vergleichen, sind n–1

 Vergleiche und im Mittel n/2 Vertauschungen notwendig. Daraus ergibt sich im Mittel ein Aufwand von

Quicksort: O(n) = n * log2 n

82 86

7 8

0 91 82 73 4 5 6

887 41 49 58 60 76 77 82 86

Quicksort

void quickSort( int UnterGrenze, int OberGrenze, int a[ ] )

int links = UnterGrenze

int rechts = OberGrenze

int pivot = a[ (links + rechts) / 2 ]

while ( links <= rechts )

while ( a[ links ] < pivot )

links = links + 1

while ( pivot < a[ rechts ] )

rechts = rechts - 1

links <= rechts ja  nein

vertausche( a[ links ], a[ rechts ] )

links = links + 1

rechts = rechts - 1

UnterGrenze < rechts ja nein

quickSort ( UnterGrenze, rechts, a )

links < OberGrenze ja nein

quickSort( links, OberGrenze, a )

C. Endreß 13 / 14 10/2008

5/12/2018 Java16 - Suchen Und Sortieren - slidepdf.com

http://slidepdf.com/reader/full/java16-suchen-und-sortieren 14/14

  16. Suchen und Sortieren 

16.3  Vergleichen von Zeichenketten

  Such- und Sortierverfahren werden häufig auf textuelle Daten angewendet wie z.B. Namen oderBuchtitel. Es ist dann erforderlich, solche Zeichenketten mit einander zu vergleichen.

  Zeichenketten sind in Java Objekte der Klasse String. Zum Vergleich von String-Objekten können dielogischen Operatoren <, >, ==, != nicht verwendet werden. Stattdessen stellt die Klasse String

Instanzmethoden zur Verfügung, mit welchen Zeichenketten verglichen werden können.

Methode Beschreibung

compareTo(String s)

compareToIgnoreCase(String s)Lexikalischer Vergleich zweier Strings:

Bei einem lexikalischen Vergleich werden die Zeichenpaarweise von links nach rechts verglichen. Tritt einUnterschied auf oder ist einer der Strings beendet, wird dasErgebnis ermittelt.

Ist das aktuelle String-Objekt kleiner als s, wird ein negativerWert zurückgegeben. Ist es größer, wird ein positiver Wertzurückgegeben. Bei Gleichheit liefert die Methode denRückgabewert 0.

equals(String s)

equalsIgnoreCase(String s)Prüfen auf Gleichheit:

Die Methoden liefern true, wenn das aktuelle String-Objektund der Parameter s inhaltlich gleich sind.

Beispiel:

String name1 = “Adam“;String name2 = “Eva“;

name1.compareTo(name2) liefert -1, weil “Adam“ im Lexikon vor “Eva“ steht.

C. Endreß 14 / 14 10/2008


Recommended