Java16 - Suchen Und Sortieren

  • View
    24

  • Download
    1

Embed Size (px)

Transcript

16. Suchen und Sortieren

16. Suchen und Sortieren

Lernziele Algorithmen fr lineare und binre Suche erklren und anwenden knnen. Die Begriffe Komplexitt und Ordnung eines Algorithmus kennen. Algorithmen fr die Sortierverfahren Bubble-Sort, Insertion-Sort und Quick-Sort erklren knnen.

16.1 SuchverfahrenDas Suchen von Informationen in Informationsbestnden gehrt zu den hufigsten Aufgaben, die mit Computersystemen ausgefhrt werden. Oft ist die gesuchte Information eindeutig durch einen Schlssel identifizierbar. Schlssel sind in der Regel positive ganze Zahlen (z.B. Artikelnummer, Kontonummer etc.) oder alphabetische Schlssel (z.B. Nachname, Firmenname usw.). Von dem Schlssel gibt es meist eine Referenz auf die eigentlichen Informationen. Die Suchverfahren knnen Kategorien zugeordnet werden: Elementare Suchverfahren: Es werden nur Vergleichsoperationen zwischen den Schlsseln ausgefhrt. Schlssel-Transformationen (Hash-Verfahren): Aus dem Suchschlssel wird mit arithmetischen Operationen direkt die Adresse von Datenstzen berechnet. Suchen in Texten: Suchen eines Musters in einer Zeichenkette.

16.1.1

Lineare Suche

Die lineare bzw. sequentielle Suche wird immer dann angewendet, wenn die Schlssel in ungeordneter Folge in einer Liste abgelegt sind. Lineare Suche: Die Elemente der Liste werden der Reihe nach mit dem Suchschlssel verglichen, bis das passende Element gefunden wird oder das Ende der Liste erreicht ist. Beispiel:

Feld: a[ ] Feldlnge: n =14 Suchschlssel: k = 57 Index: 0 27 1 2 2 13 3 6 4 8 5 16 6 5 7 59 8 47 9 33 10 57 11 19 12 29 13 4

lineare Suche Suchschlssel gefunden an Position i = 10C. Endre 1 / 14

a[ i ]

10/2008

16. Suchen und Sortieren

Als Ergebnis der Suche kann entweder die Position des gesuchten Elements zurckgegeben werden oder auch nur die Information ob das gesuchte Element in der Liste enthalten ist. Das Struktogramm zeigt eine Funktion, die bei erfolgreicher Suche die Schlsselposition zurckgibt, deren Wert zwischen 0 und (n 1) liegt. Ist das gesuchte Element nicht im Feld enthalten, liefert die Funktion den Wert n zurck.lineareSuche( int a[ ], int n, int k ) int i = 0 while( i < n && k != a[ i ] ) i=i+1 return i

AufwandsbetrachtungUnter der Komplexitt eines Algorithmus versteht man den zu seiner Durchfhrung erforderlichen Aufwand an Betriebsmitteln wie Rechenzeit und Speicherplatz. Die asymptotische Zeitkomplexitt wird als Ordnung bezeichnet und durch ein groes O ausgedrckt: O(n). Wenn ein Algorithmus Eingabedaten des Umfangs n verarbeitet, und der Zeitaufwand linear ist, besitzt der Algorithmus die Ordnung n. Seine Zeitkomplexitt ist dann proportional n. Fr die lineare Suche in einer Liste gilt: Enthlt die Liste n Elemente, dann werden im schlechtesten Fall n Schlsselvergleiche fr eine erfolgreiche Suche bentigt. Nimmt man an, dass die Verteilung der Schlssel gleichwahrscheinlich ist, dann ist zu erwarten, dass fr eine erfolgreiche Suche im Mittel1 n

i =i=1

n

n +1 2

Schlsselvergleiche durchzufhren sind. Lineare Suche: O(n) = n

16.1.2

Binre Suche

Liegen die Schlssel geordnet in einer linearen Liste vor, kann eine binre Suche durchgefhrt werden. In einem sortierten Feld kann man deutlich schneller suchen. Binre Suche: Man vergleicht zunchst den Suchschlssel mit dem Element in der Mitte des Feldes. Ist der Suchschlssel kleiner als das mittlere Element, setzt man die Suche im unteren Teilfeld fort. Ist der Suchschlssel grer als das mittlere Element, wird die Suche im oberen Teilfeld fortgefhrt. Im ausgewhlten Teilfeld vergleicht man nun den Suchschlssel wieder mit dem mittleren Element des Teilfeldes. Gegebenenfalls muss das Teilfeld erneut halbiert und die Suche nach dem beschrieben Verfahren fortgesetzt werden, bis das gesuchte Element gefunden ist oder nur noch ein Element brig bleibt.

C. Endre

2 / 14

10/2008

16. Suchen und Sortieren

Beispiel 1: Suchschlssel im Feld vorhandenFeld: a[ ] Feldlnge: n =14 Suchschlssel: k = 8 Teilfeldgrenzen: low, high Teilfeldmitte: m

Index:

0 2

1 5

2 6

3 8

4 13

5 16

6 19

7 27

8 29

9 33

10 47

11 52

12 57

13 59 low = 0, high = 13 m=6 low = 0, high = 5 m=2 low = 3, high = 5 m=4 low = 3, high = 3 m=3

2

5

6

8

13

16

8

13

16

8 Suchschlssel gefunden an Position i = 3

Beispiel 2: Suchschlssel ist nicht im Feld vorhandenFeld: a[ ] Feldlnge: n =14 Suchschlssel: k = 54 Teilfeldgrenzen: low, high Teilfeldmitte: m

Index:

0 2

1 5

2 6

3 8

4 13

5 16

6 19

7 27

8 29

9 33

10 47

11 52

12 57

13 59 low = 0, high = 13 m=6 low = 7, high = 13 m = 10 low = 11, high = 13 m = 12 low = 11, high = 11 m = 11

27

29

33

47

52

57

59

52

57

59

52

Suchschlssel nicht gefunden

C. Endre

3 / 14

10/2008

16. Suchen und Sortieren

Der Suchalgorithmus kann sowohl rekursiv als auch iterativ formuliert werden. Die folgenden Struktogramme zeigen mgliche Formulierungen einer rekursiven sowie einer iterativen Funktion binSuche.

int binSuche( int a[ ], int k, int low, int high ) int m = (low + high) / 2 ja ja k = a[ m ] k < a[ m ] return binSuche(a, k, low, m - 1)Rekursive Formulierung der binren Suche

low = 500)

Elementare Verfahren Schlsselvergleiche: O(n) = n (fr zufllig sortierte Folgen) Sortieren durch Auswahl2

Schnelle Verfahren Schlsselvergleiche: O(n) = n log2(n)

(selection sort)

Mischsortieren

(mergesort)Quicksort

Sortieren durch Austauschen

(bubblesort, exchange sort)Sortieren durch Einfgen

(insertion sort)

Sortieren mit einer Halde

(Heapsort)

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. Nach dem ersten Durchlauf ist auf jeden Fall das grte Element am Ende des Feldes. Wiederhole den obigen Verfahrensschritt so lange, bis das Feld vollstndig sortiert ist. Dabei muss jeweils das letzte Element des vorherigen Durchlaufs nicht mehr betrachtet werden, da es schon seine endgltige Position gefunden hat.

Beispiel:0 320 1 178 2 86 3 207 4 59

178

320

86

207

59

178

86

320

207

59

1. Durchgang

178

86

207

320

59

178

86

207

59

320

C. Endre

6 / 14

10/2008

16. Suchen und Sortieren

178

86

207

59

320

86

178

207

59

320 2. Durchgang

86

178

207

59

320

86

178

59

207

320

86

178

59

207

320

86

178

59

207

320

3. Durchgang

86

59

178

207

320

86

59

178

207

320 4. Durchgang

59

86

178

207

320

Der Name Bubble-Sort rhrt daher, dass man das Wandern des grten Elements ganz nach rechts mit dem Aufsteigen von Luftblasen vergleichen kann. Der Algorithmus kann folgendermaen 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++ ) ja temp = a[ k ] a[ k ] = a[ k + 1 ] a[ k + 1 ] = tempBubble-Sort

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

C. Endre

7 / 14

10/2008

16. Suchen und Sortieren

AufwandsbetrachtungStrukturell besteht der Bubble-Sort-Algorithmus aus einem Kern, der in zwei Schleifen eingebettet ist. Die Laufzeit des Kerns hngt natrlich davon ab, ob eine Vertauschung durchzufhren ist oder nicht. Im gnstigsten Fall (best case) ist das Feld bereits sortiert und es findet keine Vertauschung von Elementen statt. Im ungnstigsten Fall (worst case) erfolgt jedoch bei jedem Kerndurchlauf eine Vertauschung. Wenn wir eine zufllige Verteilung der Daten annehmen, knnen wir davon ausgehen, dass in etwa der Hlfte aller Kerndurchlufe eine Vertauschung durchzufhren ist. Der Kern wird also bei zuflliger Verteilung eine mittlere Laufzeit haben, die etwa die Hlfte der zur Vertauschung von zwei Elementen bentigten Rechenzeit ausmacht. Der Wert dieser Rechenzeit ist natrlich abhngig von der Plattform, auf der der Algorithmus abluft, sowie von dem Datentyp der Elemente. Strings oder Objekte bentigen eine wesentlich lngere Rechenzeit zur Vertauschung als elementare Datentypen. Unter der oben gemachten Annahme einer mittleren Rechenzeit fr den Algorithmuskern lsst sich die Komplexitt des Algorithmus nach folgender berlegung berechnen: Beim ersten Durchlauf durch das Feld luft die Laufvariable k der inneren Schleife von 0 bis n-2. Die innere Schleife wird also n-1 mal durchlaufen. Beim zweiten Durchlauf wird die innere Schleife nur noch n-2 mal durchlaufen. Beim dritten Durchlauf sind es nur noch n-3 Lufe durch die innere Schleife. Beim letzten Durchlauf wird die innere Schleife schlielich nur noch einmal durchlaufen. Daraus ergibt sich fr die Summe S der Lufe durch den Kern:S = (n 1) + (n 2) + (n 3) + . . . + 3 + 2 + 1 =

ii =1

n 1

Zur Berechnung der Summe verdoppeln wir beide Seiten der Gleichung:

2 S = (n 1) + (n 2) + (n 3) + K + 1 + 2 + 32 S = (n 1) n S= (n 1) n 2