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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} count the number of comparisons made in all calls to randomized_partition.

Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle z_i} denote the i^th smallest element of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} , so Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle z_j} , i.e. if either Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle z_i} or Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle z_j} is seleted as a pivot element.

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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X = \sum_{i=1}^{n-1} \sum_{j=i+1}^n X_{ij}}

Therefore, expected number of comparisons is

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle z_i} to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle z_j}

if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle z_i < x < z_j} , then they will end up in separate partitions and never be compared.

Therefore, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle z_i} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle z_j} will be compared iff the first element of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Z_{ij}} to be picked as the pivot element is contained in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{z_i,z_j\}} .

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Pr[z_i \mbox{ or } z_j \mbox{ is first pivot chosen from } Z_{ij}] = \frac{2}{j-i+1}}

Therefore, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle E[X] = \ldots = O(n \log{n})} .