Sorting Rubyists

Keynote Presentation: Sorting Rubyists.key

Slide 1

Title: “Sorting” <=> “Rubyists”

Presenter Notes:

This talk is not for people who studied computer science. If you know what Big O Notation is, you can leave now. I have nothing to give to you.

Slide 2

Title: ..

Presenter Notes:

This is for you folks who call #sort and have no idea what demon is moving your strings around in an array, but you get that array back sorted and that’s pretty cool.

Slide 3

Title: Algorithms

Presenter Notes:

To understand what Ruby or Postgresql do when you sort an array, let’s talk about algorithms.

Slide 4

Title: A series of step-by-step instructions

Presenter Notes:

It’s a scary word, but all it means is a series of step-by-step instructions to complete a task.

Slide 5

Title: t

Presenter Notes:

A recipe for chocolate chip cookies is an algorithm. I didn’t have to understand the chemistry and gastronomy of the instructions. When I realized this was a good example, I just found a recipe for chocolate chip cookies and made a batch immediately before I kept going. I followed directions and ended up with delicious cookies that I ate all of.

Slide 6

Title:

Presenter Notes:

Slide 7

Title: :14

Presenter Notes:

Slide 8

Title: Big O

Presenter Notes:

Before we get too far, I want to talk about Big O. Big O can be a scary concept when you see it written out. I usually assume it’s something for math people and I make websites, so that’s probably not me. But when it comes down to it, Big O isn’t really that scary.

Slide 9

Title:

Presenter Notes:

Big O is how we answer “How fast is an algorithm” and use that answer to compare algorithms to each other.

It is based on the assumption that basic operations involved in an algorithm will take the same amount of time between algorithms that perform the same task.

This allows us to compare using # of operations as a function of the inputs instead of time to complete.

Slide 10

Title:

Presenter Notes:

Let’s look at a couple of algorithms for cutting out squares from this paper.

Slide 11

Title:

Presenter Notes:

That took 15 operations to cut out 16 squares, so it’s a linear time complexity algorithm, represented by this notation. It’s read “order of n” and it means linear time. If I wanted to cut out 32 squares, it would take 31 cuts. Even though the number of operations isn’t the number of squares, the big O is n because the growth is linear.

You’re probably wondering what the O function is. Here’s a secret: it means nothing. We call it big o notation because we put a big o in front of it, but that’s it.

Slide 12

Title:

Presenter Notes:

Ok, let’s look at another algorithm.

Slide 13

Title:

Presenter Notes:

This new algorithm takes only 4 operations to cut out 16 squares, so it’s a O(log n) algorithm. If I wanted to double that to cut out 32 squares, it would take 5 cuts. The difference between logarithmic and linear growth is pretty impressive.

Slide 14

Title:

Presenter Notes:

This is a chart of some of the different common Big O descriptions. On the x axis we have n as it grows, and on the y axis we have time complexity. O(n) and O(log n) are down at the bottom, now orange and yellow. They’re much smaller because I changed the scale from 1:1 on the x and y axis to 10:1. I needed to do that to show the shape of some of these really slow big o representations: n!, 2^n, and n^2. If you draw an imaginary line diagonally across this chart, you basically want to avoid any of the big o values above it and shoot for the big o values below it.

Slide 15

Title:

Presenter Notes:

If we switch back to our 1:1 ratio, you can see that even these more performant options have a lot of variation. That’s why O(n) was so much faster than O(log n).

Slide 16

Title: When do you update a user record?

Presenter Notes:

Slide 17

Title: If you understood everything

Presenter Notes:

Slide 18

Title: How do you debug an app?

Presenter Notes:

Slide 19

Title: What happens when you buy something?

Presenter Notes:

Slide 20

Title: Big Ω

Presenter Notes:

We’re also going to talk about Big Omega. This one’s easy. It’s the same as Big O, but instead of talking about worst case performance, it means best case performance. That’s why it has these tails here, since it’s the lower bound for how fast an algorithm is.

Slide 21

Title: Bubble Sort

Presenter Notes:

The bubble sort algorithm is nice and simple, so it’s a great place to jump into explaining sorting algorithms.

The algorithm is: consider each pair of elements. If they’re in the wrong order, swap them. Then move one over and repeat. Keep doing that until you hit the end of the set, then start over. Remember where you left the biggest thing you found, and don’t go past it. If you go through an entire iteration and no changes are made, you’re sorted.

Slide 22

Title: 65+95+85+15+25+45+75+4+55+35+100

Presenter Notes:

To see how this algorithm works, we’re going to use it to sort 11 objects.

Slide 23

Title: 65+95+85+15+25+45+75+4+55+35+100

Presenter Notes:

Remember, we consider these objects in pairs and swap them if they’re in the wrong order. We start by looking at this first value and the one right after it. They’re in the right order, so we move on. We’ll keep going until we get to the top.

Slide 24

Title: 65+95+85+15+25+45+75+4+55+35+100

Presenter Notes:

The next set is in the wrong order…

Slide 25

Title: 65+85+95+15+25+45+75+4+55+35+100

Presenter Notes:

so we swap them over.

Slide 26

Title: 65+85+95+15+25+45+75+4+55+35+100

Presenter Notes:

Consider this pair. They’re in the wrong order again

Slide 27

Title: 65+85+15+95+25+45+75+4+55+35+100

Presenter Notes:

So we make another swap

Slide 28

Title: 65+85+15+95+25+45+75+4+55+35+100

Presenter Notes:

Slide 29

Title: 65+85+15+25+95+45+75+4+55+35+100

Presenter Notes:

Slide 30

Title: 65+85+15+25+95+45+75+4+55+35+100

Presenter Notes:

Slide 31

Title: 65+85+15+25+45+95+75+4+55+35+100

Presenter Notes:

Slide 32

Title: 65+85+15+25+45+95+75+4+55+35+100

Presenter Notes:

Slide 33

Title: 65+85+15+25+45+75+95+4+55+35+100

Presenter Notes:

Slide 34

Title: 65+85+15+25+45+75+95+4+55+35+100

Presenter Notes:

Slide 35

Title: 65+85+15+25+45+75+4+95+55+35+100

Presenter Notes:

Slide 36

Title: 65+85+15+25+45+75+4+95+55+35+100

Presenter Notes:

Slide 37

Title: 65+85+15+25+45+75+4+55+95+35+100

Presenter Notes:

Slide 38

Title: 65+85+15+25+45+75+4+55+95+35+100

Presenter Notes:

Slide 39

Title: 65+85+15+25+45+75+4+55+35+95+100

Presenter Notes:

Slide 40

Title: 65+85+15+25+45+75+4+55+35+95+100

Presenter Notes:

Slide 41

Title: 65+85+15+25+45+75+4+55+35+95+100

Presenter Notes:

That’s our first iteration. Now the bubble sort algorithm says to go back to the beginning and repeat the process over and over again until the objects are in order.

Slide 42

Title: 65+85+15+25+45+75+4+55+35+95+100

Presenter Notes:

Slide 43

Title: 65+85+15+25+45+75+4+55+35+95+100

Presenter Notes:

Slide 44

Title: 65+15+85+25+45+75+4+55+35+95+100

Presenter Notes:

Slide 45

Title: 65+15+85+25+45+75+4+55+35+95+100

Presenter Notes:

Slide 46

Title: 65+15+25+85+45+75+4+55+35+95+100

Presenter Notes:

Slide 47

Title: 65+15+25+85+45+75+4+55+35+95+100

Presenter Notes:

Slide 48

Title: 65+15+25+45+85+75+4+55+35+95+100

Presenter Notes:

Slide 49

Title: 65+15+25+45+85+75+4+55+35+95+100

Presenter Notes:

Slide 50

Title: 65+15+25+45+75+85+4+55+35+95+100

Presenter Notes:

Slide 51

Title: 65+15+25+45+75+85+4+55+35+95+100

Presenter Notes:

Slide 52

Title: 65+15+25+45+75+4+85+55+35+95+100

Presenter Notes:

Slide 53

Title: 65+15+25+45+75+4+85+55+35+95+100

Presenter Notes:

Slide 54

Title: 65+15+25+45+75+4+55+85+35+95+100

Presenter Notes:

Slide 55

Title: 65+15+25+45+75+4+55+85+35+95+100

Presenter Notes:

Slide 56

Title: 65+15+25+45+75+4+55+35+85+95+100

Presenter Notes:

Slide 57

Title: 65+15+25+45+75+4+55+35+85+95+100

Presenter Notes:

We can safely skip the last element, because we know we’ve gone through the whole iteration once, so we know it’s in the right place.

Slide 58

Title: 65+15+25+45+75+4+55+35+85+95+100

Presenter Notes:

We’ll start back over at the beginning and repeat until the objects are in order.

Slide 59

Title: 65+15+25+45+75+4+55+35+85+95+100

Presenter Notes:

Slide 60

Title: 15+65+25+45+75+4+55+35+85+95+100

Presenter Notes:

Slide 61

Title: 15+65+25+45+75+4+55+35+85+95+100

Presenter Notes:

Slide 62

Title: 15+25+65+45+75+4+55+35+85+95+100

Presenter Notes:

Slide 63

Title: 15+25+65+45+75+4+55+35+85+95+100

Presenter Notes:

Slide 64

Title: 15+25+45+65+75+4+55+35+85+95+100

Presenter Notes:

Slide 65

Title: 15+25+45+65+75+4+55+35+85+95+100

Presenter Notes:

Slide 66

Title: 15+25+45+65+75+4+55+35+85+95+100

Presenter Notes:

Slide 67

Title: 15+25+45+65+4+75+55+35+85+95+100

Presenter Notes:

Slide 68

Title: 15+25+45+65+4+75+55+35+85+95+100

Presenter Notes:

Slide 69

Title: 15+25+45+65+4+55+75+35+85+95+100

Presenter Notes:

Slide 70

Title: 15+25+45+65+4+55+75+35+85+95+100

Presenter Notes:

Slide 71

Title: 15+25+45+65+4+55+35+75+85+95+100

Presenter Notes:

Slide 72

Title: 15+25+45+65+4+55+35+75+85+95+100

Presenter Notes:

Slide 73

Title: 15+25+45+65+4+55+35+75+85+95+100

Presenter Notes:

Slide 74

Title: 15+25+45+65+4+55+35+75+85+95+100

Presenter Notes:

Slide 75

Title: 15+25+45+65+4+55+35+75+85+95+100

Presenter Notes:

Slide 76

Title: 15+25+45+65+4+55+35+75+85+95+100

Presenter Notes:

Slide 77

Title: 15+25+45+65+4+55+35+75+85+95+100

Presenter Notes:

Slide 78

Title: 15+25+45+4+65+55+35+75+85+95+100

Presenter Notes:

Slide 79

Title: 15+25+45+4+65+55+35+75+85+95+100

Presenter Notes:

Slide 80

Title: 15+25+45+4+55+65+35+75+85+95+100

Presenter Notes:

Slide 81

Title: 15+25+45+4+55+65+35+75+85+95+100

Presenter Notes:

Slide 82

Title: 15+25+45+4+55+35+65+75+85+95+100

Presenter Notes:

Slide 83

Title: 15+25+45+4+55+35+65+75+85+95+100

Presenter Notes:

Slide 84

Title: 15+25+45+4+55+35+65+75+85+95+100

Presenter Notes:

Slide 85

Title: 15+25+45+4+55+35+65+75+85+95+100

Presenter Notes:

Slide 86

Title: 15+25+45+4+55+35+65+75+85+95+100

Presenter Notes:

Slide 87

Title: 15+25+45+4+55+35+65+75+85+95+100

Presenter Notes:

Slide 88

Title: 15+25+4+45+55+35+65+75+85+95+100

Presenter Notes:

Slide 89

Title: 15+25+4+45+55+35+65+75+85+95+100

Presenter Notes:

Slide 90

Title: 15+25+4+45+55+35+65+75+85+95+100

Presenter Notes:

Slide 91

Title: 15+25+4+45+35+55+65+75+85+95+100

Presenter Notes:

Slide 92

Title: 15+25+4+45+35+55+65+75+85+95+100

Presenter Notes:

Slide 93

Title: 15+25+4+45+35+55+65+75+85+95+100

Presenter Notes:

Slide 94

Title: 15+25+4+45+35+55+65+75+85+95+100

Presenter Notes:

Slide 95

Title: 15+25+4+45+35+55+65+75+85+95+100

Presenter Notes:

Slide 96

Title: 15+4+25+45+35+55+65+75+85+95+100

Presenter Notes:

Slide 97

Title: 15+4+25+45+35+55+65+75+85+95+100

Presenter Notes:

Slide 98

Title: 15+4+25+45+35+55+65+75+85+95+100

Presenter Notes:

Slide 99

Title: 15+4+25+35+45+55+65+75+85+95+100

Presenter Notes:

Slide 100

Title: 15+4+25+35+45+55+65+75+85+95+100

Presenter Notes:

Slide 101

Title: 15+4+25+35+45+55+65+75+85+95+100

Presenter Notes:

Slide 102

Title: 15+4+25+35+45+55+65+75+85+95+100

Presenter Notes:

Slide 103

Title: 4+15+25+35+45+55+65+75+85+95+100

Presenter Notes:

You and I know now by looking that the set is ordered, but the algorithm has to complete by checking each pair until it doesn’t make any swaps.

Slide 104

Title: 4+15+25+35+45+55+65+75+85+95+100

Presenter Notes:

You and I know now by looking that the set is ordered, but the algorithm has to complete by checking each pair until it doesn’t make any swaps.

Slide 105

Title: 4+15+25+35+45+55+65+75+85+95+100

Presenter Notes:

You and I know now by looking that the set is ordered, but the algorithm has to complete by checking each pair until it doesn’t make any swaps.

Slide 106

Title: 4+15+25+35+45+55+65+75+85+95+100

Presenter Notes:

You and I know now by looking that the set is ordered, but the algorithm has to complete by checking each pair until it doesn’t make any swaps.

Slide 107

Title: 4+15+25+35+45+55+65+75+85+95+100

Presenter Notes:

Now that it’s gone through without making changes, the algorithm is complete and the bars are in ascending order.

Slide 108

Title:

Presenter Notes:

Bubble sort works on O(n^2) time.

Slide 109

Title:

Presenter Notes:

For the purposes of sorting algorithms, “n” is the length of the set.

Slide 110

Title:

Presenter Notes:

Bubble sort in n^2 time because it compares every element to every other element in the worst case. Even though we have some optimizations so that you’re not comparing every single element, when we’re stating an algorithm’s complexity we still say n^2.

For bubble sort, O(n^2) is also the average case complexity (such as on a randomized array).

Slide 111

Title:

Presenter Notes:

It has Big Omega (or lower bound / best case) time of n, which means that for its best case, which for Bubble Sort is a sorted set, it takes only “n” comparison operations to confirm that we are sorted.

Slide 112

Title:

Presenter Notes:

As we saw before, n^2 isn’t very good. It’s that Rad line there, and in this case bigger is worse, because it means number of operations and usually also time taken. What we want is to be in one of these four smaller lines, O(n log n), O(n), or ideally O(log n) or O(1). O(1) only works in a perfect world where your sorting algorithm is to return the sorted set you were asked to sort.

Slide 113

Title:

Presenter Notes:

It’s useful to see a visualization of how these algorithms work on different types of inputs. Toptal has this great set of visualizations that show bubble sort operating over different types of inputs. These can help you build an intuition about how bubble sort will work on different types of inputs. The red arrow indicates our “subject” which we used the sorting hat for, dark bars are sorted, and light bars are yet to be sorted. We have random, nearly sorted, reversed, and few unique sets of input data.

Slide 114

Title: Insertion Sort

Presenter Notes:

Insertion sort is another simple algorithm. It’s very efficient at sorting small sets. Insertion sort is so called because it inserts the subject element into the subset of previously sorted elements in the correct order by comparing until it is greater than one of the previous elements and then inserting after that.

Slide 115

Title: 75+95+100+25+35+15+5+55+85+45+65

Presenter Notes:

So the algorithm: For each element, consider all elements to its left. Continue until you reach one that is smaller than the element or you run out of elements to check. If you found anything smaller, move the element just after that place and shift the larger elements to the right. Let’s take a look.

Slide 116

Title: 75+95+100+25+35+15+5+55+85+45+65

Presenter Notes:

We start with the first and compare it to everything to its left. This step is pretty easy, there’s nothing bigger to the left (since there’s nothing to the left), so we’re done.

Slide 117

Title: 75+95+100+25+35+15+5+55+85+45+65

Presenter Notes:

No we consider the next element.

Slide 118

Title: 75+95+100+25+35+15+5+55+85+45+65

Presenter Notes:

The red element we’re comparing is not bigger than the green subject. We don’t want to move anything here, as this subset is already sorted.

Slide 119

Title: 75+95+100+25+35+15+5+55+85+45+65

Presenter Notes:

On to the next green subject.

Slide 120

Title: 75+95+100+25+35+15+5+55+85+45+65

Presenter Notes:

We’ll compare each of these

Slide 121

Title: 75+95+100+25+35+15+5+55+85+45+65

Presenter Notes:

and see that they’re both smaller.

Slide 122

Title: 75+95+100+25+35+15+5+55+85+45+65

Presenter Notes:

Next!

Slide 123

Title: 75+95+100+25+35+15+5+55+85+45+65

Presenter Notes:

This one’s bigger

Slide 124

Title: 75+95+100+25+35+15+5+55+85+45+65

Presenter Notes:

But so is this

Slide 125

Title: 75+95+100+25+35+15+5+55+85+45+65

Presenter Notes:

and this

Slide 126

Title: 25+75+95+100+35+15+5+55+85+45+65

Presenter Notes:

So we shift the green subject before all of them. Now the first four elements are in order.

We’ll repeat this until the whole set is sorted. Let’s speed through that.

Slide 127

Title: 25+75+95+100+35+15+5+55+85+45+65

Presenter Notes:

Slide 128

Title: 25+75+95+100+35+15+5+55+85+45+65

Presenter Notes:

Slide 129

Title: 25+75+95+100+35+15+5+55+85+45+65

Presenter Notes:

Slide 130

Title: 25+75+95+100+35+15+5+55+85+45+65

Presenter Notes:

Slide 131

Title: 25+75+95+100+35+15+5+55+85+45+65

Presenter Notes:

Slide 132

Title: 25+35+75+95+100+15+5+55+85+45+65

Presenter Notes:

Slide 133

Title: 25+35+75+95+100+15+5+55+85+45+65

Presenter Notes:

Slide 134

Title: 25+35+75+95+100+15+5+55+85+45+65

Presenter Notes:

Slide 135

Title: 25+35+75+95+100+15+5+55+85+45+65

Presenter Notes:

Slide 136

Title: 25+35+75+95+100+15+5+55+85+45+65

Presenter Notes:

Slide 137

Title: 25+35+75+95+100+15+5+55+85+45+65

Presenter Notes:

Slide 138

Title: 25+35+75+95+100+15+5+55+85+45+65

Presenter Notes:

Slide 139

Title: 15+25+35+75+95+100+5+55+85+45+65

Presenter Notes:

Slide 140

Title: 15+25+35+75+95+100+5+55+85+45+65

Presenter Notes:

Slide 141

Title: 15+25+35+75+95+100+5+55+85+45+65

Presenter Notes:

Slide 142

Title: 15+25+35+75+95+100+5+55+85+45+65

Presenter Notes:

Slide 143

Title: 15+25+35+75+95+100+5+55+85+45+65

Presenter Notes:

Slide 144

Title: 15+25+35+75+95+100+5+55+85+45+65

Presenter Notes:

Slide 145

Title: 15+25+35+75+95+100+5+55+85+45+65

Presenter Notes:

Slide 146

Title: 15+25+35+75+95+100+5+55+85+45+65

Presenter Notes:

Slide 147

Title: 5+15+25+35+75+95+100+55+85+45+65

Presenter Notes:

Slide 148

Title: 5+15+25+35+75+95+100+55+85+45+65

Presenter Notes:

Slide 149

Title: 5+15+25+35+75+95+100+55+85+45+65

Presenter Notes:

Slide 150

Title: 5+15+25+35+75+95+100+55+85+45+65

Presenter Notes:

Slide 151

Title: 5+15+25+35+75+95+100+55+85+45+65

Presenter Notes:

Slide 152

Title: 5+15+25+35+75+95+100+55+85+45+65

Presenter Notes:

Slide 153

Title: 5+15+25+35+55+75+95+100+85+45+65

Presenter Notes:

Slide 154

Title: 5+15+25+35+55+75+95+100+85+45+65

Presenter Notes:

Slide 155

Title: 5+15+25+35+55+75+95+100+85+45+65

Presenter Notes:

Slide 156

Title: 5+15+25+35+55+75+95+100+85+45+65

Presenter Notes:

Slide 157

Title: 5+15+25+35+55+75+95+100+85+45+65

Presenter Notes:

Slide 158

Title: 5+15+25+35+55+75+85+95+100+45+65

Presenter Notes:

Slide 159

Title: 5+15+25+35+55+75+85+95+100+45+65

Presenter Notes:

Slide 160

Title: 5+15+25+35+55+75+85+95+100+45+65

Presenter Notes:

Slide 161

Title: 5+15+25+35+55+75+85+95+100+45+65

Presenter Notes:

Slide 162

Title: 5+15+25+35+55+75+85+95+100+45+65

Presenter Notes:

Slide 163

Title: 5+15+25+35+55+75+85+95+100+45+65

Presenter Notes:

Slide 164

Title: 5+15+25+35+55+75+85+95+100+45+65

Presenter Notes:

Slide 165

Title: 5+15+25+35+55+75+85+95+100+45+65

Presenter Notes:

Slide 166

Title: 5+15+25+35+45+55+75+85+95+100+65

Presenter Notes:

Slide 167

Title: 5+15+25+35+45+55+75+85+95+100+65

Presenter Notes:

Slide 168

Title: 5+15+25+35+45+55+75+85+95+100+65

Presenter Notes:

Slide 169

Title: 5+15+25+35+45+55+75+85+95+100+65

Presenter Notes:

Slide 170

Title: 5+15+25+35+45+55+75+85+95+100+65

Presenter Notes:

Slide 171

Title: 5+15+25+35+45+55+75+85+95+100+65

Presenter Notes:

Slide 172

Title: 5+15+25+35+45+55+75+85+95+100+65

Presenter Notes:

Slide 173

Title: 5+15+25+35+45+55+65+75+85+95+100

Presenter Notes:

Slide 174

Title: 5+15+25+35+45+55+65+75+85+95+100

Presenter Notes:

And now we have a sorted set. Insertion sort is a fun one because it’s one of the simplest sorting algorithms to write.

Slide 175

Title:

Presenter Notes:

Like bubble sort, Insertion sort operates in quadratic time both for Big O (worst case) and in the average case.

Slide 176

Title:

Presenter Notes:

Its Big Omega, or best case performance, is also the same as Bubble sort, linear time. Because of the inherent “lossiness” of Big O notation, this ignores that insertion sort tends to operate more efficiently than bubble sort, but it’s definitely not a fantastic way to sort a large set.

Slide 177

Title:

Presenter Notes:

Insertion sort does work very well on nearly sorted arrays. It’s already finished. Because of this, insertion sort is sometimes used as a “finishing step” for quicksort, which we’ll look at next. It shares the benefit bubble sort has of returning an already sorted set in linear time. You can see that it’s working much better on the reversed set and is generally faster, despite having the same complexity representations, than bubble sort.

Slide 178

Title: Quicksort

Presenter Notes:

Quicksort is often considered the “state of the art” in sorting algorithms. This is because the average case performance is very low for a comparison sorting algorithms. Quicksort’s algorithm is a bit different than bubble or insertion sort. Rather than moving the element we’re comparing against, which we call the pivot in quicksort, we move everything else around it to the left if it’s less than the pivot and the right if it’s greater. Then we do the same thing for each set of things moved and continue until everything’s sorted.

Slide 179

Title: 95+5+15+45+25+100+75+85+65+55+35

Presenter Notes:

Here again we have our 11 bars.

Slide 180

Title: 95+5+15+45+25+100+75+85+65+55+35

Presenter Notes:

For the algorithm to work, it doesn’t matter what you pick for your pivot. In practice it makes sense to pick the midway point because it operates better for a lot of cases, especially for sorted data as it means no moves occur.

We’ll start with this bar, and move all elements to the left or right of it based on whether they’re taller or shorter.

Slide 181

Title: 95+5+15+45+25+75+85+65+55+35+100

Presenter Notes:

Since this is the tallest bar, we move everything else over to its left in the same order.

Slide 182

Title: 95+5+15+45+25+75+85+65+55+35+100

Presenter Notes:

Now, we quick sort everything to the left, which you see here, and the right, which is an empty set so it doesn’t get sorted. We pick a new pivot and move everything in this subset according to the same rules as before.

Slide 183

Title: 5+15+45+25+65+55+35+75+95+85+100

Presenter Notes:

This time, there’s both a left and right set. The grey bar indicates that for now we’re not considering that bar, either because it was a pivot (meaning it’s already in the correct space), or because it’s not in the subset being quick sorted right now.

Slide 184

Title: 5+15+45+25+65+55+35+75+95+85+100

Presenter Notes:

We’ll again quicksort the bars to the left of the old pivot by choosing the midpoint as our new pivot

Slide 185

Title: 5+15+25+45+65+55+35+75+95+85+100

Presenter Notes:

And moving everything to be either the left or right based on their height values.

Slide 186

Title: 5+15+25+45+65+55+35+75+95+85+100

Presenter Notes:

Slide 187

Title: 5+15+25+45+65+55+35+75+95+85+100

Presenter Notes:

Slide 188

Title: 5+15+25+45+65+55+35+75+95+85+100

Presenter Notes:

Slide 189

Title: 5+15+25+45+35+55+65+75+95+85+100

Presenter Notes:

Slide 190

Title: 5+15+25+45+35+55+65+75+95+85+100

Presenter Notes:

Slide 191

Title: 5+15+25+35+45+55+65+75+95+85+100

Presenter Notes:

Slide 192

Title: 5+15+25+35+45+55+65+75+95+85+100

Presenter Notes:

Slide 193

Title: 5+15+25+35+45+55+65+75+85+95+100

Presenter Notes:

Slide 194

Title: 5+15+25+35+45+55+65+75+85+95+100

Presenter Notes:

Slide 195

Title: 5+15+25+35+45+55+65+75+85+95+100

Presenter Notes:

Slide 196

Title: 5+15+25+35+45+55+65+75+85+95+100

Presenter Notes:

Slide 197

Title: 5+15+25+35+45+55+65+75+85+95+100

Presenter Notes:

Slide 198

Title: 5+15+25+35+45+55+65+75+85+95+100

Presenter Notes:

Slide 199

Title:

Presenter Notes:

Quicksort’s Big O is quadratic just like insertion or bubble sort. In the case of quicksort, it’s pretty rare to get this performance. To be n^2 operations, you’d need to always pick a pivot that was either the largest or smallest element, such that the remaining subsets to be quick sorted are of size 0 and n-1.

Slide 200

Title: 95+5+15+45+25+100+75+85+65+55+35

Presenter Notes:

We saw this in the very first operation in when the pivot we chose was the largest

Slide 201

Title: 95+5+15+45+25+75+85+65+55+35+100

Presenter Notes:

And the next subset was the whole set except the first pivot.

Slide 202

Title:

Presenter Notes:

The magic of quick sort is that in the average case, its performance is linearithmic (the fancy word for n log n time). Average case here is not just intuition. There are several mathematical proofs that show this performance, but they’re over my head and out of scope for this talk.

Slide 203

Title:

Presenter Notes:

Linearithmic (or n log n) performance is also the best case for quicksort. So while quick sort isn’t always the fastest algorithm and can be just as slow as insertion or bubble sort given specific inputs, its average case is its best case, and the best case is pretty quick compared do others in this type of sorting algorithm. For general purposes (meaning integers, strings, whatever), this is the cream of the crop.

Slide 204

Title:

Presenter Notes:

That said, it does have its weaknesses. While you can see that it does great with the random and reversed sets, it has trouble with the nearly sorted and few unique sets.

Slide 205

Title:

Presenter Notes:

Here you can see the same visualizations we’ve looked at for each type of algorithm, all compared together. As the different algorithms work and finish, you can begin to see that some of them are better suited for specific tasks. The random set in the first column is a fair approximation of the average case, and you can see that quick sort works quickly there. It also makes short work of the reversed set, which trips up a lot of sorting algorithms. Insertion sort works very quickly for the nearly sorted set, and even bubble sort outperforms quick sort in this case. None of these algorithms work well with the few unique set. On the other hand, it’s difficult to beat insertion sort or bubble sort for ease of writing the code. Perhaps most importantly however, quick sort provides very good average case results. This is why it is used in Ruby’s Array#sort implementation.

Slide 206

Title:

Presenter Notes:

I’d like to thank my employer, Heroku, for supporting me in coming to MagmaConf this year. You may have heard about our new Automated Certificate Management offering, which gives you free LetsEncrypt certificates for paid dynos at any tier. This video shows how easy it is, let’s say about O(1) complexity. You should check it out if you haven’t yet.

Slide 207

Title:

Presenter Notes:

Slide 208

Title: Bibliography

Presenter Notes:

Slide 209

Title: Images

Presenter Notes: