Quicksort

Quicksort
> Click or hit Control-Enter to run the code above

True or false: iteration can solve problems that recursive solutions cannot.

True or false: recursion can solve problems that iterative solutions cannot.

public void z(int value) {
  Tree current = left;
  do {
    current = current.left;
  } while (current != null);
  current.left = new Tree(value);
}

What is one problem with the function z shown above?

/**
  * Count nodes that only have a left child but no right child.
  */
public static int countLeftOnly(Tree tree) {
  if (tree.right == null) {
    if (tree.left == null) {
      return 0;
    } else {
      return 1;
    }
  } else {
    return countLeftOnly(tree.right);
    if (tree.left != null) {
      return countLeftOnly(tree.left);
    }
  }
}

What is not one (of the many) problems with the function countLeaves shown above?

> Click or hit Control-Enter to run Example.main above

(We are working on the performance problems.)

And we won’t discuss them all…

Insertion sort (last Wednesday)
Selection sort (lab)
Merge sort (last Friday)
Heapsort
Quicksort (today!)
Bubble sort (lab)
Timsort (maybe today)

Divide and conquer is an algorithm design paradigm based on multi-branched recursion. A divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.

8	5	7	3	4	11	6	-1

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

8	5	7	3	4	11	6	-1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

-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

-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

> Click or hit Control-Enter to run the code above

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).

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)!

8	7	6	5	4	3	2	1

8

7

6

5

4

3

2

1

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

8	7	6	5	4	3	2	1

8

7

6

5

4

3

2

1

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

7	6	5	4	3	2	1	8

7

6

5

4

3

2

1

8

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

7	6	5	4	3	2	1	8

7

6

5

4

3

2

1

8

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

6	5	4	3	2	1	7	8

6

5

4

3

2

1

7

8

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

6	5	4	3	2	1	7	8

6

5

4

3

2

1

7

8

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

6	5	4	3	2	1	7	8

6

5

4

3

2

1

7

8

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

5	4	3	2	1	6	7	8

5

4

3

2

1

6

7

8

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

5	4	3	2	1	6	7	8

5

4

3

2

1

6

7

8

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

5	4	3	2	1	6	7	8

5

4

3

2

1

6

7

8

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

4	3	2	1	5	6	7	8

4

3

2

1

5

6

7

8

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

4	3	2	1	5	6	7	8

4

3

2

1

5

6

7

8

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

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

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)

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.

Algorithm	Best Case	Worst Case
Insertion Sort	Already sorted	Sorted backwards
Merge Sort	Doesn’t matter	Doesn’t matter
Quicksort	Random	Sorted 1

Algorithm

Best Case

Worst Case

Insertion Sort

Already sorted

Sorted backwards

Merge Sort

Doesn’t matter

Quicksort

Random

Sorted 1

(Note that most of these are implementation dependent.)

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)

Algorithm

Best Case

Worst Case

Average Case

Insertion Sort

O(n)

O(n^2)

Merge Sort

O(n log n)

Quicksort

O(n log n)

O(n^2)

O(n log n)

Algorithm	Extra Memory
Insertion Sort	O(1)
Merge Sort	O(n)
Quicksort	O(log n), due to the recursive calls

Algorithm

Extra Memory

Insertion Sort

O(1)

Merge Sort

O(n)

Quicksort

O(log n), due to the recursive calls

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.

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

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?

Sort first using the name field
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.

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.

MP6 will be out tonight.
Get your Android environment set up! Come to office hours if you need help.
We’ve added an anonymous feedback form to the course website. Use it to give us feedback!
My office hours continue today at 11AM in the lounge outside of Siebel 0226.

Q8 Review: Recursion v. Iteration

Q8 Review: Iteration v. Recursion

Q8 Review: Buggy Recursive Code

Q8 Review: More Buggy Recursive Code

Questions About CBTF Programming?

There Are Many Sorting Algorithms

Divide and Conquer

Quicksort: Overview

Quicksort: Overview

Quicksort: Overview

Quicksort: Overview

Quicksort: Overview

Quicksort: Overview

Quicksort: Overview

Quicksort: Overview

Quicksort: Overview

Quicksort: Partition

Quicksort: Partition

Quicksort: Partition

Quicksort: Partition

Quicksort: Partition

Quicksort: Partition

Quicksort: Partition

Quicksort: Partition

Quicksort: Partition

Quicksort: Partition

Quicksort: Partition

Quicksort Runtime: Best Case

But Trouble Lurks…​

Quicksort Runtime: Worst Case

Quicksort: Worst Case Overview

Quicksort: Worst Case Overview

Quicksort: Worst Case Overview

Quicksort: Worst Case Overview

Quicksort: Worst Case Overview

Quicksort: Worst Case Overview

Quicksort: Worst Case Overview

Quicksort: Worst Case Overview

Quicksort: Worst Case Overview

Quicksort: Worst Case Overview

Quicksort: Worst Case Overview

Quicksort: Worst Case Overview

Avoiding Bad Pivots

Quicksort Runtime

Sorting Summary: Input Dependence

Sorting Summary: Runtime

Sorting Summary: Space

There Be Tradeoffs

Sorting Stability

Why Is Stability Important?

What About Timsort?

Questions About Sorting?

A Fun Visualization

Announcements

But Trouble Lurks…