Notes for 9 April
COEN 251: Data Structures and Algorithms

Spring 1998

Algorithm for quicksort (from the textbook, p 154): 
QUICKSORT(A,p,r)
1  if p < r
2    then q <- PARTITION(A,p,r)
3         QUICKSORT(A,p,q)
4         QUICKSORT(A,q+1,r)

PARTITION(A,p,r)
1  x <- A[p]
2  i <- p - 1
3  j <- r + 1
4  while TRUE
5      do repeat j <- j - 1
6           until A[j] <= x
7         repeat i <- i + 1
8           until A[i] >= x
9         if i < j
10          then exchange A[i] <-> A[j]
11          else return j
Algorithm for randomized quicksort (from the textbook, p 162): 
RANDOMIZED_QUICKSORT(A,p,r)
1  if p < r
2    then q <- RANDOMIZED_PARTITION(A,p,r)
3         RANDOMIZED_QUICKSORT(A,p,q)
4         RANDOMIZED_QUICKSORT(A,q+1,r)

RANDOMIZED_PARTITION(A,p,r)
1  i <- RANDOM(p,q)
2  exchange A[p] <-> A[i]
3  return PARTITION(A,p,r)