-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSorting.html
More file actions
599 lines (595 loc) · 33.6 KB
/
Sorting.html
File metadata and controls
599 lines (595 loc) · 33.6 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
<!DOCTYPE html><html lang="de"><head>
<title>Variationen zum Thema: Algorithmen</title>
<meta name="title" content="Variationen zum Thema: Algorithmen">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta charset="UTF-8">
<meta name="description" content="Eine Einführung anhand von Beispielen">
<meta name="keywords" content="Java,Algorithmen,Datenstrukturen">
<meta name="author" content="Ralph P. Lano">
<meta name="robots" content="index,follow">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link rel="stylesheet" type="text/css" href="book.css">
</head>
<body><center>
<div id="wrap">
<ul class="sidenav">
<p><a href="index.html">Variationen zum Thema</a><a href="index.html">Algorithmen</a></p>
<li><a href="Introduction.html">Introduction</a></li>
<li><a href="Lists.html">Lists</a></li>
<li><a href="Maps.html">Maps</a></li>
<li><a href="Recursion.html">Recursion</a></li>
<li><a href="Algorithms.html">Algorithms</a></li>
<li><a href="Sorting.html" class="active">Sorting</a></li>
<li><a href="Trees.html">Trees</a></li>
<li><a href="Graphs.html">Graphs</a></li>
<li><a href="Text.html">Text</a></li>
<li><a href="Techniques.html">Techniques</a></li>
</ul>
<div class="content"><p>
<img src="images/Cards.png" style="display: block; margin-left: auto; margin-right: auto; width: 155px; height: 151px;" /></p>
<h1>
Sorting</h1>
<p>
Schon Aschenputtel wußte wie wichtig es ist schnell sortieren zu können: "die guten ins Töpfchen, die schlechten ins Kröpfchen" [7]. Und auch der damalige Präsidentschaftskandidat und spätere Präsident, Barack Obama, wusste bei einem Interview mit Google's Eric Schmidt [8], dass Bubble Sort kein besonders guter Sortieralgorithmus ist. Aber was ist denn ein guter Sortieralgorithmus? Darum geht es in diesem Kapitel: wir stellen die vier wichtigsten Sortieralgorithmen vor, und zeigen deren jeweilgen Stärken und Schwächen. Wir werden auch sehen wie man gut mischt, sozusagen das Gegenstück zum Sortieren. Und schließlich werden wir sehen welche Verbindung zwischen Suche und Sortierung besteht.</p>
<p>
.</p>
<h2>
Shuffle</h2>
<p>
Bevor wir uns mit dem Sortieren beschäftigen können, müssen wir uns erst einmal kurz mit dem Mischen auseinandersetzen. Sonst haben wir ja nichts zum sortieren. Das richtige Mischen ist gar nicht so einfach und man muss sich da schon ein paar Gedanken machen. Gott sei Dank hat das schon jemand gemacht: die Herren Fisher und Yates [1]. Der sogenannte Fisher-Yates Algorithmus wird heutzutage am häufigsten verwendet. Sehen wir ihn uns mal an: wir wollen ein gegebenes Array von Ganzzahlen mischen:</p>
<pre style="margin-left: 40px;">
private void shuffle(int[] arr) {
int n = arr.length;
for (int i = 0; i < n; i++) {
int j = (int)(Math.random() * n);
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}</pre>
<p>
Eigentlich ganz einfach: wir gehen durch das ganze Array, beginnend mit dem ersten Element, und tauschen eines nach dem anderen mit einem anderen zufällig ausgewählten Element aus.</p>
<p>
Eine etwas schnellere Version des gleichen Algorithmus [2] erinnert sich, dass der erste Teil des Arrays bereits gemischt ist und daher die Zufallszahl eigentlich nur aus der hinteren Hälfte kommen muss:</p>
<pre style="margin-left: 40px;">
private static void shuffleFast(int[] arr) {
int n = arr.length;
for (int i = 0; i < n; i++) {
int j = <span style="color:#0000ff;">i+ (int)(Math.random() * (n-i))</span>;
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}</pre>
<p>
Diese zweite Version ist ein klein wenig schneller, aber beide Algorithmen führen das Shuffling in linearer Zeit durch, also O(n). Obwohl das Mischen wie eine triviale Übung erscheinen mag, kann überraschend viel dabei schief gehen, z.B. beim Generieren der Zufallszahlen [1].</p>
<p>
.</p>
<h2>
Sorting</h2>
<p>
Kommen wir endlich zum Sortieren. Nehmen wir an wir haben ein Array von Ganzzahlen, das wir gerne sortiert hätten. Wie macht man das? Nun in Java ist das ganz einfach:</p>
<pre style="margin-left: 40px;">
int[] arrOfInts = { 5, 55, 2, 7, 45, 3, 1, 8, 23, 12 };
Arrays.sort(arrOfInts);</pre>
<p>
Wir verwenden einfach die Methode <em>sort()</em> der Klasse Arrays, die macht das. Ganz einfach, Kapitel zu Ende. </p>
<p>
Nun das hier wäre kein Buch über Algorithmen wenn wir nicht auch etwas über Sortieralgorthmen erfahren würden. Deswegen, was macht denn <em>Arrays.sort()</em> eigentlich?</p>
<p>
.</p>
<h2>
Selection Sort</h2>
<p>
Sortieralgorithmen gibt es wie Sand am Meer, im Duzent sind sie billiger. Wir fangen aber mit dem einfachsten an, dem <em>Selection Sort</em>. Im Prinzip kennt jeder den Selection Sort der schon mal Karten gespielt hat: man nimmt seinen Stapel, sucht nach der kleinsten und setzt die an den Anfang. Dann sucht man nach der nächst kleinsten und setzt die daneben. Das macht man solange bis man den Stapel durch hat. Das übersetzen wir jetzt so, dass es auch der Computer kapiert:</p>
<ol>
<li>
suche nach der kleinsten Zahl und setze sie an den Anfang;</li>
<li>
suche nach der nächst kleinsten und setze sie daneben;</li>
<li>
mach das solange bis du alle Zahlen durch hast.</li>
</ol>
<p>
In Java sieht das Ganze dann so aus:</p>
<pre style="margin-left: 40px;">
1. public void sort(int arr[]) {
2. for (int i = 0; i < arr.length - 1; i++) {
3. int min = i;
4. for (int j = i + 1; j < arr.length; j++) {
5. if (arr[j] < arr[min]) {
6. min = j;
7. }
8. }
9. swap(arr, i, min);
10. }
11. }</pre>
<p>
Dabei tauscht die <em>swap()</em> Methode einfach zwei Elemente in dem Array:</p>
<pre style="margin-left: 40px;">
private void swap(int arr[], int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}</pre>
<p>
So schwer war das gar nicht. Die Frage die uns jetzt interessiert, wie lange dauert das denn? Betrachten wir die verschiedenen Teile:</p>
<ol>
<li>
die swap() Methode ist einfach, sie benötigt immer 3 Instruktionen;</li>
<li>
Zeilen 5 und 6 sind ein Vergleich und evtl. eine Zuweisung, also im Schnitt 1.5 Instruktionen;</li>
<li>
die innere for-Schleife, Zeilen 4 bis 8, besteht aus einem Vergleich und einem Inkrement, die bei jedem Schleifendurchlauf ausgeführt werden (2 Instruktionen), zusätzlich kommen noch die Zeilen 5 und 6 dazu. Insgesamt besteht also die innere Schleife aus 3.5 Instruktionen. Wie oft die Schleife durchlaufen wird hängt von der Größe des Arrays ab. Wenn man kurz darüber nachdenkt, dann ist das so im Schnitt n/2 mal, wobei <em>n</em> die Größe des Arrays ist. Das macht dann 3.5 * n/2 Instruktionen;</li>
<li>
die äußere Schleife besteht wieder aus einem Vergleich und einem Inkrement (2 Instruktionen), dazu kommt die Zuweisung in Zeile 3, und natürlich kommt noch die innere Schleife dazu (3.5 * n/2 Instruktionen), dann noch der Swap (3 Instruktionen), macht dann insgesamt 6 + 3.5*n/2 Instruktionen pro Durchlauf;</li>
</ol>
<p>
Da die Schleife n-mal ausgeführt wird, kommt die Summe grob auf</p>
<pre style="margin-left: 40px;">
# of instructions = n * ( 6 + 3.5*n/2 ) = 6*<span style="color:#0000ff;">n</span> + 1.75*<span style="color:#0000ff;">n²</span> ~ <span style="color:#0000ff;">n²</span></pre>
<p>
Was wir hier also haben, ist ein Algorithmus mit quadratischer Laufzeit, O(n²), da der <em>n²</em> Term zum dominanten Term für große <em>n</em> wird. Quadratische Laufzeit ist schlecht. Eigentlich immer wenn man zwei for-Schleifen sieht deutet das auf O(n²) hin.</p>
<p>
.</p>
<h2>
Insertion Sort</h2>
<p>
Kommen wir zur zweiten Sortiermethode, dem <em>Insertion Sort</em>. Der funktioniert so: man nimmt einfach die oberste Karte vom Stapel. Dann nimmt man die nächste Karte vom Stapel, und fügt die vor die erste Karte wenn sie kleiner ist, oder hinter die erste wenn sie größer ist. Dann kommt die nächste Karte vom Stapel, und die wird dann an die richtige Stelle "einsortiert". Wir übersetzen das wieder für den Computer:</p>
<ol>
<li>
nimm die erste Zahl vom Array, die ist sortiert;</li>
<li>
dann nimm die zweite Zahl, wenn die kleiner als die erste ist, setze sie davor, ansonsten dahinter;</li>
<li>
mach das mit den anderen Zahlen aus dem Array, eine nach der anderen, und füge sie in dem neuen Array jeweils an der richtigen Stelle ein.</li>
</ol>
<p>
Daraus wird dann der folgende Code:</p>
<pre style="margin-left: 40px;">
1. public void sort(int arr[]) {
2. for (int i = 1; i < arr.length; i++) {
3. int cur = arr[i];
4. int j = i - 1;
5. while (j >= 0 && arr[j] > cur) {
6. arr[j + 1] = arr[j];
7. arr[j] = cur;
8. j--;
9. }
10. }
11. }</pre>
<p>
Wie schnell ist denn der Insertion Sort? Wir schauen uns die verschiedenen Teile des Codes an:</p>
<ol>
<li>
Zeile 6 ist ein Inkrement und eine Zuweisung, also 2 Instruktionen;</li>
<li>
Zeilen 7 und 8 sind jeweils 1 Instruktion;</li>
<li>
Zeile 5 besteht aus zwei Vergleichen und einer && Operation, macht 3 Instruktionen;</li>
<li>
die innere while-Schleife, Zeilen 5 bis 9, wird im Schnitt n/2 mal augeführt, damit benötigt die innere Schleife 7 * n/2 Instruktionen;</li>
<li>
Zeile 3 ist 1 Instruktion und Zeile 4 ist 2 Instruktionen;</li>
<li>
Zeile 2 ist eine Instruktion und ein Vergleich, macht 2 Instruktionen.</li>
</ol>
<p>
Da die Schleife wieder n-mal ausgeführt wird, kommt das grob auf</p>
<pre style="margin-left: 40px;">
# of instructions = n * ( 5 + 7*n/2 ) = 6*<span style="color:#0000ff;">n</span> + 3.5*<span style="color:#0000ff;">n²</span> ~ <span style="color:#0000ff;">n²</span></pre>
<p>
Also auch der Insertion Sort hat quadratische Laufzeit, O(n²).</p>
<p>
.</p>
<h2>
MergeSort</h2>
<p>
Bisher haben wir zwei Sortieralgorithmen gesehen, beide haben quadratische Laufzeit. Das bedeutet, wenn wir die Größe unseres Arrays verdoppeln, dann vervierfacht sich die Zeit die das dauert. Nun hat sich ein schlauer Mensch (John von Neumann) gedacht, wenn wir ein Array nehmen das nur halb so groß ist, dann würde es nur ein Viertel der Zeit dauern. Und genau das ist die Idee hinter dem <em>Merge Sort</em> Algorithmus:</p>
<ul>
<li>
teile das Array in zwei Hälften;</li>
<li>
rekursiv, sortiere jede Hälfte;</li>
<li>
am Ende füge jeweils beide Hälften zusammen.</li>
</ul>
<p>
Man nennt den Merge Sort auch ’<b>easy-split, hard-join</b>’, denn das Aufspalten ist sehr einfach, die Arrays werden einfach halbiert. Die eigentliche Arbeit (also das Sortieren) erfolgt beim Zusammenfügen.</p>
<p>
Schauen wir uns den Code an:</p>
<pre style="margin-left: 40px;">
public void sort(int arr[]) {
mergeSort(arr);
}</pre>
<p>
dabei ist die <em>mergeSort()</em> Methode rekursiv:</p>
<pre style="margin-left: 40px;">
1. private void <span style="color:#0000ff;">mergeSort</span>(int[] arr) {
2. if (arr.length > 1) {
3. int middle = arr.length / 2;
4. int[] left = Arrays.copyOfRange(arr, 0, middle);
5. int[] right = Arrays.copyOfRange(arr, middle, arr.length);
6. <span style="color:#0000ff;">mergeSort</span>(left);
7. <span style="color:#0000ff;">mergeSort</span>(right);
8. merge(arr, left, right);
9. }
10. }</pre>
<p>
Wie gesagt, die harte Arbeit steckt in der <em>merge()</em> Methode:</p>
<pre style="margin-left: 40px;">
private void merge(int[] arr, int[] left, int[] right) {
int pos = 0;
int leftPos = 0;
int rightPos = 0;
// main merge loop
while (leftPos < left.length && rightPos < right.length) {
if (left[leftPos] < right[rightPos]) {
arr[pos] = left[leftPos];
leftPos++;
} else {
arr[pos] = right[rightPos];
rightPos++;
}
pos++;
}
// copy rest of left half, if needed
while (leftPos < left.length) {
arr[pos] = left[leftPos];
leftPos++;
pos++;
}
// copy rest of right half, if needed
while (rightPos < right.length) {
arr[pos] = right[rightPos];
rightPos++;
pos++;
}
}</pre>
<p>
Und wie lange dauert das? Das ist ein bisschen knifflig, aber fangen wir langsam an. Die Zeit, die in der Methode <em>merge()</em> verbracht wird, ist proportional zur Größe des Arrays. Um das zu sehen, gehen wir mal davon aus, dass die linken und rechten Arrays so sind, dass nach dem "main merge loop" beide leer sind. Dann sind die Zuweisungen in den ersten drei Zeilen 3 Instruktionen. Der innere Teil der while-Schleife ist ein Vergleich, eine Zuweisung und zwei Inkrements, d.h. 4 Befehle. Der Vergleich der while-Schleife selbst besteht aus zwei Vergleichen und einem &&, also 3 Instruktionen, also zusammen beinhaltet die while-Schleife 7 * n Instruktionen. Das bedeutet,</p>
<pre style="margin-left: 40px;">
# of instructions for merge() = 3 + 7*n</pre>
<p>
Was bleibt ist die <em>mergeSort()</em> Methode: Zeile 2 ist ein Vergleich, 1 Instruktion. Zeile 3 ist eine Division und eine Zuordnung, 2 Instruktionen. Zeile 4 und 5 sind interessant: In Java müssen wir eine Kopie machen, aber in C oder C++ wäre es mit Zeiger Arithmetik einfach, ein Array zu halbieren. Da wir uns nur für den Algorithmus interessieren und nicht für Probleme die mit Java oder irgendeiner anderen Sprache zu tun haben, nehmen wir an, dass jede dieser Zeilen nur eine Instruktion ist.</p>
<p>
Was bleibt ist der rekursive Aufruf. Das ist nicht ganz einfach, aber im letzten Kapitel hatten wir mit der <em>powerDC()</em> Methode ein ganz ähnliches Problem. Dort haben wir, um ein Gefühl für das Problem zu bekommen, einfach mal geschaut wie lange es dauert für verschieden große Arrays. Beginnen wir mit einem Array, das nur ein Element hat, also n=1:</p>
<ul>
<li>
<strong>n=1:</strong> es gibt keinen rekursiven Aufruf, nur einen Vergleich in Zeile 2, also insgesamt 1 Instruktion;</li>
<li>
<strong>n=2:</strong> Zeilen 2 bis 5 entsprechen 5 Instruktionen, Zeilen 6 und 7 benötigen je 1 Instruktion, und der merge() in Zeile 8 entspricht 3+7*n = 17 Instruktionen, zusammen also 5+2*1+17 = 24 Instruktionen;</li>
<li>
<strong>n=4:</strong> hier wird n=2 zweimal rekursiv aufgerufen, macht 2*24 Instruktionen, der merge in Zeile 8 entspricht 3+7*n= 31 Instruktionen, was insgesamt zu 5+2*24+31 = 84 Instruktionen führt;</li>
<li>
<strong>n=8:</strong> hier wird n=4 zweimal rekursiv aufgerufen, macht 2*84 Instruktionen, der merge in Zeile 8 entspricht 3+7*n= 59 Instruktionen, was insgesamt 5+2*84+59 = 232 Instruktionen bedeutet;</li>
<li>
<strong>n=16:</strong> hier wird n=8 zweimal rekursiv aufgerufen, macht 2*232 Instruktionen, der merge in Zeile 8 entspricht 3+7*n= 115 Instruktionen, was insgesamt 5+2*232+115 = 584 Instruktionen bedeutet.</li>
</ul>
<p>
Wir könnten jetzt zwar so weitermachen, aber was wir haben genügt schon. Wir tragen unsere Ergebnisse mal in eine Tabelle ein, und vergleichen sie mit <em>n</em>, mit <em>n*log(n)</em> und mit <em>n²</em>:</p>
<table border="1" cellpadding="1" cellspacing="1" height="101" width="473">
<tbody>
<tr>
<td style="text-align: center;">
log(n)</td>
<td align="center">
n</td>
<td align="center">
n * log(n)</td>
<td align="center">
n²</td>
<td align="center">
10* n * log(n)</td>
<td align="center">
<span style="color:#0000ff;">merge()</span></td>
<td align="center">
4* n²</td>
</tr>
<tr>
<td style="text-align: center;">
1</td>
<td align="center">
2</td>
<td align="center">
2</td>
<td align="center">
4</td>
<td align="center">
20</td>
<td align="center">
<span style="color:#0000ff;">24</span></td>
<td align="center">
16</td>
</tr>
<tr>
<td style="text-align: center;">
2</td>
<td align="center">
4</td>
<td align="center">
8</td>
<td align="center">
16</td>
<td align="center">
80</td>
<td align="center">
<span style="color:#0000ff;">84</span></td>
<td align="center">
64</td>
</tr>
<tr>
<td style="text-align: center;">
3</td>
<td align="center">
8</td>
<td align="center">
24</td>
<td align="center">
64</td>
<td align="center">
240</td>
<td align="center">
<span style="color:#0000ff;">232</span></td>
<td align="center">
256</td>
</tr>
<tr>
<td style="text-align: center;">
4</td>
<td align="center">
16</td>
<td align="center">
64</td>
<td align="center">
256</td>
<td align="center">
640</td>
<td align="center">
<span style="color:#0000ff;">584</span></td>
<td align="center">
1024</td>
</tr>
<tr>
<td style="text-align: center;">
5</td>
<td align="center">
32</td>
<td align="center">
160</td>
<td align="center">
1024</td>
<td align="center">
1600</td>
<td align="center">
<span style="color:#0000ff;">1400</span></td>
<td align="center">
4096</td>
</tr>
</tbody>
</table>
<p>
Das ist jetzt kein exakter mathematischer Beweis, aber wenn man sich die Tabelle ansieht, dann ist ziemlich klar, dass sich merge() am ehesten wie <em>n*log(n)</em> verhält und nicht wie <em>n²</em>. Man kann tatsächlich beweisen, dass das der Fall ist. Dies ist das erste Mal, dass wir auf einen Algorithmus stoßen, der ein <em>linearithmisches</em> Laufzeitverhalten hat, d.h. O(n*log(n)). Und das ist eine gute Sache. Merge Sort gehört auch zur Klasse der <em>divide and conquer</em> Algorithmen.</p>
<p>
.</p>
<h2>
QuickSort</h2>
<p>
So wie Merge Sort ist auch <em>Quick Sort</em> ein <em>divide and conquer</em> Algorithmus. Die Grundidee ist folgende:</p>
<ul>
<li>
teile das Array in zwei Hälften, eine mit den niedrigeren Zahlen und eine mit den höheren;</li>
<li>
sortiere jede Hälfte, rekursiv;</li>
<li>
am Ende füge die beiden Hälften einfach aneinander.</li>
</ul>
<p>
Man nennt diese Methode auch ’<span style="font-weight: bold;">hard</span><b>-split, easy-join</b>’. Hier ist das Aufspalten der schwierige Teil, dafür ist das Zusammenfügen einfach. In Bezug auf den Code sieht das so aus:</p>
<pre style="margin-left: 40px;">
public void sort(int arr[]) {
quickSort(arr);
}</pre>
<p>
wobei die <em>quickSort()</em> Methode rekursiv ist und sich selbst aufruft:</p>
<pre style="margin-left: 40px;">
private void <span style="color:#0000ff;">quickSort</span>(int[] arr) {
if (arr.length > 1) {
int pivot = arr[arr.length / 2];
int[] low = getLowerHalf(arr, pivot);
int[] high = getUpperHalf(arr, pivot);
<span style="color:#0000ff;">quickSort</span>(low);
<span style="color:#0000ff;">quickSort</span>(high);
join(arr, low, high);
}
}</pre>
<p>
Wir wollen uns hier nicht mit den Details langweilen, aber man kann auch zeigen, dass Quick Sort linearithmisches Laufzeitverhalten hat. Der einfache Quick Sort hat ein paar kleine Macken, aber die kann man alle beheben.</p>
<p>
So, nun zurück zu unserer ursprünglichen Frage: welchen Algorithmus verwendet denn Arrays.sort()? Wenn wir in der Java Dokumentation der Klasse Arrays nachschlagen, finden wir, dass ein modifizierter und optimierter Quick Sort Algorithmus verwendet wird [3].</p>
<p>
.</p>
<h2>
Which one is the best?</h2>
<p>
Normalerweise ist ein linearithmischer Algorithmus immer besser als ein quadratischer. Aber es gibt Ausnahmen, z.B.:</p>
<ul>
<li>
Insertion Sort ist sehr schnell, wenn die Ausgangsdaten bereits fast sortiert sind. Interessanterweise passiert das relativ häufig in der realen Welt.</li>
<li>
Selection Sort minimiert die Anzahl der Swaps. Also für den Fall, dass ein Swap eine sehr teure Operation ist (z.B. schwere Möbel verschieben), dann kann der Selection Sort die bessere Wahl sein.</li>
</ul>
<p>
Es gibt auch Fälle, in denen z.B. Quick Sort nicht so gut ist. Bleibt die Frage, geht es vielleicht noch schneller als linearithmisch? Die Antwort liefert die Theorie: man kann zeigen, dass es keinen Sortieralgorithmus gibt der schneller als O( n * log(n) ) ist. Das ist o.k. Wie bereits angedeutet, gibt es noch ein paar mehr Sortieralgorithmen, falls Interesse besteht kann man sich die im Internet ansehen [4], die werden auch alle mit einer schönen Animation verglichen, wirklich hübsch.</p>
<p>
.</p>
<hr />
<h1>
Review</h1>
<p>
Wir haben kurz gesehen wie man richtig mischt, danach haben wir uns aber hauptsächlich mit dem Sortieren beschäftigt. Wir haben vier Sortieralgorithmen näher kennen gelernt, and the winner is: QuickSort.</p>
<p>
.</p>
<hr />
<h1>
Projekte</h1>
<p>
In diesem Kapitel gibt es nur wenige Projekte, was nicht heißen soll, dass sie unwichtig sind. Suche ist nämlich ein sehr wichtiges Thema.</p>
<p>
.</p>
<h2>
<img alt="" src="images/Search.png" style="width: 200px; height: 85px; float: right;" />Searching</h2>
<p>
Suchen und Sortieren gehen Hand in Hand. Um das zu zeigen schauen wir uns mehrere verschiedene Möglichkeiten an zu suchen. Als Beispiel verwenden wir folgendes Array von Ganzzahlen:</p>
<pre style="margin-left: 40px;">
int[] arr = { 44, 88, 17, 32, 97, 65, 28, 82, 29, 76, 54, 80 };</pre>
<p>
Darin wollen wir nach der Zahl 17 suchen, die an Position 2 ist, und nach der Zahl 42, die gar nicht in dem Array ist.</p>
<h3>
Sequential Search</h3>
<p>
Als erstes versuchen wir es mal mit der <em>Sequential Search</em>: das ist ein Brute-Force Algorithmus, der einfach alle Einträge des Arrays durchläuft, bis die Zahl die wir suchen, gefunden wird:</p>
<pre style="margin-left: 40px;">
private int sequentialSearch(int key, int[] arr) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == key)
return i;
}
return -1;
}</pre>
<p>
Manchmal wird die Zahl die wir suchen, eher am Anfang des Arrays sein, manchmal eher am Ende. Im Durchschnitt müssen wir also ca. durch die Hälfte des Arrays gehen, wenn die gesuchte Zahl im Array ist, oder wenn sie gar nicht im Array ist, durch das ganze Array. Wir erwarten also ein Laufzeitverhalten, das linear zur Größe des Arrays ist, d.h. O(n).</p>
<h3>
Sequential Search2</h3>
<p>
In einem zweiten Versuch nehmen wir an, dass unser Array sortiert ist:</p>
<pre style="margin-left: 40px;">
int[] arr = { 17, 28, 29, 32, 44, 54, 65, 76, 80, 82, 88, 97 };</pre>
<p>
Wenn wir aber kurz nachdenken, ändert das gar nichts. Das Laufzeitverhalten bleibt bei O(n).</p>
<h3>
Binary Search</h3>
<p>
Aber wir geben nicht so schnell auf: wie wäre es mit einem <em>divide and conquer</em> Ansatz? Angenommen, wir suchen die Zahl 17 und das Array ist sortiert. Dann folgt der <em>Binary Search</em> Algorithmus diesen Schritten:</p>
<ol>
<li>
nimm die Zahl in der Mitte des Arrays (das ist die 54);</li>
<li>
vergleiche sie mit der gesuchten 17;</li>
<li>
sind die beiden gleich, sind wir fertig, wir haben die Zahl gefunden;</li>
<li>
ist 17 kleiner als die Mitte, dann wissen wir, dass 17 unmöglich in der rechten Hälfte des Arrays sein kann, weil es ja sortiert ist, können dort nur Zahlen größer als 54 sein. Also müssen wir für unsere weitere Suche nur in der linken Hälfte suchen. Unser Problem hat sich gerade um die Hälfte reduziert;</li>
<li>
jetzt gehen wir wieder zurück zum ersten Schritt, allerdings nur mit der linken Hälfte. Das machen wir so lange bis wir entweder die Zahl gefunden haben, oder bis das Array nur noch ein Element hat.</li>
</ol>
<p>
In Java sieht der Binary Search Algorithmus wie folgt aus:</p>
<pre style="margin-left: 40px;">
private static int binarySearch(int key, int[] arr, int start, int stop) {
// base case
if (start > stop)
return -1;
// recursive case
int mid = (start + stop) / 2;
if (key == arr[mid]) {
return mid;
} else if (key < arr[mid]) {
return binarySearch(key, arr, start, mid - 1);
} else {
return binarySearch(key, arr, mid + 1, stop);
}
}</pre>
<p>
Das Laufzeitverhalten des binären Suchalgorithmus ist O(log(n)), also deutlich besser als die sequentielle Suche. Das ist einer der Gründe, warum Sortieren so wichtig ist, weil es die Suchzeiten drastisch reduzieren hilft.</p>
<h3>
Hash Search</h3>
<p>
Ist die binäre Suche wirklich die schnellste? Und ist die Sortiererei wirklich nötig? Dauert ja auch. Zweimal Nein. Das Sortieren ist nicht unbedingt nötig, und binäre Suche ist auch nicht die schnellste. <em>Hash-based Search</em> ist die schnellste. Wie funktioniert sie? Wir brauchen zwei Schritte: im ersten speichern wir unser Array in einem HashSet:</p>
<pre style="margin-left: 40px;">
Integer[] arr = { 17, 28, 29, 32, 44, 54, 65, 76, 80, 82, 88, 97 };
HashSet<Integer> hs = new HashSet(Arrays.asList(arr));</pre>
<p>
und im zweiten verwenden wir einfach die <em>contains()</em> Methode des HashSets für die Suche:</p>
<pre style="margin-left: 40px;">
boolean b = hs.contains(key);</pre>
<p>
Die Suche selbst hat konstantes Laufzeitverhalten, also O(1). Das ist also noch schneller als O(log(n)). Ausserdem muss unser Array nicht sortiert werden, also wir sparen uns die O(n log(n)) Strafe für das Sortieren. Aber wir müssen unser Array in das HashSet einfügen, und das kostet uns O(n). Trotzdem am Ende noch deutlich schneller!</p>
<pre style="margin-left: 40px;">
sequential search unsorted array: 273830 ms
sequential search sorted array: 245650 ms
binary search sorted array: 41 ms
hash search: 18 ms</pre>
<p>
Obwohl Hash-based Search doppelt so schnell wie Binäre Suche ist, macht es fast keinen Unterschied wenn man beide mit sequentieller Suche vergleicht.</p>
<h3>
Binary Search Tree</h3>
<p>
Es gibt noch eine Suchmethode, die wir in diesem Zusammenhang erwähnen wollen: der binäre Suchbaum. Wir werden sie im Kapitel über Bäume kennenlernen. Sie hat auch logarithmische Suchzeiten, d.h. O(log (n)), und hat auch noch einige andere Vorteile. Dennoch, wenn es um rohe Suchkraft geht: hash is the best!</p>
<p>
.</p>
<h2>
TreeMap</h2>
<p>
In Kapitel drei haben wir bereits in zwei Projekten Bekanntschaft mit der TreeMap gemacht: in Languages und in BuildIndex. Das ist eine ganz normale Map bei der allerdings die Schlüssel automatisch sortiert sind. Welchen Sortieralgorithmus verwendet denn die TreeMap? Interessanterweise keinen der hier behandelten. Anstelle verwendet es einen <em>Red-Black Tree</em> als interne Datenstruktur, der für die Sortierung sorgt. Wir werden mehr dazu im nächsten Kapitel erfahren.</p>
<p>
.</p>
<hr />
<h1>
Research</h1>
<p>
Ein Thema das wir in diesem Buch komplett ausgelassen haben ist der Heap, auch eine interessante Datenstruktur.</p>
<p>
.</p>
<h2>
HeapSort</h2>
<p>
Basierend auf dem Heap gibt es auch ein Sortierverfahren, den HeapSort. Wir sollten vielleicht erst mal nachlesen was denn überhaupt ein Heap ist und danach könnten wir uns mal den HeapSort näher ansehen.</p>
<p>
.</p>
<hr />
<h1>
Fragen</h1>
<ol>
<li>
Bitte erläutern Sie, wie der SelektionSort und der InsertionSort funktionieren.<br />
</li>
<li>
Wie gut ist QuickSort bei der Sortierung bereits sortierter Daten? Wie gut ist InsertionSort beim Sortieren bereits sortierter Daten?<br />
</li>
<li>
Sie haben eine Gruppe von Studenten, die zufällig im Wohnheim auf Zimmer verteilt wurden. Da die Zimmerhöhe aber von hinten nach vorne im Wohnheim abnimmt, wollen Sie die Räume neu zuordnen, so dass die kleineren Studenten in den hinteren Räumen sind, während die größeren in den vorderen. Jeder Student hat eine Menge persönliches Zeug zu schleppen, deswegen sollte die Anzahl der Umzüge minimiert werden. Würden Sie eher einen InsertionSort oder einen SelektionSort Algorithmus verwenden? Warum?</li>
</ol>
<p>
.</p>
<hr />
<h1>
Referenzen</h1>
<p>
Zwei hervorragende Bücher wenn es um Suche geht sind das Buch von Roberts und Zelenski [5], sowie das von Sedgewick and Wayne [2]. Das Buch von Goodrich und Tamassia [6] steigt etwas tiefer in die Materie ein, ist auch sehr zu empfehlen.</p>
<p>
[1] Fisher–Yates shuffle, <a href="https://en.wikipedia.org/wiki/Fisher–Yates_shuffle#The_modern_algorithm">https://en.wikipedia.org/wiki/Fisher–Yates_shuffle#The_modern_algorithm</a></p>
<p>
[2] Introduction to Programming in Java, Robert Sedgewick and Kevin Wayne</p>
<p>
[3] Arrays (Java Platform SE 7 ) - Oracle, <a href="https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html">https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html</a></p>
<p>
[4] Sorting Algorithms Animations, <a href="http://www.sorting-algorithms.com/">http://www.sorting-algorithms.com/</a></p>
<p>
[5] Programming Abstractions in C++, Eric S. Roberts and Julie Zelenski</p>
<p>
[6] Data Structures and Algorithms in Java, M.T. Goodrich and R. Tamassia</p>
<p>
[7] Aschenputtel, <a href="https://de.wikipedia.org/wiki/Aschenputtel_(1989)">https://de.wikipedia.org/wiki/Aschenputtel_(1989)</a></p>
<p>
[8] Barack Obama | Candidates at Google, <a href="https://www.youtube.com/watch?v=m4yVlPqeZwo">https://www.youtube.com/watch?v=m4yVlPqeZwo</a>, (about 23 minutes into the talk)</p>
<p>
.</p>
<p class="footer">
Copyright © 2016-2021 <a href="http://www.lano.de">Ralph P. Lano</a>. All rights reserved.
</p>
</div>
</center>
</div>
</body>
</html>