Module: Sorting

Included in:
Array
Defined in:
lib/kimquy_algo.rb

Instance Method Summary collapse

Instance Method Details

#kimquy_merge_sort(a, p, r) ⇒ Object 



33
34
35
36
37
38
39
40
 
# 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) ⇒ Object 



2
3
4
5
6
7
8
 
# 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) ⇒ Object 



42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
 
# 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) ⇒ Object 



10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
# 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