JHU 605.421 response to Muddiest Point for module 7.

muddy7.rb

# JHU 605.421
# 03/14/2013
# Here's a response to your muddy question. This will run through the 
# example given in the course material and trace out what is happening. 
# Specifically, it traces the partition function
# 
# Outputs
# 
#  p                    r
# [5, 3, 2, 6, 4, 1, 3, 7]
#  p        r
# [3, 3, 2, 1,  ,  ,  ,  ]
#     p     r
# [ , 2, 3, 3,  ,  ,  ,  ]
#              p        r
# [ ,  ,  ,  , 4, 6, 5, 7]
#           p           r
# [ ,  ,  , 3, 4, 6, 5, 7]
#     p                 r
# [ , 2, 3, 3, 4, 6, 5, 7]


class QuickSortTrace 

  def quicksort(array)
    quicksortHelper(array, 0, array.size - 1)
    array
  end

  def quicksortHelper(array, p, r)
    if p < r then
      puts "#{prettyPartition(array, p, r)}"
      q = partition(array, p, r)
      if q == 0 then 
        return
      end
      if p < q - 1 then
        quicksortHelper(array, p, q - 1)
      end
      if q < r
        quicksortHelper(array, q, r)
      end
    end
  end

  def partition(array, p, r)
    x = array[p]
    i = p
    j = r
    until i >= j do
      until array[j] < x || j <= 0 do
        j = j - 1
      end
      until array[i] >= x do
        i = i + 1
      end
      if i < j then
        exchange array, i, j
      end
    end
    return j
  end

  def exchange(array, i, j) 
    temp = array[i]
    array[i] = array[j]
    array[j] = temp
  end

  def prettyPartition(arr, p, r)
    markers = ' '
    s = '['
    p.times do 
      markers += '   '
      s += ' , '
    end
    markers += 'p '
    i = p
    while i <= r
      markers += '   '
      s += "#{arr[i]}, "
      i += 1
    end
    markers = markers[0..-6]
    s = s[0..-3]
    markers += 'r'
    (arr.size - 1 - r).times do
      s += ',  '
    end
    s += "]"
    "#{markers}\n#{s}"
  end
end

sorter = QuickSortTrace.new
array = [5, 3, 2, 6, 4, 1, 3, 7]
sorter.quicksort(array)