CSCE 411 Lecture 26

Lecture Slides

« previous | Monday, October 29, 2012 | next »

Deterministic Quicksort

def quicksort arr, p, r
  if p < r
    q = partition(arr, p,r)  #rearrange a[p..r] in place
    quicksort(arr, p,q-1)
    quicksort(arr, p+1,r)
  end
end

def partition arr, p, r
  x = arr[r]  #select rightmost element as pivot
  i = p-1
  p.upto(r-1) do |j|
    if arr[j] <= x
      i += 1
      arr[i], arr[j] = arr[j], arr[i]
    end
  end
  arr[i+1], arr[r] = arr[r], arr[i+1]
  i+1
end

quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) = quicksort (filter xs (< x)) ++ [x] ++ quicksort (filter (>= x))

partition selects a pivot element (Ruby uses last element, Haskell uses first element) and rearranges all items around the pivot (less on left, greater on right)

Analysis

Worst-case is $T(n)=T(n-1)+\Theta (n)=\Theta (n^{2})$

Better Deterministic Quicksort

find the median of all array elements in linear time:

def median arr
  do_something if arr.length < 5
  median arr.split(5).map {|subarr| subarr.median_of_5} # finding median of 5 elements requires 6 comparisons
end

Analysis

Worst-case is now $T(n)=\Theta (n\log {n})$

Best Randomized Quicksort

def randomized_partition arr, p, r
  i = (p..r).to_a.sample  # choose a random index between P and R
  arr[i], arr[r] = arr[r], arr[i]
  partition arr, p, r
end

Analysis

Let rv $X$ count the number of comparisons made in all calls to randomized_partition.

Let $z_{i}$ denote the i^th smallest element of $A$, so $A$ sorted is $\{z_{1},z_{2},\ldots ,z_{n}\}$

Let $Z_{ij}=\{z_{i},\ldots ,z_{j}\}$ be the set of elements between and including $z_{i}$ and $z_{j}$

Indicator rv $X_{ij}=I{z_{i}{\mbox{ is compared to }}z_{j}}$ indicates whether $z_{i}$ is compared to $z_{j}$, i.e. if either $z_{i}$ or $z_{j}$ is seleted as a pivot element.

Since each pair of elemens is compared at most once, number of comparisons is

$X=\sum _{i=1}^{n-1}\sum _{j=i+1}^{n}X_{ij}$

Therefore, expected number of comparisons is

$E[X]=\sum _{i=1}^{n-1}\sum _{j=i+1}^{n}E[X_{ij}]=\sum _{i=1}^{n-1}\sum _{j=i+1}^{n}Pr[z_{i}{\mbox{ is compared to }}z_{j}]$

When do we compare $z_{i}$ to $z_{j}$

if $z_{i}<x<z_{j}$, then they will end up in separate partitions and never be compared.

Therefore, $z_{i}$ and $z_{j}$ will be compared iff the first element of $Z_{ij}$ to be picked as the pivot element is contained in $\{z_{i},z_{j}\}$.

$Pr[z_{i}{\mbox{ or }}z_{j}{\mbox{ is first pivot chosen from }}Z_{ij}]={\frac {2}{j-i+1}}$

Therefore, $E[X]=\ldots =O(n\log {n})$.