CS2040S
Data Structures and Algorithms
Welcome!
Does this sorting algorithm work correct? If not, can you fix it…
Last Time: Sorting
Sorting algorithms
o BubbleSort
o SelectionSort
o InsertionSort
o MergeSort
Properties
o Running time
o Space usage
o Stability
Today: more sorting!
QuickSort:
– Divide-and-Conquer
– Partitioning
– Duplicates
– Choosing a pivot
– Randomization
– Analysis
Recursive… Step 1:
Divide array into two pieces.
MergeSort(A, n)
if (n=1) then return;
else:
X ¬MergeSort(A[1..n/2], n/2);
Y ¬MergeSort(A[n/2+1, n], n/2);
return Merge (X,Y, n/2);
Recursive… Step 2:
Recursively sort the two halves.
MergeSort(A, n)
if (n=1) then return;
else:
X ¬MergeSort(A[1..n/2], n/2);
Y ¬MergeSort(A[n/2+1, n], n/2);
return Merge (X,Y, n/2);
Sort Sort
Recursive… Step 3:
Merge the two halves into
one sorted array.
MergeSort(A, n)
if (n=1) then return;
else:
X ¬MergeSort(A[1..n/2], n/2);
Y ¬MergeSort(A[n/2+1, n], n/2);
return Merge (X,Y, n/2);
Merge
Source: Wikipedia
MergeSort, Bottom Up
1 2 3 4 5 6 7 8 9 10 11 12 13 15 15 16
2 4 6 7 9 12 13 15 1 3 5 8 10 11 14 16
2 7 9 15 4 6 12 13 1 5 8 10 3 11 14 16
7 15 2 9 6 12 4 13 1 8 5 10 3 14 11 16
15 7 9 2 6 12 13 4 1 8 10 5 3 14 11 16
Challenge 1:
Write an iterative version of MergeSort.
No recursion allowed!
MergeSort
Space usage…
– Need extra space to do merge.
– Merge copies data to new array.
Space Complexity
Question:
How much space is allocated during a call to
MergeSort?
Note:
Measure total allocated space.
We will not model garbage
collection or other Java details.
Space Complexity
Question:
How much space is allocated during a call to
MergeSort?
Key subroutine: Merge
Merging Two Sorted Lists
20 12 20 12 20 12 20 12
13 11 13 11 13 11 13 11
7 9 7 9 7 9 9
2 1 2
1 2 7 9
Need temporary array of size n.
Space Analysis
Let S(n) be the worst-case space allocated for
an array of n elements.
MergeSort(A, n)
if (n=1) then return; q(1)
else:
X ¬Merge-Sort(…); S(n/2)
Y ¬Merge-Sort(…); S(n/2)
return Merge (X,Y, n/2); n
S(n) = 2S(n/2) + n
S(n) = ?
A. O(log n)
B. O(n)
C. O(n log n)
D. O(n2)
E. O(n2 log n)
F. O(2n)
is open
Space Analysis
Let S(n) be the worst-case space for an array
of n elements.
S(n) = q(1) if (n=1)
= 2S(n/2) + n if (n>1)
= O(n log n)
MergeSort
1 2 3 4 5 6 7 8 9 10 11 12 13 15 15 16
2 4 6 7 9 12 13 15 1 3 5 8 10 11 14 16
2 7 9 15 4 6 12 13 1 5 8 10 3 11 14 16
7 15 2 9 6 12 4 13 1 8 5 10 3 14 11 16
15 7 9 2 6 12 13 4 1 8 10 5 3 14 11 16
Space Analysis
S(n) = 2S(n/2) + n
merge
recursive recursive
sort
n sort
S(n/2) S(n/2)
Space Analysis
S(n) = 2S(n/2) + n
n
n/2 n/2
S(n/4) S(n/4) S(n/4) S(n/4)
Space Analysis
S(n) = 2S(n/2) + n
n
n/2 n/2
S(n/4) S(n/4) S(n/4) S(n/4)
Space Analysis
S(n) = 2S(n/2) + n
n
n/2 n/2
n/4 n/4 n/4 n/4
S(n/8) S(n/8) S(n/8) S(n/8) S(n/8) S(n/8) S(n/8) S(n/8)
Space Analysis
S(n) = 2S(n/2) + n
n
n/2 n/2
n/4 n/4 n/4 n/4
n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8
Base case
Space Analysis
S(n) = 2S(n/2) + n
n =n
n/2 n/2 =n
n/4 n/4 n/4 n/4 =n
n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8 =n
Space Analysis
S(n) = 2S(n/2) + n
n =n
n/2 n/2 =n
n/4 n/4 n/4 n/4 =n
n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8 =n
n log n
Space Analysis
S(n) =O(n log n)
MergeSort(A, n)
if (n=1) then return;
else: q(1)
X ¬MergeSort(…);
Y ¬MergeSort(…); S(n/2)
return Merge (X,Y, n/2); S(n/2)
q(n)
Challenge 2:
Design a version of MergeSort that minimizes the
amount of extra space needed.
Hint: Do not allocate any new space during the
recursive calls!
MergeSort: log(n) arrays
1 2 3 4 5 6 7 8 9 10 11 12 13 15 15 16
2 4 6 7 9 12 13 15 1 3 5 8 10 11 14 16
2 7 9 15 4 6 12 13 1 5 8 10 3 11 14 16
7 15 2 9 6 12 4 13 1 8 5 10 3 14 11 16
15 7 9 2 6 12 13 4 1 8 10 5 3 14 11 16
MergeSort: 2 arrays
1 2 3 4 5 6 7 8 9 10 11 12 13 15 15 16
2 4 6 7 9 12 13 15 1 3 5 8 10 11 14 16
2 7 9 15 4 6 12 13 1 5 8 10 3 11 14 16
7 15 2 9 6 12 4 13 1 8 5 10 3 14 11 16
15 7 9 2 6 12 13 4 1 8 10 5 3 14 11 16
Better Space Usage
On termination, items in range
Use only one temporary array! [begin,end] are sorted in A.
The tempArray is used for
MergeSort(A, begin, end, tempArray) workspace.
if (begin=end) then return;
else:
mid = begin + (end-begin)/2
MergeSort(A, begin, mid, tempArray);
MergeSort(A, mid+1, end, tempArray);
Merge(A[begin..mid], A[mid+1, end], tempArray);
Copy(tempArray, A, begin, end); Merge copies items into
tempArray.
We then copy the items back
into array A.
Better Space Usage
S(n) = 2S(n/2) + O(1) = O(n)
MergeSort(A, begin, end, tempArray)
if (begin=end) then return;
else:
mid = begin + (end-begin)/2
MergeSort(A, begin, mid, tempArray);
MergeSort(A, mid+1, end, tempArray);
Merge(A[begin..mid], A[mid+1, end], tempArray);
Copy(tempArray, A, begin, end);
Better Space Usage
Still a problem: can we avoid the extra copying of data?
MergeSort(A, begin, end, tempArray)
if (begin=end) then return;
else:
mid = begin + (end-begin)/2
MergeSort(A, begin, mid, tempArray);
MergeSort(A, mid+1, end, tempArray);
Merge(A[begin..mid], A[mid+1, end], tempArray);
Copy(tempArray, A, begin, end);
Better Space Usage
Idea: switch temporary array at every step!
Initially, both A and B have
MergeSort(A, B, begin, end) copies of the unsorted array.
if (begin=end) then return;
else:
mid = begin + (end-begin)/2
MergeSort(B, A, begin, mid);
MergeSort(B, A, mid+1, end);
Merge(A, B, begin, mid, end);
Copy(B, A, begin, end); Switch the order of A and B at
every recursive call.
Today: more sorting!
QuickSort:
– Divide-and-Conquer
– Partitioning
– Duplicates
– Choosing a pivot
– Randomization
– Analysis
QuickSort
History:
– Invented by C.A.R. Hoare in 1960
• Turing Award: 1980
– Visiting student at
Moscow State University
– Used for machine
translation
(English/Russian)
Photo: Wikimedia Commons (Rama)
Hoare
Quote:
“There are two ways of constructing a software
design:
One way is to make it so simple that there are
obviously no deficiencies, and the other way is
to make it so complicated that there are no
obvious deficiencies.
The first method is far more difficult.”
QuickSort
History:
– Invented by C.A.R. Hoare in 1960
– Used for machine translation (English/Russian)
In practice:
– Very fast
– Many optimizations
– In-place (i.e., no extra space needed)
– Good caching performance
– Good parallelization
QuickSort Today
1960: Invented by Hoare
1979: Adopted everywhere (e.g., Unix qsort)
1993: Bentley & McIlroy improvements
“Engineering a sort function”
Yet in the summer of 1991 our colleagues Allan Wilks and
Rick Becker found that a qsort run that should have taken a
few minutes was chewing up hours of CPU time. Had they
not interrupted it, it would have gone on for weeks. They
found that it took n2 comparisons to sort an ‘organ-pipe’
array of 2n integers: 123..nn.. 321.
QuickSort Today
1960: Invented by Hoare
1979: Adopted everywhere (e.g., Unix qsort)
1993: Bentley & McIlroy improvements
”Ok, QuickSort is done,” said everyone.
Every algorithms class since 1993:
Punk in the front row:
“But what if we used more pivots?”
Every algorithms class since 1993:
Punk in the front row:
“But what if we used more pivots?”
Professor:
“Doesn’t work. I can prove it.
Let’s get back to the syllabus….”
In 2009:
Punk in the front row:
“But what if we used more pivots?”
Professor:
“Doesn’t work. I can prove it.
Let’s get back to the syllabus….”
Punk in the front row:
“Huh… let me try it. Wait a sec, it’s faster!”
QuickSort Today
1960: Invented by Hoare
1979: Adopted everywhere (e.g., Unix qsort)
1993: Bentley & McIlroy improvements
2009: Vladimir Yaroslavskiy
– Dual-pivot Quicksort !!!
– Now standard in Java
– 10% faster!
QuickSort Today
1960: Invented by Hoare
1979: Adopted everywhere (e.g., Unix qsort)
1993: Bentley & McIlroy improvements
2009: Vladimir Yaroslavskiy
– Dual-pivot Quicksort !!!
– Now standard in Java
– 10% faster!
2012: Sebastian Wild and Markus E. Nebel
– “Average Case Analysis of Java 7’s Dual Pivot…”
– Best paper award at ESA
Moral of the story:
1) Don’t just listen to me. Go try it!
2) Even “classical” algorithms change.
QuickSort in 5 years may be different
than QuickSort I am teaching today.
QuickSort
History:
– Invented by C.A.R. Hoare in 1960
– Used for machine translation (English/Russian)
In practice:
– Very fast
– Many optimizations
– In-place (i.e., no extra space needed)
– Good caching performance
– Good parallelization
QuickSort
QuickSort(A[1..n], n)
if (n==1) then return;
else
p = partition(A[1..n], n)
x = QuickSort(A[1..p-1], p-1)
y = QuickSort(A[p+1..n], n-p)
S m a l l B i g
partition
sort sort
QuickSort
Before partition
S m a l l B i g
partition
sort sort
QuickSort
pivot
After partition
S m a l l B i g
partition
sort sort
QuickSort
QuickSort(A[1..n], n)
if (n==1) then return;
else
p = partition(A[1..n], n)
x = QuickSort(A[1..p-1], p-1)
y = QuickSort(A[p+1..n], n-p)
S m a l l B i g
partition
sort sort
QuickSort
Given: n element array A[1..n]
1. Divide: Partition the array into two sub-arrays
around a pivot x such that elements in lower
subarray ≤ x ≤ elements in upper sub-array.
<x x >x
2. Conquer: Recursively sort the two sub-arrays.
3. Combine: Trivial, do nothing.
Key: efficient partition sub-routine
Partitioning an Array
Three steps:
1. Choose a pivot.
2. Find all elements smaller than the pivot.
3. Find all elements larger than the pivot.
<x x >x
Quicksort
Example:
6 3 9 8 4 2
Quicksort
Example:
6 3 9 8 4 2
3 4 2 6 9 8
Quicksort
Example:
6 3 9 8 4 2
3 4 2 6 9 8
2 3 4
Quicksort
Example:
6 3 9 8 4 2
3 4 2 6 9 8
2 3 4 8 9
Quicksort
Example:
6 3 9 8 4 2
3 4 2 6 9 8
2 3 4 6 8 9
Quicksort
Example:
6 3 9 8 4 2
3 4 2 6 9 8
2 3 4 6 8 9
The following array has been partitioned
around which element?
18 5 6 1 10 22 40 32 31
a. 6
b. 10
c. 22
d. 40
e. 32
f. I don’t know.
is open
Partitioning an Array
Example: partition around 22
22 1 6 40 32 10 18 50 4
Output array:
low high
< 22 > 22
Partitioning an Array
Example: partition around 22
22 1 6 40 32 10 18 50 4
Output array:
1
< 22
low high
> 22
Partitioning an Array
Example: partition around 22
22 1 6 40 32 10 18 50 4
Output array:
1 6
< 22
low high
> 22
Partitioning an Array
Example: partition around 22
22 1 6 40 32 10 18 50 4
Output array:
1 6 40
< 22 > 22
low high
Partitioning an Array
Example: partition around 22
22 1 6 40 32 10 18 50 4
Output array:
1 6 32 40
< 22 > 22
low high
Partitioning an Array
Example: partition around 22
22 1 6 40 32 10 18 50 4
Output array:
1 6 10 32 40
< 22 > 22
low high
Partitioning an Array
Example: partition around 22
22 1 6 40 32 10 18 50 4
Output array:
1 6 10 18 32 40
< 22 > 22
low high
Partitioning an Array
Example: partition around 22
22 1 6 40 32 10 18 50 4
Output array:
1 6 10 18 50 32 40
< 22 > 22
low high
Partitioning an Array
Example: partition around 22
22 1 6 40 32 10 18 50 4
Output array:
1 6 10 18 4 50 32 40
< 22 > 22
high
low
Partitioning an Array
Example: partition around 22
22 1 6 40 32 10 18 50 4
Output array:
1 6 10 18 4 22 50 32 40
< 22 > 22
high
low
partition(A[2..n], n, pivot) // Assume no duplicates
B = new n element array i
low = 1;
high = n;
22 1 6 40 32 10 18 50 4
for (i = 2; i<= n; i++)
if (A[i] < pivot) then
B[low] = A[i];
low++; 1 6 10 18 32 40
else if (A[i] > pivot) then
< 22 > 22
B[high] = A[i];
high– – ; low high
B[low] = pivot;
return < B, low >
Partition
Claim: array B is partitioned around the pivot
Proof:
Invariants:
1. For every i < low : B[i] < pivot
2. For every j > high : B[j] > pivot
In the end, every element from A is copied to B.
Then: B[i] = pivot
By invariants, B is partitioned around the pivot.
Partitioning an Array
Example:
22 1 6 40 32 10 18 50 4
What is the running time of partition?
1. O(log n)
2. O(n)
3. O(n log n)
4. O(n2)
5. I have no idea.
is open
Any bugs?
Anything that can be improved?
is open
partition(A[2..n], n, pivot) // Assume no duplicates
B = new n element array i
low = 1;
high = n;
22 1 6 40 32 10 18 50 4
for (i = 2; i<= n; i++)
if (A[i] < pivot) then
B[low] = A[i];
low++; 1 6 10 18 32 40
else if (A[i] > pivot) then
< 22 > 22
B[high] = A[i];
high– – ; low high
B[low] = pivot;
return < B, low >
Partitioning an Array “in-place”
Example: partition around 22
22 1 6 40 32 10 18 4 50
low high
< 22 > 22
Move until it’s Move until it’s
bigger than the less than the
pivot pivot
Partitioning an Array
Example: partition around 22
22 1 6 40 32 10 18 4 50
low high
< 22 > 22
Partitioning an Array
Example: partition around 22
22 1 6 40 32 10 18 4 50
< 22
low high
> 22
Partitioning an Array
Example: partition around 22
22 1 6 40 32 10 18 4 50
< 22
low high
> 22
Partitioning an Array
Example: partition around 22
22 1 6 40 32 10 18 4 50
< 22 > 22
low high
Partitioning an Array
Example: partition around 22
22 1 6 40 32 10 18 4 50
< 22 > 22
low high
Partitioning an Array
Example: partition around 22
22 1 6 4 32 10 18 40 50
< 22 > 22
low high
Partitioning an Array
Example: partition around 22
22 1 6 4 32 10 18 40 50
< 22 > 22
low high
Partitioning an Array
Example: partition around 22
22 1 6 4 32 10 18 40 50
< 22 > 22
low high
Partitioning an Array
Example: partition around 22
22 1 6 4 32 10 18 40 50
< 22 > 22
low high
Partitioning an Array
Example: partition around 22
22 1 6 4 18 10 32 40 50
< 22 > 22
low high
Partitioning an Array
Example: partition around 22
22 1 6 4 18 10 32 40 50
< 22 > 22
low high
Partitioning an Array
Example: partition around 22
22 1 6 4 18 10 32 40 50
< 22 > 22
high
low
Partitioning an Array
Example: partition around 22
22 1 6 4 18 10 32 40 50
< 22 > 22
high
low
Partitioning an Array
Example: partition around 22
10 1 6 4 18 22 32 40 50
< 22 > 22
high
low
partition(A[1..n], n, pIndex) // Assume no duplicates, n>1
pivot = A[pIndex]; // pIndex is the index of pivot
swap(A[1], A[pIndex]); // store pivot in A[1]
low = 2; // start after pivot in A[1]
high = n+1; // Define: A[n+1] = ¥
while (low < high)
while (A[low] <= pivot) and (low < high) do low++;
while (A[high] > pivot) and (low < high) do high– – ;
if (low < high) then swap(A[low], A[high]);
swap(A[1], A[low–1]);
return low–1;
Pseudocode
vs.
Real Code
QuickSort is notorious for off-by-one errors…
Partition
Invariant: A[high] > pivot at the end of each loop.
Proof:
Initially: true by assumption A[n+1]= ¥
Partition
Invariant: A[high] > pivot at the end of each iter:
Proof: During loop:
– When exit loop incrementing low: A[low] > pivot
If (low > high), then by while condition.
If (low = high), then by inductive assumption.
– When exit loop decrementing high:
A[high] < pivot OR low = high
– If (high == low), then A[high] > pivot
– Otherwise, swap A[high] and A[low]>pivot.
partition(A[1..n], n, pIndex) // Assume no duplicates, n>1
pivot = A[pIndex]; // pIndex is the index of pivot
swap(A[1], A[pIndex]); // store pivot in A[1]
low = 2; // start after pivot in A[1]
high = n+1; // Define: A[n+1] = ¥
while (low < high)
while (A[low] < pivot) and (low < high) do low++;
while (A[high] > pivot) and (low < high) do high– – ;
if (low < high) then swap(A[low], A[high]);
swap(A[1], A[low–1]);
return low–1;
Partition
Invariant: At the end of every loop iteration:
for all i >= high, A[i] > pivot.
for all 1 < j < low, A[j] < pivot.
22 1 6 4 18 10 32 40 50
< 22 > 22
low high
Partition
Invariant: At the end of every loop iteration:
for all i >= high, A[i] > pivot.
for all 1 < j < low, A[j] < pivot.
22 1 6 4 18 10 32 40 50
< 22 > 22
high
low
Partition
Claim: At the end of every loop iteration:
for all i >= high, A[i] > pivot.
for all 1 < j < low, A[j] < pivot.
10 1 6 4 18 22 32 40 50
< 22 > 22
high
low
Claim: Array A is partitioned around the pivot
partition(A[1..n], n, pIndex) // Assume no duplicates, n>1
pivot = A[pIndex]; // pIndex is the index of pivot
swap(A[1], A[pIndex]); // store pivot in A[1]
low = 2; // start after pivot in A[1]
high = n+1; // Define: A[n+1] = ¥
while (low < high)
while (A[low] < pivot) and (low < high) do low++;
while (A[high] > pivot) and (low < high) do high– – ;
if (low < high) then swap(A[low], A[high]);
swap(A[1], A[low–1]);
return low–1;
partition(A[1..n], n, pIndex) // Assume no duplicates, n>1
pivot = A[pIndex]; // pIndex is the index of pivot
Running time:
swap(A[1], A[pIndex]); // store pivot in A[1]
low = 2; // start after
O(n)pivot in A[1]
high = n+1; // Define: A[n+1] = ¥
while (low < high)
while (A[low] < pivot) and (low < high) do low++;
while (A[high] > pivot) and (low < high) do high– – ;
if (low < high) then swap(A[low], A[high]);
swap(A[1], A[low–1]);
return low–1;
QuickSort
QuickSort(A[1..n], n)
if (n == 1) then return;
else
Choose pivot index pIndex.
p = partition(A[1..n], n, pIndex)
x = QuickSort(A[1..p–1], p–1)
y = QuickSort(A[p+1..n], n–p)
<x x >x
Sorting, continued
QuickSort
– Divide-and-Conquer
– Partitioning
– Duplicates
– Choosing a pivot
– Randomization
– Analysis
QuickSort
What happens if there are duplicates?
is open
Duplicates
QuickSort(A[1..n], n)
if (n==1) then return;
else
Choose pivot index pIndex.
p = partition(A[1..n], n, pIndex)
x = QuickSort(A[1..p–1], p–1)
y = QuickSort(A[p+1..n], n–p)
<x x x x >x
Quicksort
Example:
6 6 6 6 6 6
Quicksort
Example:
6 6 6 6 6 6
6 6 6 6 6 6
Quicksort
Example:
6 6 6 6 6 6
6 6 6 6 6 6
6 6 6 6 6 6
Quicksort
Example:
6 6 6 6 6 6
6 6 6 6 6 6
6 6 6 6 6 6
6 6 6 6 6 6
Quicksort
Example:
6 6 6 6 6 6
6 6 6 6 6 6
6 6 6 6 6 6
6 6 6 6 6 6
6 6 6 6 6 6
Quicksort
Example:
6 6 6 6 6 6
6 6 6 6 6 6
6 6 6 6 6 6
6 6 6 6 6 6
6 6 6 6 6 6
6 6 6 6 6 6
Quicksort
Example:
6 6 6 6 6 6
6 6 6 6 6 6
6 6 6 6 6 6
6 6 6 6 6 6
6 6 6 6 6 6
6 6 6 6 6 6
6 6 6 6 6 6
Quicksort
What is the running time on the all 6’s array?
6 6 6 6 6 6
6 6 6 6 6 6
6 6 6 6 6 6
6 6 6 6 6 6
6 6 6 6 6 6
is open 6 6 6 6 6 6
Quicksort
Example:
6 6 6 6 6 6
Running 6 6 6 6 6 6
time:
6 6 6 6 6 6
O(n2) 6 6 6 6 6 6
6 6 6 6 6 6
6 6 6 6 6 6
6 6 6 6 6 6
partition(A[1..n], n, pIndex) // Assume no duplicates, n>1
pivot = A[pIndex]; // pIndex is the index of pivot
swap(A[1], A[pIndex]); // store pivot in A[1]
low = 2; // start after pivot in A[1]
high = n+1; // Define: A[n+1] = ¥
while (low < high)
while (A[low] < pivot) and (low < high) do low++;
while (A[high] > pivot) and (low < high) do high– – ;
if (low < high) then swap(A[low], A[high]);
swap(A[1], A[low–1]);
return low–1;
Duplicates
QuickSort(A[1..n], n)
if (n==1) then return;
else
Choose pivot index pIndex.
p = partition(A[1..n], n, pIndex)
x = QuickSort(A[1..p–1], p–1)
y = QuickSort(A[p+1..n], n–p)
x x x >x
Duplicates
QuickSort(A[1..n], n)
if (n==1) then return;
else
Choose pivot index pIndex.
p = partition(A[1..n], n, pIndex)
x = QuickSort(A[1..p–1], p–1)
y = QuickSort(A[p+1..n], n–p)
<x x x x >x
Pivot
Duplicates
3-Way Partitioning
– Option 1: two pass partitioning
1. Regular partition.
2. Pack duplicates.
Pack Duplicates
Example:
2 6 3 6 4 6 5 6 9 9 9 9
index pivotIndex
Pack Duplicates
Example:
2 6 3 6 4 6 5 6 9 9 9 9
index pivotIndex
Pack Duplicates
Example:
2 6 3 6 4 6 5 6 9 9 9 9
index pivotIndex
Pack Duplicates
Example:
2 6 3 6 4 6 5 6 9 9 9 9
index pivotIndex
Pack Duplicates
Example:
2 5 3 6 4 6 6 6 9 9 9 9
index pivotIndex
Pack Duplicates
Example:
2 5 3 6 4 6 6 6 9 9 9 9
index pivotIndex
Pack Duplicates
Example:
2 5 3 6 4 6 6 6 9 9 9 9
index pivotIndex
Pack Duplicates
Example:
2 5 3 6 4 6 6 6 9 9 9 9
index pivotIndex
Pack Duplicates
Example:
2 5 3 6 4 6 6 6 9 9 9 9
index
pivotIndex
Pack Duplicates
Example:
2 5 3 6 4 6 6 6 9 9 9 9
index
pivotIndex
Pack Duplicates
Example:
2 5 3 4 6 6 6 6 9 9 9 9
index
pivotIndex
Pack Duplicates
Example:
2 5 3 4 6 6 6 6 9 9 9 9
index
pivotIndex
Duplicates
QuickSort(A[1..n], n)
if (n==1) then return;
else
Choose pivot index pIndex.
p = 3wayPartition(A[1..n], n, pIndex)
x = QuickSort(A[1..p–1], p–1)
y = QuickSort(A[p+1..n], n–p)
<x x x x >x
Duplicates
3-Way Partitioning
– Option 1: two pass partitioning
1. Regular partition.
2. Pack duplicates.
– Option 2: one pass partitioning
• More complicated.
• Maintain four regions of the array
3-Way Partitioning
< pivot = pivot In Progress > pivot
3-Way Partitioning
< pivot = pivot In Progress > pivot
if A[i] < pivot
3-Way Partitioning
< pivot = pivot In Progress > pivot
if A[i] == pivot
3-Way Partitioning
< pivot = pivot In Progress > pivot
if A[i] > pivot
3-Way Partitioning
< pivot = pivot > pivot
Duplicates
QuickSort(A[1..n], n)
if (n==1) then return;
else
Choose pivot index pIndex.
p = 3wayPartition(A[1..n], n, pIndex)
x = QuickSort(A[1..p–1], p–1)
y = QuickSort(A[p+1..n], n–p)
<x x x x >x
Is QuickSort stable?
is open
QuickSort is not stable
< pivot = pivot In Progress > pivot
if A[i] > pivot
Sorting, continued
QuickSort
– Divide-and-Conquer
– Partitioning
– Duplicates
– Choosing a pivot
– Randomization
– Analysis