Randomized QuickSort

Randomized QuickSort is an efficient sort algorithm requiring only $\Theta(n\log n)$ expected time on any input.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function RANDOMIZED-QUICKSORT(Array, low, high)
if low < high then
partition := RANDOMIZED-PARTITION(Array, low, high)
RANDOMIZED-QUICKSORT(Array, low, partition - 1)
RANDOMIZED-QUICKSORT(Array, partition + 1, high)

function RANDOMIZED-PARTITION(Array, low, high)
pivotIndex := RANDOMIZED-CHOOSEPIVOT(Array, low, high)
pivotValue := Array[pivotIndex]
swap Array[high] and Array[pivotIndex]
storeIndex := low
for i from low to high do
if Array[i] < pivotValue then
swap Array[i] and Array[storeIndex]
storeIndex := storeIndex + 1
swap Array[high] and Array[storeIndex]
return storeIndex

Randomized Select

Randomized Select is an efficient algorithm to find $i$th smallest element of Array[low…high] with only linear expected time on any input.

1
2
3
4
5
6
7
8
9
10
11
function RANDOMIZED-SELECT(Array, low, high, i)
if low = high then
return Array[low]
partition := RANDOMIZED-PARTITION(Array, low, high)
rank := partition - low + 1
if i = rank then
return Array[partition]
else if i < rank then
return RANDOMIZED-SELECT(Array, low, partition - 1, i)
else
return RANDOMIZED-SELECT(Array, partition + 1, high, i - rank)
Read More
  • page 1 of 1
Author's picture

Haiyang Shi

A Ph.D. candidate in Computer Science and Engineering at The Ohio State University (OSU).


Graduate Research Assistant


Columbus, OH