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

I am a Ph.D. student in Computer Science and Engineering at The Ohio State University (OSU), advised by Dr. Xiaoyi Lu. My professional interests involve high-performance interconnects and protocols, erasure coding, and distributed systems. In my ongoing and recent projects, which are mainly developed in C++ and Java, I focus on implementing RDMA (Remote Direct Memory Access)-based communication protocols, optimizing I/O performance by exploiting RDMA for data transmission, enabling distributed systems to leverage heterogeneous hardware-optimized erasure coders in parallel, and designing tripartite graph based EC paradigm to gain better overlapping and parallelism on HPC clusters. In the meantime, I have participated in characterizing deep learning over big data stacks recently, and have understandings of deep learning training on distributed systems and modern data centers. Prior to graduate school, I worked as a Software Engineer at MiningLamp and Weibo, China. I finished my Bachelor’s degree in Tianjin University, China.


Graduate Research Associate


Columbus, OH