The Quicksort Algorithm
undefined
Q
u
i
c
k
s
o
r
t
David Kauchak
cs201
Spring 2014
public static int
partition(
double
[] nums,
int
start,
int
end){int
lessThanIndex = start-1;
for
(
int
i = start; i < end; i++ ){if
( nums[i] <= nums[end] ){lessThanIndex++;
swap(nums, lessThanIndex, i);
}
}
swap(nums, lessThanIndex+1, end);
return
lessThanIndex+1;
}
what does this method do?
n
u
m
s
[
e
n
d
]
i
s
c
a
l
l
e
d
t
h
e
p
i
v
o
t
Partitions the elements nums[start…end-1] in to two sets,
those
≤ pivot
and those > pivot
Operates in place
Final result:
nums
start
pivot
end
≤ pivot
> pivot
public static int
partition(
double
[] nums,
int
start,
int
end){int
lessThanIndex = start-1;
for
(
int
i = start; i < end; i++ ){if
( nums[i] <= nums[end] ){lessThanIndex++;
swap(nums, lessThanIndex, i);
}
}
swap(nums, lessThanIndex+1, end);
return
lessThanIndex+1;
}
… 5 7 1 2 8 4 3 6 …
public static int
partition(
double
[] nums,
int
start,
int
end){int
lessThanIndex = start-1;
for
(
int
i = start; i < end; i++ ){if
( nums[i] <= nums[end] ){lessThanIndex++;
swap(nums, lessThanIndex, i);
}
}
swap(nums, lessThanIndex+1, end);
return
lessThanIndex+1;
}
l
e
s
s
T
h
a
n
I
n
d
e
x
… 5 7 1 2 8 4 3 6 …
s
t
a
r
t
e
n
d
public static int
partition(
double
[] nums,
int
start,
int
end){int
lessThanIndex = start-1;
for
(
int
i = start; i < end; i++ ){if
( nums[i] <= nums[end] ){lessThanIndex++;
swap(nums, lessThanIndex, i);
}
}
swap(nums, lessThanIndex+1, end);
return
lessThanIndex+1;
}
l
e
s
s
T
h
a
n
I
n
d
e
x
… 5 7 1 2 8 4 3 6 …
s
t
a
r
t
e
n
d
public static int
partition(
double
[] nums,
int
start,
int
end){int
lessThanIndex = start-1;
for
(
int
i = start; i < end; i++ ){if
( nums[i] <= nums[end] ){lessThanIndex++;
swap(nums, lessThanIndex, i);
}
}
swap(nums, lessThanIndex+1, end);
return
lessThanIndex+1;
}
l
e
s
s
T
h
a
n
I
n
d
e
x
… 5 7 1 2 8 4 3 6 …
s
t
a
r
t
e
n
d
public static int
partition(
double
[] nums,
int
start,
int
end){int
lessThanIndex = start-1;
for
(
int
i = start; i < end; i++ ){if
( nums[i] <= nums[end] ){lessThanIndex++;
swap(nums, lessThanIndex, i);
}
}
swap(nums, lessThanIndex+1, end);
return
lessThanIndex+1;
}
l
e
s
s
T
h
a
n
I
n
d
e
x
… 5 7 1 2 8 4 3 6 …
s
t
a
r
t
e
n
d
public static int
partition(
double
[] nums,
int
start,
int
end){int
lessThanIndex = start-1;
for
(
int
i = start; i < end; i++ ){if
( nums[i] <= nums[end] ){lessThanIndex++;
swap(nums, lessThanIndex, i);
}
}
swap(nums, lessThanIndex+1, end);
return
lessThanIndex+1;
}
l
e
s
s
T
h
a
n
I
n
d
e
x
…
5
7 1 2 8 4 3 6 …
s
t
a
r
t
e
n
d
public static int
partition(
double
[] nums,
int
start,
int
end){int
lessThanIndex = start-1;
for
(
int
i = start; i < end; i++ ){if
( nums[i] <= nums[end] ){lessThanIndex++;
swap(nums, lessThanIndex, i);
}
}
swap(nums, lessThanIndex+1, end);
return
lessThanIndex+1;
}
l
e
s
s
T
h
a
n
I
n
d
e
x
… 5 7 1 2 8 4 3 6 …
s
t
a
r
t
e
n
d
public static int
partition(
double
[] nums,
int
start,
int
end){int
lessThanIndex = start-1;
for
(
int
i = start; i < end; i++ ){if
( nums[i] <= nums[end] ){lessThanIndex++;
swap(nums, lessThanIndex, i);
}
}
swap(nums, lessThanIndex+1, end);
return
lessThanIndex+1;
}
l
e
s
s
T
h
a
n
I
n
d
e
x
… 5 7 1 2 8 4 3 6 …
s
t
a
r
t
e
n
d
public static int
partition(
double
[] nums,
int
start,
int
end){int
lessThanIndex = start-1;
for
(
int
i = start; i < end; i++ ){if
( nums[i] <= nums[end] ){lessThanIndex++;
swap(nums, lessThanIndex, i);
}
}
swap(nums, lessThanIndex+1, end);
return
lessThanIndex+1;
}
l
e
s
s
T
h
a
n
I
n
d
e
x
… 5 7 1 2 8 4 3 6 …
s
t
a
r
t
e
n
d
public static int
partition(
double
[] nums,
int
start,
int
end){int
lessThanIndex = start-1;
for
(
int
i = start; i < end; i++ ){if
( nums[i] <= nums[end] ){lessThanIndex++;
swap(nums, lessThanIndex, i);
}
}
swap(nums, lessThanIndex+1, end);
return
lessThanIndex+1;
}
l
e
s
s
T
h
a
n
I
n
d
e
x
… 5
1 7
2 8 4 3 6 …
s
t
a
r
t
e
n
d
public static int
partition(
double
[] nums,
int
start,
int
end){int
lessThanIndex = start-1;
for
(
int
i = start; i < end; i++ ){if
( nums[i] <= nums[end] ){lessThanIndex++;
swap(nums, lessThanIndex, i);
}
}
swap(nums, lessThanIndex+1, end);
return
lessThanIndex+1;
}
l
e
s
s
T
h
a
n
I
n
d
e
x
… 5 1 7 2 8 4 3 6 …
s
t
a
r
t
e
n
d
public static int
partition(
double
[] nums,
int
start,
int
end){int
lessThanIndex = start-1;
for
(
int
i = start; i < end; i++ ){if
( nums[i] <= nums[end] ){lessThanIndex++;
swap(nums, lessThanIndex, i);
}
}
swap(nums, lessThanIndex+1, end);
return
lessThanIndex+1;
}
l
e
s
s
T
h
a
n
I
n
d
e
x
… 5 1 7 2 8 4 3 6 …
s
t
a
r
t
e
n
d
public static int
partition(
double
[] nums,
int
start,
int
end){int
lessThanIndex = start-1;
for
(
int
i = start; i < end; i++ ){if
( nums[i] <= nums[end] ){lessThanIndex++;
swap(nums, lessThanIndex, i);
}
}
swap(nums, lessThanIndex+1, end);
return
lessThanIndex+1;
}
l
e
s
s
T
h
a
n
I
n
d
e
x
… 5 1
2 7
8 4 3 6 …
s
t
a
r
t
e
n
d
public static int
partition(
double
[] nums,
int
start,
int
end){int
lessThanIndex = start-1;
for
(
int
i = start; i < end; i++ ){if
( nums[i] <= nums[end] ){lessThanIndex++;
swap(nums, lessThanIndex, i);
}
}
swap(nums, lessThanIndex+1, end);
return
lessThanIndex+1;
}
l
e
s
s
T
h
a
n
I
n
d
e
x
… 5 1 2 7 8 4 3 6 …
s
t
a
r
t
e
n
d
public static int
partition(
double
[] nums,
int
start,
int
end){int
lessThanIndex = start-1;
for
(
int
i = start; i < end; i++ ){if
( nums[i] <= nums[end] ){lessThanIndex++;
swap(nums, lessThanIndex, i);
}
}
swap(nums, lessThanIndex+1, end);
return
lessThanIndex+1;
}
l
e
s
s
T
h
a
n
I
n
d
e
x
… 5 1 2 7 8 4 3 6 …
s
t
a
r
t
e
n
d
public static int
partition(
double
[] nums,
int
start,
int
end){int
lessThanIndex = start-1;
for
(
int
i = start; i < end; i++ ){if
( nums[i] <= nums[end] ){lessThanIndex++;
swap(nums, lessThanIndex, i);
}
}
swap(nums, lessThanIndex+1, end);
return
lessThanIndex+1;
}
l
e
s
s
T
h
a
n
I
n
d
e
x
… 5 1 2 7 8 4 3 6 …
s
t
a
r
t
e
n
d
What’s happening?
l
e
s
s
T
h
a
n
I
n
d
e
x
… 5 1 2 7 8 4 3 6 …
s
t
a
r
t
e
n
d
≤ pivot
> pivot
unprocessed
l
e
s
s
T
h
a
n
I
n
d
e
x
… 5 1 2 7 8 4 3 6 …
s
t
a
r
t
e
n
d
public static int
partition(
double
[] nums,
int
start,
int
end){int
lessThanIndex = start-1;
for
(
int
i = start; i < end; i++ ){if
( nums[i] <= nums[end] ){lessThanIndex++;
swap(nums, lessThanIndex, i);
}
}
swap(nums, lessThanIndex+1, end);
return
lessThanIndex+1;
}
l
e
s
s
T
h
a
n
I
n
d
e
x
… 5 1 2
4
8
7
3 6 …
s
t
a
r
t
e
n
d
public static int
partition(
double
[] nums,
int
start,
int
end){int
lessThanIndex = start-1;
for
(
int
i = start; i < end; i++ ){if
( nums[i] <= nums[end] ){lessThanIndex++;
swap(nums, lessThanIndex, i);
}
}
swap(nums, lessThanIndex+1, end);
return
lessThanIndex+1;
}
l
e
s
s
T
h
a
n
I
n
d
e
x
… 5 1 2 4
3
7
8
6 …
s
t
a
r
t
e
n
d
public static int
partition(
double
[] nums,
int
start,
int
end){int
lessThanIndex = start-1;
for
(
int
i = start; i < end; i++ ){if
( nums[i] <= nums[end] ){lessThanIndex++;
swap(nums, lessThanIndex, i);
}
}
swap(nums, lessThanIndex+1, end);
return
lessThanIndex+1;
}
l
e
s
s
T
h
a
n
I
n
d
e
x
… 5 1 2 4 3
6
8
7
…
s
t
a
r
t
e
n
d
public static int
partition(
double
[] nums,
int
start,
int
end){int
lessThanIndex = start-1;
for
(
int
i = start; i < end; i++ ){if
( nums[i] <= nums[end] ){lessThanIndex++;
swap(nums, lessThanIndex, i);
}
}
swap(nums, lessThanIndex+1, end);
return
lessThanIndex+1;
}
P
a
r
t
i
t
i
o
n
r
u
n
n
i
n
g
t
i
m
e
?
O
(
n
)
public static int
partition(
double
[] nums,
int
start,
int
end){int
lessThanIndex = start-1;
for
(
int
i = start; i < end; i++ ){if
( nums[i] <= nums[end] ){lessThanIndex++;
swap(nums, lessThanIndex, i);
}
}
swap(nums, lessThanIndex+1, end);
return
lessThanIndex+1;
}
Q
u
i
c
k
s
o
r
t
public static int
partition(
double
[] nums,
int
start,
int
end){int
lessThanIndex = start-1;
for
(
int
i = start; i < end; i++ ){if
( nums[i] <= nums[end] ){lessThanIndex++;
swap(nums, lessThanIndex, i);
}
}
swap(nums, lessThanIndex+1, end);
return
lessThanIndex+1;
}
How can we use this method to sort nums?
Q
u
i
c
k
s
o
r
t
private static void
quicksortHelper(
double
[] nums,
int
start,
int
end){if
( start < end ){int
partition =
partition(nums, start, end);
quicksortHelper(nums, start, partition-1);
quicksortHelper(nums, partition+1, end);
}
}
public static int
partition(
double
[] nums,
int
start,
int
end){int
lessThanIndex = start-1;
for
(
int
i = start; i < end; i++ ){if
( nums[i] <= nums[end] ){lessThanIndex++;
swap(nums, lessThanIndex, i);
}
}
swap(nums, lessThanIndex+1, end);
return
lessThanIndex+1;
}
8 5 1 3 6 2 7 4
private static void
quicksortHelper(
double
[] nums,
int
start,
int
end){if
( start < end ){int
partition =
partition(nums, start, end);
quicksortHelper(nums, start, partition-1);
quicksortHelper(nums, partition+1, end);
}
}
private static void
quicksortHelper(
double
[] nums,
int
start,
int
end){if
( start < end ){int
partition =
partition(nums, start, end);
quicksortHelper(nums, start, partition-1);
quicksortHelper(nums, partition+1, end);
}
}
8 5 1 3 6 2 7 4
private static void
quicksortHelper(
double
[] nums,
int
start,
int
end){if
( start < end ){int
partition =
partition(nums, start, end);
quicksortHelper(nums, start, partition-1);
quicksortHelper(nums, partition+1, end);
}
}
1 3 2 4 6 8 7 5
private static void
quicksortHelper(
double
[] nums,
int
start,
int
end){if
( start < end ){int
partition =
partition(nums, start, end);
quicksortHelper(nums, start, partition-1);
quicksortHelper(nums, partition+1, end);
}
}
1 3 2 4 6 8 7 5
private static void
quicksortHelper(
double
[] nums,
int
start,
int
end){if
( start < end ){int
partition =
partition(nums, start, end);
quicksortHelper(nums, start, partition-1);
quicksortHelper(nums, partition+1, end);
}
}
1 3 2 4 6 8 7 5
private static void
quicksortHelper(
double
[] nums,
int
start,
int
end){if
( start < end ){int
partition =
partition(nums, start, end);
quicksortHelper(nums, start, partition-1);
quicksortHelper(nums, partition+1, end);
}
}
1 2 3 4 6 8 7 5
private static void
quicksortHelper(
double
[] nums,
int
start,
int
end){if
( start < end ){int
partition =
partition(nums, start, end);
quicksortHelper(nums, start, partition-1);
quicksortHelper(nums, partition+1, end);
}
}
1 2 3 4 6 8 7 5
private static void
quicksortHelper(
double
[] nums,
int
start,
int
end){if
( start < end ){int
partition =
partition(nums, start, end);
quicksortHelper(nums, start, partition-1);
quicksortHelper(nums, partition+1, end);
}
}
1 2 3 4 6 8 7 5
1 2 3 4 6 8 7 5
private static void
quicksortHelper(
double
[] nums,
int
start,
int
end){if
( start < end ){int
partition =
partition(nums, start, end);
quicksortHelper(nums, start, partition-1);
quicksortHelper(nums, partition+1, end);
}
}
1 2 3 4 6 8 7 5
private static void
quicksortHelper(
double
[] nums,
int
start,
int
end){if
( start < end ){int
partition =
partition(nums, start, end);
quicksortHelper(nums, start, partition-1);
quicksortHelper(nums, partition+1, end);
}
}
1 2 3 4 5 8 7 6
What happens here?
private static void
quicksortHelper(
double
[] nums,
int
start,
int
end){if
( start < end ){int
partition =
partition(nums, start, end);
quicksortHelper(nums, start, partition-1);
quicksortHelper(nums, partition+1, end);
}
}
1 2 3 4 5 8 7 6
private static void
quicksortHelper(
double
[] nums,
int
start,
int
end){if
( start < end ){int
partition =
partition(nums, start, end);
quicksortHelper(nums, start, partition-1);
quicksortHelper(nums, partition+1, end);
}
}
1 2 3 4 5 8 7 6
private static void
quicksortHelper(
double
[] nums,
int
start,
int
end){if
( start < end ){int
partition =
partition(nums, start, end);
quicksortHelper(nums, start, partition-1);
quicksortHelper(nums, partition+1, end);
}
}
1 2 3 4 5 6 7 8
private static void
quicksortHelper(
double
[] nums,
int
start,
int
end){if
( start < end ){int
partition =
partition(nums, start, end);
quicksortHelper(nums, start, partition-1);
quicksortHelper(nums, partition+1, end);
}
}
1 2 3 4 5 6 7 8
private static void
quicksortHelper(
double
[] nums,
int
start,
int
end){if
( start < end ){int
partition =
partition(nums, start, end);
quicksortHelper(nums, start, partition-1);
quicksortHelper(nums, partition+1, end);
}
}
R
u
n
n
i
n
g
t
i
m
e
o
f
Q
u
i
c
k
s
o
r
t
?
Worst case?
Each call to Partition splits the array into an empty
array and n-1 array
Q
u
i
c
k
s
o
r
t
:
W
o
r
s
t
c
a
s
e
r
u
n
n
i
n
g
t
i
m
e
When does this happen?
sorted
reverse sorted
near sorted/reverse sorted
n-1 + n-2 + n-3 + … + 1 =
O(n
2
)
Q
u
i
c
k
s
o
r
t
b
e
s
t
c
a
s
e
?
Each call to Partition splits the array into two equal parts
How much work is done at each “level”,
i.e. running time of a level?
O(n)
Q
u
i
c
k
s
o
r
t
b
e
s
t
c
a
s
e
?
Each call to Partition splits the array into two equal parts
How many levels are there?
Similar to binary search, each call to Partition will throw away
half the data until we’re down to one element: log
2
n levels
Q
u
i
c
k
s
o
r
t
b
e
s
t
c
a
s
e
?
Each call to Partition splits the array into two equal parts
Overall runtime?
O(n log n)
Q
u
i
c
k
s
o
r
t
A
v
e
r
a
g
e
c
a
s
e
?
Two intuitions
As long as the Partition procedure always splits the array
into some constant ratio between the left and the right, say
L-to-R, e.g. 9-to-1, then we maintain
O(n log n)
As long as we only have a constant number of “bad”
partitions intermixed with a “good partition” then we
maintain
O(n log n)
H
o
w
c
a
n
w
e
a
v
o
i
d
t
h
e
w
o
r
s
t
c
a
s
e
?
Inject randomness into the data
private static void
randomizedPartition(
double
[] nums,
int
start,
int
end){int
i =
random
(start, end);
swap
(nums, i, end);
return
partition =
partition(nums, start, end);
}
Randomized quicksort is average case
O(n log n)
W
h
a
t
i
s
t
h
e
w
o
s
t
c
a
s
e
r
u
n
n
i
n
g
t
i
m
e
o
f
r
a
n
d
o
m
i
z
e
d
Q
u
i
c
k
s
o
r
t
?
O(n
2
)
We could still get very unlucky and
pick “bad” partitions at every step
Quicksort is a widely used sorting algorithm that operates by partitioning an array into smaller subarrays. The `public.static.int.partition` method plays a crucial role in Quicksort by selecting a pivot element and rearranging elements around it based on their values. This process creates a split between elements less than the pivot and those greater than it, leading to a sorted array. Visualization and explanation of the partitioning step with examples like `5, 7, 1, 2, 8, 4, 3, 6` help in grasping the essence of Quicksort.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Quicksort David Kauchak cs201 Spring 2014
public static int partition(double[] nums, int start, int end){ int lessThanIndex = start-1; for( int i = start; i < end; i++ ){ if( nums[i] <= nums[end] ){ lessThanIndex++; swap(nums, lessThanIndex, i); } } swap(nums, lessThanIndex+1, end); return lessThanIndex+1; } what does this method do?
public static int partition(double[] nums, int start, int end){ int lessThanIndex = start-1; for( int i = start; i < end; i++ ){ if( nums[i] <= nums[end] ){ lessThanIndex++; swap(nums, lessThanIndex, i); } } swap(nums, lessThanIndex+1, end); return lessThanIndex+1; } nums[end] is called the pivot Partitions the elements nums[start end-1] in to two sets, those pivot and those > pivot Operates in place Final result: start pivot end nums > pivot pivot
5 7 1 2 8 4 3 6 start end public static int partition(double[] nums, int start, int end){ int lessThanIndex = start-1; for( int i = start; i < end; i++ ){ if( nums[i] <= nums[end] ){ lessThanIndex++; swap(nums, lessThanIndex, i); } } swap(nums, lessThanIndex+1, end); return lessThanIndex+1; }
lessThanIndex 5 7 1 2 8 4 3 6 start end public static int partition(double[] nums, int start, int end){ int lessThanIndex = start-1; for( int i = start; i < end; i++ ){ if( nums[i] <= nums[end] ){ lessThanIndex++; swap(nums, lessThanIndex, i); } } swap(nums, lessThanIndex+1, end); return lessThanIndex+1; }
lessThanIndex i 5 7 1 2 8 4 3 6 start end public static int partition(double[] nums, int start, int end){ int lessThanIndex = start-1; for( int i = start; i < end; i++ ){ if( nums[i] <= nums[end] ){ lessThanIndex++; swap(nums, lessThanIndex, i); } } swap(nums, lessThanIndex+1, end); return lessThanIndex+1; }
lessThanIndex i 5 7 1 2 8 4 3 6 start end public static int partition(double[] nums, int start, int end){ int lessThanIndex = start-1; for( int i = start; i < end; i++ ){ if( nums[i] <= nums[end] ){ lessThanIndex++; swap(nums, lessThanIndex, i); } } swap(nums, lessThanIndex+1, end); return lessThanIndex+1; }
lessThanIndex i 5 7 1 2 8 4 3 6 start end public static int partition(double[] nums, int start, int end){ int lessThanIndex = start-1; for( int i = start; i < end; i++ ){ if( nums[i] <= nums[end] ){ lessThanIndex++; swap(nums, lessThanIndex, i); } } swap(nums, lessThanIndex+1, end); return lessThanIndex+1; }
lessThanIndex i 5 7 1 2 8 4 3 6 start end public static int partition(double[] nums, int start, int end){ int lessThanIndex = start-1; for( int i = start; i < end; i++ ){ if( nums[i] <= nums[end] ){ lessThanIndex++; swap(nums, lessThanIndex, i); } } swap(nums, lessThanIndex+1, end); return lessThanIndex+1; }
lessThanIndex i 5 7 1 2 8 4 3 6 start end public static int partition(double[] nums, int start, int end){ int lessThanIndex = start-1; for( int i = start; i < end; i++ ){ if( nums[i] <= nums[end] ){ lessThanIndex++; swap(nums, lessThanIndex, i); } } swap(nums, lessThanIndex+1, end); return lessThanIndex+1; }
lessThanIndex i 5 7 1 2 8 4 3 6 start end public static int partition(double[] nums, int start, int end){ int lessThanIndex = start-1; for( int i = start; i < end; i++ ){ if( nums[i] <= nums[end] ){ lessThanIndex++; swap(nums, lessThanIndex, i); } } swap(nums, lessThanIndex+1, end); return lessThanIndex+1; }
lessThanIndex i 5 7 1 2 8 4 3 6 start end public static int partition(double[] nums, int start, int end){ int lessThanIndex = start-1; for( int i = start; i < end; i++ ){ if( nums[i] <= nums[end] ){ lessThanIndex++; swap(nums, lessThanIndex, i); } } swap(nums, lessThanIndex+1, end); return lessThanIndex+1; }
lessThanIndex i 5 1 7 2 8 4 3 6 start end public static int partition(double[] nums, int start, int end){ int lessThanIndex = start-1; for( int i = start; i < end; i++ ){ if( nums[i] <= nums[end] ){ lessThanIndex++; swap(nums, lessThanIndex, i); } } swap(nums, lessThanIndex+1, end); return lessThanIndex+1; }
lessThanIndex i 5 1 7 2 8 4 3 6 start end public static int partition(double[] nums, int start, int end){ int lessThanIndex = start-1; for( int i = start; i < end; i++ ){ if( nums[i] <= nums[end] ){ lessThanIndex++; swap(nums, lessThanIndex, i); } } swap(nums, lessThanIndex+1, end); return lessThanIndex+1; }
lessThanIndex i 5 1 7 2 8 4 3 6 start end public static int partition(double[] nums, int start, int end){ int lessThanIndex = start-1; for( int i = start; i < end; i++ ){ if( nums[i] <= nums[end] ){ lessThanIndex++; swap(nums, lessThanIndex, i); } } swap(nums, lessThanIndex+1, end); return lessThanIndex+1; }
lessThanIndex i 5 1 2 7 8 4 3 6 start end public static int partition(double[] nums, int start, int end){ int lessThanIndex = start-1; for( int i = start; i < end; i++ ){ if( nums[i] <= nums[end] ){ lessThanIndex++; swap(nums, lessThanIndex, i); } } swap(nums, lessThanIndex+1, end); return lessThanIndex+1; }
lessThanIndex i 5 1 2 7 8 4 3 6 start end public static int partition(double[] nums, int start, int end){ int lessThanIndex = start-1; for( int i = start; i < end; i++ ){ if( nums[i] <= nums[end] ){ lessThanIndex++; swap(nums, lessThanIndex, i); } } swap(nums, lessThanIndex+1, end); return lessThanIndex+1; }
lessThanIndex i 5 1 2 7 8 4 3 6 start end public static int partition(double[] nums, int start, int end){ int lessThanIndex = start-1; for( int i = start; i < end; i++ ){ if( nums[i] <= nums[end] ){ lessThanIndex++; swap(nums, lessThanIndex, i); } } swap(nums, lessThanIndex+1, end); return lessThanIndex+1; }
lessThanIndex i 5 1 2 7 8 4 3 6 start end What s happening?
lessThanIndex i 5 1 2 7 8 4 3 6 start end > pivot unprocessed pivot
lessThanIndex i 5 1 2 7 8 4 3 6 start end public static int partition(double[] nums, int start, int end){ int lessThanIndex = start-1; for( int i = start; i < end; i++ ){ if( nums[i] <= nums[end] ){ lessThanIndex++; swap(nums, lessThanIndex, i); } } swap(nums, lessThanIndex+1, end); return lessThanIndex+1; }
lessThanIndex i 5 1 2 4 8 7 3 6 start end public static int partition(double[] nums, int start, int end){ int lessThanIndex = start-1; for( int i = start; i < end; i++ ){ if( nums[i] <= nums[end] ){ lessThanIndex++; swap(nums, lessThanIndex, i); } } swap(nums, lessThanIndex+1, end); return lessThanIndex+1; }
lessThanIndex i 5 1 2 4 3 7 8 6 start end public static int partition(double[] nums, int start, int end){ int lessThanIndex = start-1; for( int i = start; i < end; i++ ){ if( nums[i] <= nums[end] ){ lessThanIndex++; swap(nums, lessThanIndex, i); } } swap(nums, lessThanIndex+1, end); return lessThanIndex+1; }
lessThanIndex i 5 1 2 4 3 6 8 7 start end public static int partition(double[] nums, int start, int end){ int lessThanIndex = start-1; for( int i = start; i < end; i++ ){ if( nums[i] <= nums[end] ){ lessThanIndex++; swap(nums, lessThanIndex, i); } } swap(nums, lessThanIndex+1, end); return lessThanIndex+1; }
Partition running time? O(n) public static int partition(double[] nums, int start, int end){ int lessThanIndex = start-1; for( int i = start; i < end; i++ ){ if( nums[i] <= nums[end] ){ lessThanIndex++; swap(nums, lessThanIndex, i); } } swap(nums, lessThanIndex+1, end); return lessThanIndex+1; }
Quicksort How can we use this method to sort nums? public static int partition(double[] nums, int start, int end){ int lessThanIndex = start-1; for( int i = start; i < end; i++ ){ if( nums[i] <= nums[end] ){ lessThanIndex++; swap(nums, lessThanIndex, i); } } swap(nums, lessThanIndex+1, end); return lessThanIndex+1; }
Quicksort private static void quicksortHelper(double[] nums, int start, int end){ if( start < end ){ int partition = partition(nums, start, end); quicksortHelper(nums, start, partition-1); quicksortHelper(nums, partition+1, end); } } public static int partition(double[] nums, int start, int end){ int lessThanIndex = start-1; for( int i = start; i < end; i++ ){ if( nums[i] <= nums[end] ){ lessThanIndex++; swap(nums, lessThanIndex, i); } } swap(nums, lessThanIndex+1, end); return lessThanIndex+1; }
8 5 1 3 6 2 7 4 private static void quicksortHelper(double[] nums, int start, int end){ if( start < end ){ int partition = partition(nums, start, end); quicksortHelper(nums, start, partition-1); quicksortHelper(nums, partition+1, end); } }
8 5 1 3 6 2 7 4 private static void quicksortHelper(double[] nums, int start, int end){ if( start < end ){ int partition = partition(nums, start, end); quicksortHelper(nums, start, partition-1); quicksortHelper(nums, partition+1, end); } }
1 3 2 4 6 8 7 5 private static void quicksortHelper(double[] nums, int start, int end){ if( start < end ){ int partition = partition(nums, start, end); quicksortHelper(nums, start, partition-1); quicksortHelper(nums, partition+1, end); } }
1 3 2 4 6 8 7 5 private static void quicksortHelper(double[] nums, int start, int end){ if( start < end ){ int partition = partition(nums, start, end); quicksortHelper(nums, start, partition-1); quicksortHelper(nums, partition+1, end); } }
1 3 2 4 6 8 7 5 private static void quicksortHelper(double[] nums, int start, int end){ if( start < end ){ int partition = partition(nums, start, end); quicksortHelper(nums, start, partition-1); quicksortHelper(nums, partition+1, end); } }
1 2 3 4 6 8 7 5 private static void quicksortHelper(double[] nums, int start, int end){ if( start < end ){ int partition = partition(nums, start, end); quicksortHelper(nums, start, partition-1); quicksortHelper(nums, partition+1, end); } }
1 2 3 4 6 8 7 5 private static void quicksortHelper(double[] nums, int start, int end){ if( start < end ){ int partition = partition(nums, start, end); quicksortHelper(nums, start, partition-1); quicksortHelper(nums, partition+1, end); } }
1 2 3 4 6 8 7 5 private static void quicksortHelper(double[] nums, int start, int end){ if( start < end ){ int partition = partition(nums, start, end); quicksortHelper(nums, start, partition-1); quicksortHelper(nums, partition+1, end); } }
1 2 3 4 6 8 7 5 private static void quicksortHelper(double[] nums, int start, int end){ if( start < end ){ int partition = partition(nums, start, end); quicksortHelper(nums, start, partition-1); quicksortHelper(nums, partition+1, end); } }
1 2 3 4 6 8 7 5 private static void quicksortHelper(double[] nums, int start, int end){ if( start < end ){ int partition = partition(nums, start, end); quicksortHelper(nums, start, partition-1); quicksortHelper(nums, partition+1, end); } }
1 2 3 4 5 8 7 6 What happens here? private static void quicksortHelper(double[] nums, int start, int end){ if( start < end ){ int partition = partition(nums, start, end); quicksortHelper(nums, start, partition-1); quicksortHelper(nums, partition+1, end); } }
1 2 3 4 5 8 7 6 private static void quicksortHelper(double[] nums, int start, int end){ if( start < end ){ int partition = partition(nums, start, end); quicksortHelper(nums, start, partition-1); quicksortHelper(nums, partition+1, end); } }
1 2 3 4 5 8 7 6 private static void quicksortHelper(double[] nums, int start, int end){ if( start < end ){ int partition = partition(nums, start, end); quicksortHelper(nums, start, partition-1); quicksortHelper(nums, partition+1, end); } }
1 2 3 4 5 6 7 8 private static void quicksortHelper(double[] nums, int start, int end){ if( start < end ){ int partition = partition(nums, start, end); quicksortHelper(nums, start, partition-1); quicksortHelper(nums, partition+1, end); } }
1 2 3 4 5 6 7 8 private static void quicksortHelper(double[] nums, int start, int end){ if( start < end ){ int partition = partition(nums, start, end); quicksortHelper(nums, start, partition-1); quicksortHelper(nums, partition+1, end); } }
Running time of Quicksort? Worst case? Each call to Partition splits the array into an empty array and n-1 array
Quicksort: Worst case running time n-1 + n-2 + n-3 + + 1 = O(n2) When does this happen? sorted reverse sorted near sorted/reverse sorted
Quicksort best case? Each call to Partition splits the array into two equal parts How much work is done at each level , i.e. running time of a level? O(n)
Quicksort best case? Each call to Partition splits the array into two equal parts How many levels are there? Similar to binary search, each call to Partition will throw away half the data until we re down to one element: log2 n levels
Quicksort best case? Each call to Partition splits the array into two equal parts Overall runtime? O(n log n)
Quicksort Average case? Two intuitions As long as the Partition procedure always splits the array into some constant ratio between the left and the right, say L-to-R, e.g. 9-to-1, then we maintain O(n log n) As long as we only have a constant number of bad partitions intermixed with a good partition then we maintain O(n log n)
How can we avoid the worst case? Inject randomness into the data private static void randomizedPartition(double[] nums, int start, int end){ int i = random(start, end); swap(nums, i, end); return partition = partition(nums, start, end); } Randomized quicksort is average case O(n log n)
What is the wost case running time of randomized Quicksort? O(n2) We could still get very unlucky and pick bad partitions at every step
