Sorting Finale

Quicksort: Review

8

5

7

3

4

11

6

-1

  • In each step, Quicksort picks a value called the pivot and divides the array into two parts: values larger than the pivot and values smaller

  • This continues until arrays of size 1 are reached, at which point the entire array is sorted

Quicksort: Review

8

5

7

3

4

11

6

-1

  • In each step, Quicksort picks a value called the pivot and divides the array into two parts: values larger than the pivot and values smaller

  • This continues until arrays of size 1 are reached, at which point the entire array is sorted

Quicksort: Review

5

7

3

4

6

-1

8

11

  • In each step, Quicksort picks a value called the pivot and divides the array into two parts: values larger than the pivot and values smaller

  • This continues until arrays of size 1 are reached, at which point the entire array is sorted

Quicksort: Review

5

7

3

4

6

-1

8

11

5

7

3

4

6

-1

8

11

  • In each step, Quicksort picks a value called the pivot and divides the array into two parts: values larger than the pivot and values smaller

  • This continues until arrays of size 1 are reached, at which point the entire array is sorted

Quicksort: Review

5

7

3

4

6

-1

8

11

3

4

-1

5

7

6

8

11

  • In each step, Quicksort picks a value called the pivot and divides the array into two parts: values larger than the pivot and values smaller

  • This continues until arrays of size 1 are reached, at which point the entire array is sorted

Quicksort: Review

5

7

3

4

6

-1

8

11

3

4

-1

5

7

6

8

11

3

4

-1

5

7

6

8

11

  • In each step, Quicksort picks a value called the pivot and divides the array into two parts: values larger than the pivot and values smaller

  • This continues until arrays of size 1 are reached, at which point the entire array is sorted

Quicksort: Review

5

7

3

4

6

-1

8

11

3

4

-1

5

7

6

8

11

-1

3

4

5

6

7

8

11

  • In each step, Quicksort picks a value called the pivot and divides the array into two parts: values larger than the pivot and values smaller

  • This continues until arrays of size 1 are reached, at which point the entire array is sorted

Quicksort: Review

5

7

3

4

6

-1

8

11

3

4

-1

5

7

6

8

11

-1

3

4

5

6

7

8

11

-1

3

4

5

6

7

8

11

  • In each step, Quicksort picks a value called the pivot and divides the array into two parts: values larger than the pivot and values smaller

  • This continues until arrays of size 1 are reached, at which point the entire array is sorted

Quicksort: Review

5

7

3

4

6

-1

8

11

3

4

-1

5

7

6

8

11

-1

3

4

5

6

7

8

11

-1

3

4

5

6

7

8

11

-1

3

4

5

6

7

8

11

  • In each step, Quicksort picks a value called the pivot and divides the array into two parts: values larger than the pivot and values smaller

  • This continues until arrays of size 1 are reached, at which point the entire array is sorted

Quicksort: Partition

6

5

7

3

4

11

8

-1

  • We want to divide the array into smaller and larger parts and put the pivot in between them

  • If we see a smaller value, increase the size of the smaller part and put the value in the smaller part

  • When we’re done, we’ll know where to put the pivot

Quicksort: Partition

6

5

7

3

4

11

8

-1

 

↑

 

 

 

 

 

 

  • We want to divide the array into smaller and larger parts and put the pivot in between them

  • If we see a smaller value, increase the size of the smaller part and put the value in the smaller part

  • When we’re done, we’ll know where to put the pivot

Quicksort: Partition

6

5

7

3

4

11

8

-1

 

 

↑

 

 

 

 

 

  • We want to divide the array into smaller and larger parts and put the pivot in between them

  • If we see a smaller value, increase the size of the smaller part and put the value in the smaller part

  • When we’re done, we’ll know where to put the pivot

Quicksort: Partition

6

5

7

3

4

11

8

-1

 

 

↑

 

 

 

 

 

  • We want to divide the array into smaller and larger parts and put the pivot in between them

  • If we see a smaller value, increase the size of the smaller part and put the value in the smaller part

  • When we’re done, we’ll know where to put the pivot

Quicksort: Partition

6

5

3

7

4

11

8

-1

 

 

 

↑

 

 

 

 

  • We want to divide the array into smaller and larger parts and put the pivot in between them

  • If we see a smaller value, increase the size of the smaller part and put the value in the smaller part

  • When we’re done, we’ll know where to put the pivot

Quicksort: Partition

6

5

3

4

7

11

8

-1

 

 

 

 

↑

 

 

 

  • We want to divide the array into smaller and larger parts and put the pivot in between them

  • If we see a smaller value, increase the size of the smaller part and put the value in the smaller part

  • When we’re done, we’ll know where to put the pivot

Quicksort: Partition

6

5

3

4

7

11

8

-1

 

 

 

 

↑

 

 

 

  • We want to divide the array into smaller and larger parts and put the pivot in between them

  • If we see a smaller value, increase the size of the smaller part and put the value in the smaller part

  • When we’re done, we’ll know where to put the pivot

Quicksort: Partition

6

5

3

4

7

11

8

-1

 

 

 

 

↑

 

 

 

  • We want to divide the array into smaller and larger parts and put the pivot in between them

  • If we see a smaller value, increase the size of the smaller part and put the value in the smaller part

  • When we’re done, we’ll know where to put the pivot

Quicksort: Partition

6

5

3

4

-1

11

8

7

 

 

 

 

 

↑

 

 

  • We want to divide the array into smaller and larger parts and put the pivot in between them

  • If we see a smaller value, increase the size of the smaller part and put the value in the smaller part

  • When we’re done, we’ll know where to put the pivot

Quicksort: Partition

-1

5

3

4

6

11

8

7

 

 

 

 

 

↑

 

 

  • We want to divide the array into smaller and larger parts and put the pivot in between them

  • If we see a smaller value, increase the size of the smaller part and put the value in the smaller part

  • When we’re done, we’ll know where to put the pivot

Quicksort: Partition

-1

5

3

4

6

11

8

7

 

 

 

 

 

↑

 

 

  • We want to divide the array into smaller and larger parts and put the pivot in between them

  • If we see a smaller value, increase the size of the smaller part and put the value in the smaller part

  • When we’re done, we’ll know where to put the pivot

Quicksort Runtime: Best Case

Let’s consider an array of size 8. In the best case, the pivot divides the array evenly at each step. So the analysis is similar to Mergesort:

  • Partition 1: 1 O(n) partition where n = 8 into two arrays of size 4

  • Partition 2: 2 O(n) partition where n = 4 into four arrays of size 2

  • Partition 3: 4 O(n) partition where n = 2 into eight arrays of size 1

  • So given n = 8, we have done 3 O(n) steps, or O(n log n).

But Trouble Lurks…​

Quicksort Runtime: Worst Case

Let’s consider an array of size 8. In the worst case, the pivot is the maximum or minimum value in each step.

  • Partition 1: 1 O(n) partition where n = 8 into two arrays of size 7 and size 1

  • Partition 2: 1 O(n) partition where n = 7 into two arrays of size 6 and size 1

  • Partition 3: 1 O(n) partition where n = 6 into two arrays of size 5 and size 1

  • Partition 4: 1 O(n) partition where n = 5 into two arrays of size 4 and size 1

  • …​etc…​

  • So given n = 8, we have done n O(n) steps, or O(n^2)!

Quicksort: Worst Case Overview

8

7

6

5

4

3

2

1

  • In the worst case the problem only gets 1 unit smaller in each step!

Quicksort: Worst Case Overview

8

7

6

5

4

3

2

1

  • In the worst case the problem only gets 1 unit smaller in each step!

Quicksort: Worst Case Overview

7

6

5

4

3

2

1

8

  • In the worst case the problem only gets 1 unit smaller in each step!

Quicksort: Worst Case Overview

7

6

5

4

3

2

1

8

  • In the worst case the problem only gets 1 unit smaller in each step!

Quicksort: Worst Case Overview

6

5

4

3

2

1

7

8

  • In the worst case the problem only gets 1 unit smaller in each step!

Quicksort: Worst Case Overview

6

5

4

3

2

1

7

8

  • In the worst case the problem only gets 1 unit smaller in each step!

Quicksort: Worst Case Overview

6

5

4

3

2

1

7

8

  • In the worst case the problem only gets 1 unit smaller in each step!

Quicksort: Worst Case Overview

5

4

3

2

1

6

7

8

  • In the worst case the problem only gets 1 unit smaller in each step!

Quicksort: Worst Case Overview

5

4

3

2

1

6

7

8

  • In the worst case the problem only gets 1 unit smaller in each step!

Quicksort: Worst Case Overview

5

4

3

2

1

6

7

8

  • In the worst case the problem only gets 1 unit smaller in each step!

Quicksort: Worst Case Overview

4

3

2

1

5

6

7

8

  • In the worst case the problem only gets 1 unit smaller in each step!

Quicksort: Worst Case Overview

4

3

2

1

5

6

7

8

  • In the worst case the problem only gets 1 unit smaller in each step!

Avoiding Bad Pivots

Good Quicksort implementations try to avoid picking bad pivot values:

  • First value: fails if the array is sorted in reverse order

  • Last value: fails if the array in already sorted

  • Better idea: choose a random value, or the median of several values

Quicksort Runtime

Measure Best Case Worst Case Average Case

Time

O(n log n)

O(n^2)

O(n log n)

Space

O(log n)

O(n)

O(log n)

One advantage of Quicksort over Mergesort is that it can be done in-place without requiring extra space.

Sorting Summary: Input Dependence

Algorithm Best Case Worst Case

Insertion Sort

Already sorted

Sorted backwards

Merge Sort

Doesn’t matter

Doesn’t matter

Quicksort

Random

Sorted 1

(Note that most of these are implementation dependent.)

Sorting Summary: Runtime

Algorithm Best Case Worst Case Average Case

Insertion Sort

O(n)

O(n^2)

O(n^2)

Merge Sort

O(n log n)

O(n log n)

O(n log n)

Quicksort

O(n log n)

O(n^2)

O(n log n)

Sorting Summary: Space

Algorithm Extra Memory

Insertion Sort

O(1)

Merge Sort

O(n)

Quicksort

O(log n), due to the recursive calls

There Be Tradeoffs

  • If you have a very small array? Try insertion sort. It avoids the recursive calls made by merge sort and quick sort and is fastest on small arrays.

  • Do you want predictable performance? Try merge sort. It’s performance doesn’t vary based on its inputs, although it requires O(n) space.

  • Are you short on space? Try Quicksort. It’s best-case performance is as good as merge sort but it can be done using much less memory.

Sorting Stability

We also refer to sorts as being either stable or unstable:

  • Stable sorts: two items with the same value cannot switch positions

  • Unstable sorts: two items with the same value may switch positions

Why Is Stability Important?

class Person {
  int age;
  String name;
}

Let’s say I wanted a list of all Persons, sorted first by age and then by name. How would I do that?

  1. Sort first using the name field

  2. Then sort by the age field

If the sort is not stable I cannot do this, since the second sort will alter the results of the first.

What About Timsort?

Timsort is the adaptive sorting algorithm used by Python and now Java.

  • It’s far more complex than any of the algorithms we’ve discussed, but tries to take advantage of runs of already-sorted values in the data.

  • Internally it uses both merge sort and insertion sort to sort smaller arrays and combine them together.

  • It’s an adaptive sort, meaning that it adjusts its behavior to features of the data.

A Fun Visualization

Questions About Sorting?

Announcements

  • Good luck finishing up MP4!

  • I have office hours today from 1–3PM. Please come by! It’s not too late to stop by and introduce yourself.

Keyboard Shortcuts

Here is a list of potentially helpful keyboard shortcuts:

  • : go forward to the next slide
  • : go back to the previous slide
  • o: open (and close) the slide overview
  • m: open (and close) the top menu
  • h: open (and close) this help menu