Suppose that an array A contains numbers that are either 0 or 1.

Question

Quicksort(a, first, last)
  if first < last 
    p = partition(a, first, last)
    quicksort(a, first, p - 1)
    quicksort(a, p + 1, last)

Partition(a, first, last)
  pivot = a[last]
  i = first - 1
  j = first
  for j to last-1
    if a[j] <= pivot
      i++
      swap a[i] with a[j]
  i++
  swap a[i] with a[last]
  return i

(a) Modify the partition method to to sort an array with only numbers that are either 1 or 0 in linear time

(b) Argue why this does not violate the $\Omega(n lg n)$ bound for comparison based sorting.

(c) Suppose now that the elements consist of numbers from 0 to 5. Can you still use a variation of your algorithm to sort the list in (worst case) linear time?

Attempted solution

(a)

Partition(a, first, last)
  pivot = a[last]
  i = first - 1
  j = first
  for j to last-1
    if a[j] != pivot
      i++
      swap a[i] with a[j]
  i++
  swap a[i] with a[last]
  return i

(b) The bound does not apply here since we know additional information about the input. Since we know information, and are not just getting random input, we are not violating the rule

Answer 1

Hint: you just need to put all the $0$s before all the $1$s. I think it might be easier to create a new array than to swap the elements in your existing one. Is that prohibited by the use of the word "sort"? Even if you do have to swap you should be able to do it on one pass through the array.