Quicksort
> Click or hit ControlEnter to run the code above
Q8 Review: Recursion v. Iteration
True or false: iteration can solve problems that recursive solutions cannot.
Q8 Review: Iteration v. Recursion
True or false: recursion can solve problems that iterative solutions cannot.
Q8 Review: Buggy Recursive Code
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?
Q8 Review: More Buggy Recursive Code
/**
* 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 ControlEnter to run Example.main above
Questions About CBTF Programming?
(We are working on the performance problems.)
There Are Many Sorting Algorithms
And we won’t discuss them all…

Insertion sort (last Wednesday)

Selection sort (lab)

Merge sort (last Friday)

Quicksort (today!)

Bubble sort (lab)

Timsort (maybe today)
Divide and Conquer
Divide and conquer is an algorithm design paradigm based on multibranched recursion. A divide and conquer algorithm works by recursively breaking down a problem into two or more subproblems of the same or related type, until these become simple enough to be solved directly. The solutions to the subproblems are then combined to give a solution to the original problem.
Quicksort: Overview
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: Overview
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: Overview
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: Overview
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: Overview
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: Overview
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: Overview
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: Overview
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: Overview
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
> Click or hit ControlEnter to run the code above
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 inplace 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 bestcase 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 Person
s, 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.
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 alreadysorted 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.
Questions About Sorting?
A Fun Visualization
Announcements

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.