Quick sort
Does a clever split, a recursive solve and trivial combine
function Quicksort(A, low, high)
if low < high
p = Partition(A, low, high) //split
Quicksort (A, low, p-1) //recursive
Quicksort (A, p+1, high)
if low < high
p = Partition(A, low, high) //split
Quicksort (A, low, p-1) //recursive
Quicksort (A, p+1, high)
Lumoto's partition algo:
function Partition(A, low, high)
v = A[low]
m = low
i = low
//Initialisation
for i = (low + 1) to high
if A[i] < v
m++
swap(A[i], A[m])
swap(A[m], A[low])
return m
v = A[low]
m = low
i = low
//Initialisation
for i = (low + 1) to high
if A[i] < v
m++
swap(A[i], A[m])
swap(A[m], A[low])
return m
Precondition
1. A is an array
2. 0< = low < = high < = A.length
3. A has no duplicate
Post condition
1. A[m] = v //mid
1. A[m] = v //mid
2. low<= k <= m-1 , A[k] < v //lower box
3. m+1 < = k < = high , A[k] > v //upper box
Loop Invariances
1. A[low] = v
2. if low+1 <= k <= m, A[k] < v
3. if m+1 <= k <= i, A[k] > k
Loop Invariances
1. A[low] = v
2. if low+1 <= k <= m, A[k] < v
3. if m+1 <= k <= i, A[k] > k
"Quick sort assumes that left is already sorted"
1. Choose a pivot (first index)
2. Iterate from pivot up
3. If element is smaller than pivot, m++, swap element with element at counter m
4. i++, repeat 3
5. Stop only when i = high
5. Stop only when i = high
The idea is put all the smaller than pivot at the left, put all the bigger in the right.
Finally, put the median in the correct position
Correctness and Efficiency:
There are algorithms that are fast but sometimes incorrect.
Quicksort is n^2 depending on the situation.
This is due to the fact that Lumoto's algo will still partition even if the data structure is already sorted when the wrong pivot is chosen.
This is due to the fact that Lumoto's algo will still partition even if the data structure is already sorted when the wrong pivot is chosen.
A deterministic quicksort is
T(n-1) + T(1) +cn
T(n-1) -> Cost of quicksort on n-1 elements
T(1) -> Cost of Quicksort on 1 element
cn -> Cost of partition on n elements
T(n-1) -> Cost of quicksort on n-1 elements
T(1) -> Cost of Quicksort on 1 element
cn -> Cost of partition on n elements
//Partition takes n time
p = Partition(A, low, high) //cn time
Quicksort (A, low, p-1) // n-1
Quicksort (A, p+1, high) //1
Quicksort (A, low, p-1) // n-1
Quicksort (A, p+1, high) //1
The problem is that we always pick A[low] for a pivot so instead of doing that,
we can pick the median value.
Better quicksort,
Our time complexity will be 2T(n/2) + cn
T(n/2) -> Cost of Quicksort on n/2 high elements
t(n/2) - > Cost of quicksort on n/2 low elements
cn -> cost of partition of n elements
But for quick sort the worst is nlogn
t(n/2) - > Cost of quicksort on n/2 low elements
cn -> cost of partition of n elements
But for quick sort the worst is nlogn
Hoare's Partition algo
Unlike lumoto, Hoare's partition method is harder but is more efficient as it runs 3 times faster and does fewer sorts on average compared to Lumoto. Like Lumoto, it will be n^2 if the array is already sorted.
(Check if low< high)
1. Iterate from the left up
2. If larger or equal to pivot then break out of the loop with i at the index
3. Iterate from the right down
4. If smaller than pivot, break out of the loop with j at the index
5. If the two pointers (i>= j), return j
else
swap elements at i and j
6. After left side and right side is partitioned, swap the pivot with A[j] ,which is smaller than pivot
6. After left side and right side is partitioned, swap the pivot with A[j] ,which is smaller than pivot
7. Quick sort the lower half, and Quick sort the upper half
function Partition(A, low, high)
v = A[low]
i = low+1;
j = high;
while i < j
while (A[i] < v) and (i <= high) i++
while (A[j] > v) and (j >= low) j--
if (i<j) swap(A[i], A[j])
swap(A[j], A[low])
return j
function Partition(A, low, high)
v = A[low]
i = low+1;
j = high;
while i < j
while (A[i] < v) and (i <= high) i++
while (A[j] > v) and (j >= low) j--
if (i<j) swap(A[i], A[j])
swap(A[j], A[low])
return j
Pivot choices
Selecting Median
function Quicksort(A, low, high)
if low < high
mid = (low+ high) /2
p = Partition(A, mid, low, high) //split
Quicksort (A, low, p-1) //recursive
Quicksort (A, p+1, high)
This will allow the split to be 50:50
if low < high
mid = (low+ high) /2
p = Partition(A, mid, low, high) //split
Quicksort (A, low, p-1) //recursive
Quicksort (A, p+1, high)
This will allow the split to be 50:50
But,we don't need a 50:50 split for it to be nlogn
Because its always Cnlogn
Imagine a 90:10 Partition,
T(n) = T(n/10) + T(9n/10) + cn
Imagine a 90:10 Partition,
T(n) = T(n/10) + T(9n/10) + cn
Base case is 1 element,
If each time we split, we will reach 1 = n(9/10)^h where h is the total height
We use 9/10 because it have more elements, so it will spread the deepest
If each time we split, we will reach 1 = n(9/10)^h where h is the total height
We use 9/10 because it have more elements, so it will spread the deepest
then h = clog(2) n
At every level, we take n effort to partition each level,
the time complexity is then nlogn
At every level, we take n effort to partition each level,
the time complexity is then nlogn
Randomized quicksort
function RandomizedPartition(A, low, high)
r = Random(A, low, high) //median is randomised
swap(A[r], A[low])
return Partition(A, low, high)
r = Random(A, low, high) //median is randomised
swap(A[r], A[low])
return Partition(A, low, high)
Randomly sort an elements
Just swap a random element with the first element.
Just swap a random element with the first element.
Intuition: Random element should result in balance split on average
Paranoid Quicksort
Make sure that it will never satisfy the condition of 1:9 partition
Will continue to randomise until the low and high is not a pivot
Will continue to randomise until the low and high is not a pivot
Probability of picking a good pivot
8/10 (Pick the numbers 2-9)
Bad pivots would be 1 and 10
Problem: Duplicates
Quicksort will take longer when there is duplicates.
3 way partition + quicksort:
1. Cuts into 3
a. Less than v
b. Equal to V
c. Greater than V
2. If find a duplicate, increase partition
3. Else do the same as normal quick sort
Quick sort is unstable
Stable: Everything remains unsorted if the key is the same.
Unstable: The keys may be swapped even if they are the same
Quicksort is unstable because it just swaps the value without considering the original position.
- Insertion sort
- Bubble sort
- Quick sort
<Prev Next>
Stable
- Mergesort- Insertion sort
- Bubble sort
Unstable
- Selection sort (Arrays)- Quick sort
<Prev Next>