algorithms/docs/notes/sorting.html at master · thoward27/algorithms · GitHub

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
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
<!DOCTYPE html>
<html>

<head>
    <title>Sorting</title>
    <meta charset="utf-8">
    <style>
        @import url(https://fonts.googleapis.com/css?family=Droid+Serif);
        @import url(https://fonts.googleapis.com/css?family=Yanone+Kaffeesatz);
        @import url(https://fonts.googleapis.com/css?family=Ubuntu+Mono:400,700,400italic);
        @import "static/base.css";
    </style>
    <script type="text/x-mathjax-config">
        MathJax.Hub.Config({
  tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}
});
</script>
    <script src='https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/latest.js?config=TeX-MML-AM_CHTML' async></script>
</head>

<body>
    <textarea id="source">

class: center, middle

# Sorting

---
name: agenda

## Agenda

.two-columns[
- [Agenda](#agenda)
- [Sorting Motivation](#sorting-motivation)
- [Bubble Sort](#bubble-sort)
- [Selection Sort](#selection-sort)
- [Stable Sorting](#stable-sorting)
- [Insertion Sort](#insertion-sort)
- [MergeSort](#mergesort)
- [QuickSort](#quicksort)
- [Resources](#resources)

]

---
name: sorting-motivation

## Sorting Motivation

There are many use cases for sorting things, it's something you most likely do every day, it's also something your computer does every day, all the time.

Can you think of common things that your computer sorts for you?

--

- Emails
- Articles
- Contacts in your Phone
- Your calendar events

--

The question is, how is your computer sorting so many thing so quickly?

---
name: bubble-sort
class: middle

## Bubble Sort

---

### Bubble Sort: Introduction

What if we simply walk through the list, and repeatedly swap out-of-order elements?

--

Let's start with the array: `[5, 2, 4, 3, 1]`

--

We begin by starting with `5` and `2`, which are swapped: `[2, 5, 4, 3, 1]`

--

Then `5` and `4` must be swapped: `[2, 4, 5, 3, 1]`

--

Now `5` and `3` are out of order: `[2, 4, 3, 5, 1]`.

--

Finally for this pass, we must fix `5` and `1`: `[2, 4, 3, 1, 5]`

--

We must then repeat this process until the entire list is sorted.

--

How much work is required if the list is sorted? Reversed?

---

### Bubble Sort: Implementation

.pull-left[

### A helpful animation

<img src="images/sort_bubble.gif" width="350" height="200">

### Pseudocode

```
While the array is not sorted:
  For each element in the array (except the last):
    If the current element is greater than the next element:
      Swap the current and next element.
```

]

.pull-right[

### Details

- Comparison based sort
- Extremely simple
- Stable: Does not change the relative order of elements of equal value
- Adaptive: Runs in linear time on sorted arrays
- Larger elements "bubble" to the top
- Too slow for practical use

]

---
name: selection-sort
class: middle

## Selection Sort

---

### Selection Sort: Introduction

What if we simply selected the minimum from the array at each pass, and appended it to a sorted sublist?

--

Let's start with the array: `[5, 2, 4, 3, 1]`, and the sorted sublist `[]`

--

Select the smallest element in the list, and append it to the sorted list.

`[2, 4, 3, 5]`, `[1]`

--

We repeat this process, until the unsorted array is empty:

`[4, 3, 5]`, `[1, 2]`

--

`[4, 5]`, `[1, 2, 3]`

--

`[5]`, `[1, 2, 3, 4]`

--

`[]`, `[1, 2, 3, 4, 5]`

--

Although this will work, ideally we would make this work in-place, like bubble sort did.

--

We can accomplish this by using swaps, and using the left side of our array as our sorted portion.

---

### Selection Sort: In-Place

We start with the same array: `[|5, 2, 4, 3, 1]` where the bar denotes the sorted sublist.

--

For each index in the array, from left to right, we select the minimum value in the array, and swap it with our current position.

--

`[1|, 2, 4, 3, 5]` Here we selected the `1`, and swapped it with the `5`.

--

`[1, 2|, 4, 3, 5]` Here we selected the `2`, and swapped it with itself.

--

`[1, 2, 3|, 4, 5]` On this step, we swapped the `3` and the `4`.

--

`[1, 2, 3, 4|, 5]` On this step, we swapped the `4` with itself.

--

And finally, we can swap the `5` with itself, but do we actually have to do this?

--

No, the final element must be the largest, this algorithm can exit safely after evaluating the second to last index.

--

How much work is required for Selection Sort on an already sorted list? Reversed list?

---

### Selection Sort: Implementation

.pull-left[

#### A helpful animation

<img src="images/sort_selection.gif" width="400" height="170">

#### Pseudocode

```
For each i from 0 to n:
  Set the current minimum index to i
  For each j from i + 1 to n:
    If the element at j is less than the element at the current minimum index:
      Set the current minimum index to j
  Swap the elements at i and the current minimum index
```

]

.pull-right[

#### Details

- Starts from the left, selects the minimum element in the array and swaps the value at it's current position with the minimum
- Unstable: Elements relative orders are not preserved, though it can be made stable
- Linear in regards to swaps, which is unique

]

---

### Selection Sort: Analysis

- Worst Case: $O(n^2)$
- Average Case: $O(n^2)$
- Best Case: $O(n^2)$

Selection sort scans the array at each interval searching for the minimum, the total number of comparisons is:

$$(n - 1) + (n - 2) + (n - 3) + ... + 1 = \sum_{i = 1}^{n - 1} i$$

Which evaluates to $O(n^2)$ in all cases.

---
name: stable-sorting
class: middle

## Stable Sorting

---

### Stable Sorting: Overview

If we want equal elements to preserve their order in the original list, we must use a stable sorting algorithm.

Consider if we wanted to sort a list by multiple keys, when we sort by the secondary key, we do not want the primary order to be disrupted!

.pull-left[
  <img src="images/sort_stable.png" width="200" height="350">
]

Let's examine how stable sorting could impact the order of these cards.

We can see that stable sorting preserves the *relative* order of the cards of rank 5.

Can you think of some applications where this may be important?

--

How about flights? They could be sorted by price, then by day, in which case we do not want our list to be out of order by price!

---
name: insertion-sort
class: middle

## Insertion Sort

---

### Insertion Sort: Introduction

What if we *inserted* each element in the array into an already sorted array?

--

Similarly to Selection Sort, we can use the left side of the array to hold the *sorted* elements, and iterate through to the right.

--

Let's start with the array:

`[5|, 2, 4, 3, 1]` Where the `|` marks the end of the sorted sublist.

--

`[2, 5|, 4, 3, 1]` The `2` element gets inserted into the sorted sublist.

--

`[2, 4, 5|, 3, 1]` Then the `4` gets inserted.

--

`[2, 3, 4, 5|, 1]` After the `3` is inserted.

--

Finally, the `1` gets inserted and we have concluded our sort:

`[1, 2, 3, 4, 5]`

--

How much work is required if the list is reversed? Already sorted? Partially Sorted?

---

### Insertion Sort: Implementation

.pull-left[

#### A helpful animation

<img src="images/sort_insertion.gif" width="350" height="200">

#### Pseudocode

```
For each i from 0 to n:
  For each j from i to 0:
    If the element at j-1 is greater than the element at j:
      Swap the elements at j-1 and j
    Otherwise:
      Break
```

]

.pull-right[

#### Details

- The left-hand side of the array is considered sorted, the algorithm then *inserts* each new element into it's proper place
- Stable: The order of elements of equal value is preserved
- Adaptive: Efficient for datasets that are already sorted or partially sorted
- Efficient on small datasets
- In-place: Requires a constant amount of extra memory

]

---

### Insertion Sort: Analysis

- Worst Case: $O(n^2)$
- Average Case: $O(n^2)$
- Best Case: $O(n)$
- Partially Sorted Arrays: $O(kn)$ where $k$ is some constant limit on the number of inversions.

Consider the act of inserting an element into a sorted sublist, if the element is the smallest element in the list, it must be swapped all the way to the beginning of the list. The worst case for insertion sort is when the list is in reversed order, forcing the algorithm to make $1 + 2 + 3 + ... + n - 1$ swaps.

We can convert this statement into a recurrence, which can then be used to attain the closed-form solution:

$$\sum_{i = 1}^{n - 1} i = \frac{n(n - 1)}{2} = O(n^2)$$

---
name: mergesort
class: middle

## MergeSort

---

### MergeSort: Introduction

What if we could sort an array recursively and efficiently in any case?

- What should our base case be?
- How can we get there?
- How do we put together the pieces?

--

As the name may suggest, we are going to put the pieces back together by *merging* them, but wait - what pieces?

--

MergeSort works by breaking down an array into singletons, arrays of length 1 or 0, then recombines them via merging.

--

Starting with the array below, we split down to singletons.

`[5, 2, 4, 3, 1]`

--

`[[5, 2, 4], [3, 1]]`

--

`[[[5, 2], [4]], [[3], [1]]]`

--

`[[[[5], [2]], [4]], [[3], [1]]]`

---

### MergeSort: Introduction (cont)

Starting with our singletons from the last slide:

`[[[[5], [2]], [4]], [[3], [1]]]`

We now merge these pieces back together.

--

`[[[2, 5], [4]], [1, 3]]`

--

`[[2, 4, 5], [1, 3]]`

--

`[1, 2, 3, 4, 5]` And we are done!

--

While you are implementing this algorithm strongly consider what it's runtime should be.

---

### MergeSort: Implementation

.pull-left[

#### A helpful animation

<img src="images/sort_merge.gif" width="300" height="200">

#### Pseudocode for MergeSort

```
Let Array be an array of n elements.
if the number of elements is greater than 1:
    call mergesort on the first half
    call mergesort on the second half
    merge the array
```

]

.pull-right[

#### Pseudocode for Merge

```
Let Array be an array of n elements.
Temp = Copy(Array)
Let j = 0, k = MiddleIndex(Array)
For each i from 0 to n:
  If j >= MiddleIndex(Array):
    Array[i] = Temp[k], k = k + 1
  Else if (k >= n):
    Array[i] = Temp[j], j = j + 1
  Else if Temp[j] < Temp[k]:
    Array[i] = Temp[j], j = j + 1
  Else:
    Array[i] = Temp[k], k = k + 1
```

#### Details

- Recursive: Calls itself to solve the problem
- Stable: Relative orderings of elements of equal value are preserved.
- Not Adaptive: Takes the same amount of time in all conditions

]

---

### MergeSort: Analysis

MergeSort calls itself on two halves of the original list, then combines them.

Roughly speaking, we can provide this recursive definition:

`MergeSort(n) = Merge(MergeSort(n / 2), MergeSort(n / 2))`

--

We can translate this into the recurrence:

$$ T(n) = 2T(n / 2) + n = O(n \log n) $$

To solve this recurrence you can unroll the equation, use the [tree method](https://www.educative.io/collection/page/10370001/760001/1280004), or the master method.

---
name: quicksort
class: middle

## QuickSort

---

### QuickSort: Introduction

What if instead of simply dividing the array into two halves, we split it into lower and upper portions, then sorted those halves?

We'll walk through our normal example with this scheme:

`[5, 2, 4, 3, 1]` Starting with our array, we pick a *pivot*, which is normally the first, last, middle, or median of 3 elements.
For this example, we will pick the first element.

--

`[2, 4, 3, 1], [5], []` After pivoting on 5.

--

`[1], [2], [4, 3], [5], []` Pivoting on 2.

--

`[1], [2], [3], [4], [], [5], []` Pivoting on 4.

--

`[1, 2, 3, 4, 5]` Combing the results.

--

Of course, this is actually done in-place, with recursive calls on each sublist.

---

### QuickSort Implementation

.pull-left[

#### A helpful animation

<img src="images/sort_quick.gif" width="400" height="200">

#### Pseudocode for Partition

```
set i to lo + 1 and j to hi
while true:
    increment i until array at i is greater than array at lo
    decrement j until array at j is less than array at lo
    break if j <= i
    swap the elements at i and at j
swap the elements at lo and at j
return j
```

]

.pull-right[

#### Pseudocode for QuickSort

```
if lo is less than hi:
    p = call partition on the array
    call quicksort with lo and p - 1
    call quicksort with p + 1 and hi
```

#### Details

- Think of some details as you work! We'll do this section together

]

---

### QuickSort: Analysis

#### Worst Case

The partition is always the largest or smallest, removing only a single element from each call.

$$T(n) = n + T(n - 1) = \sum_{i=1}^n i = O(n^2)$$

#### Best Case

We can look at the best case in two different ways, as a recurrence relation

$$
T(n) = n + 2T \bigg( \frac{n}{2} \bigg)
= k \cdot n  + 2^k T \bigg(\frac{n}{2^k} \bigg)
= n \cdot \log n + n
= O(n \cdot \log n)
$$

Or, as a call tree, where each level of the tree examines all $n$ elements, and the max height of this tree is $\log n$, since we dividing $n$ by $2$ at each call, which equates to $O(n \cdot \log n)$

---
name: resources

## Resources

Visualizations

- [sorting.at](http://sorting.at/)
- [Comparison Sorts TOPTAL](https://www.toptal.com/developers/sorting-algorithms)
- [Sound of Sorting](https://www.youtube.com/watch?v=kPRA0W1kECg)
- [Comparison Sorts USFCA](https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html)
- [Median of Medians](http://eshrews.com/select)


</textarea>
    <script src="https://remarkjs.com/downloads/remark-latest.min.js"></script>

    <script>
        var slideshow = remark.create();
    </script>
</body>

</html>