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