ECE209_sorting2.pptx
ECE 209 Fall 2012 Sorting
10/24/12
2
Quicksort: Big Picture
Choose a random element,
called the partitioning element, P.
Partition the array into two regions:
In one, all elements are smaller than P.
In the other, all elements are larger than P.
Element P goes in between,
which is its correct position in the sorted array.
Then (recursively) sort each of the two partitions.
ECE 209 Fall 2012 Sorting
10/24/12
3
Quicksort: Big Picture
ECE 209 Fall 2012 Sorting
10/24/12
4
Quicksort: Runtime Analysis
How many operations to sort an N-element array?
Let T(N) be operations to sort N elements.
Partition of N elements takes N-1 comparisons, N exch.
On avg, partition will divide the array into two equal parts.
T(N) ≈ N + 2T(N/2)
ECE 209 Fall 2012 Sorting
10/24/12
5
Quicksort: Runtime Analysis
How many operations to sort an N-element array?
Let T(N) be operations to sort N elements.
Partition of N elements takes N-1 comparisons, N exch.
On avg, partition will divide the array into two equal parts.
T(N) ≈ N + 2T(N/2)
≈ N + 2(N/2 + 2T(N/4)) = 2N + 4T(N/4)
ECE 209 Fall 2012 Sorting
10/24/12
6
Quicksort: Runtime Analysis
How many operations to sort an N-element array?
Let T(N) be operations to sort N elements.
Partition of N elements takes N-1 comparisons, N exch.
On avg, partition will divide the array into two equal parts.
T(N) ≈ N + 2T(N/2)
≈ N + 2(N/2 + 2T(N/4)) = 2N + 4T(N/4)
≈ 2N + 4(N/4 + 2T(N/8)) = 3N + 8T(N/8)
ECE 209 Fall 2012 Sorting
10/24/12
7
Quicksort: Runtime Analysis
How many operations to sort an N-element array?
Let T(N) be operations to sort N elements.
Partition of N elements takes N-1 comparisons, N exch.
On avg, partition will divide the array into two equal parts.
T(N) ≈ N + 2T(N/2)
≈ N + 2(N/2 + 2T(N/4)) = 2N + 4T(N/4)
≈ 2N + 4(N/4 + 2T(N/8)) = 3N + 8T(N/8)
…repeated log2N times, until…
≈ (log2N)·N + 2log2N·T(1)
≈ Nlog2N + 2log2N
= O(NlogN)
ECE 209 Fall 2012 Sorting
10/24/12
8
Is NlogN better than N2?
10000
664.39
0
2000
4000
6000
8000
10000
0
10
20
30
40
50
60
70
80
90
100
N*N
N*logN
ECE 209 Fall 2012 Sorting
10/24/12
9
Quicksort: Algorithm
Given: a sequence, A, of n items (A1 to An)
If n = 1, exit (already sorted)
Let partition element P = An
Partition A according to P,
Let m = index of element P after partition
Perform Quicksort on sequence A1…Am-1
Perform Quicksort on sequence Am+1…An
ECE 209 Fall 2012 Sorting
10/24/12
10
Quicksort: Code
int partition(Item a[], int left, int right);
void quicksort(Item a[], int left, int right) {
/* left is index of leftmost element,
right is index of rightmost element */
int m;
if (left >= right) return; /* termination condition */
/* partition and return index of partition element */
m = partition(a, left, right);
/* recursively sort sub-arrays */
quicksort(a, left, m-1);
quicksort(a, m+1, right);
return;
}
ECE 209 Fall 2012 Sorting
10/24/12
11
Partition: Algorithm
Given: a sequence, A, of n items (A1 to An)
Let partition element P = An
Let i = 1, j = n-1
Repeat
Let i = index of leftmost element > P
Let j = index of rightmost element < P
If i < j, exchange Ai and Aj
Until i >= j
Exchange An with Ai (putting P in its correct place)
Return i
ECE 209 Fall 2012 Sorting
10/24/12
12
Partition: Code
int partition(Item a[], int left, int right) {
int i = left-1, j = right;
Item p = a[right];
while (1) {
while (LESS(a[++i],p));
while (LESS(p,a[–j])) if (j == left) break;
if (i >= j) break;
EXCH(a[i],a[j]);
}
EXCH(a[i],a[right]);
return i;
}
ECE 209 Fall 2012 Sorting
10/24/12
13
Quicksort Observations
O(N2) in the worst case.
For an array that’s already in sorted order, partition will divide the
array into a zero-element subarray and an (N-1)-element subarray.
How many activation records on stack?
Avg case — logN. Worst case — N.
Not very efficient for small arrays.
E.g., use selection sort when subarray becomes 10 elements or less.
ECE 209 Fall 2012 Sorting
10/24/12
14
My Timing Experiment
Random
Order
Selec5on
Sort
12.8
Bubble
Sort
30.5
Quicksort
0.015
array of 80,000 integers
times in seconds
ECE 209 Fall 2012 Sorting
10/24/12
15
My Timing Experiment
Random
Order
In-‐order
Selec5on
Sort
12.8
12.6
Bubble
Sort
30.5
0
Quicksort
0.015
crashed
array of 80,000 integers
times in seconds
ECE 209 Fall 2012 Sorting
10/24/12
16
My Timing Experiment
Random
Order
In-‐order
Reverse-‐
order
Selec5on
Sort
12.8
12.6
13.2
Bubble
Sort
30.5
0
29.5
Quicksort
0.015
crashed
crashed
array of 80,000 integers
times in seconds