module Sorting

Public Instance Methods

kimquy_merge_sort(a, p, r) click to toggle source
# File lib/kimquy_algo.rb, line 33
def kimquy_merge_sort(a, p, r)
  if p < r
    q = (p+r)/2
    kimquy_merge_sort(a,p,q) 
    kimquy_merge_sort(a,q+1,r)
    merge(a,p,q,r)
  end
end
kimquy_quicksort(a, p, r) click to toggle source
# File lib/kimquy_algo.rb, line 2
def kimquy_quicksort(a, p, r)
  if p < r
    q = partition(a, p, r) 
    kimquy_quicksort(a, p, q)
    kimquy_quicksort(a,q+1,r)
  end
end
merge(a, p, q, r) click to toggle source
# File lib/kimquy_algo.rb, line 42
def merge(a, p, q, r)

  left = a[p..q-1]
  right = a[q..r]

  left << 1000000000   #sentinel
  right << 1000000000  #sentinel

  i = 0
  j = 0
  k = p
  k.upto(r-1) do |x|
    if left[i] <= right[j]
      a[x] = left[i]
      i = i + 1
    else
      a[x] = right[j]
      j = j + 1
    end
  end
end
partition(a, p, r) click to toggle source
# File lib/kimquy_algo.rb, line 10
def partition(a, p, r)
  x = a[p] 
  i = p 
  j = r - 1 
  while true
    while true
      break if a[j] <= x
      j = j -1
    end 

    while true
      break if a[i] >= x
      i = i +1
    end

    if i < j
      a.swap(i,j)
    else
      return j
    end
  end
end