Method: Algorithmable::Sort::Utils#partition

Defined in:
lib/algorithmable/sort/utils.rb

#partition(a, bottom, top) ⇒ Integer

Returns Integer representing new pivot location.

Parameters:

  • a (Integer)
  • bottom (Integer)
  • top (Array)

Returns:

  • (Integer) —

    Integer representing new pivot location



8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
# File 'lib/algorithmable/sort/utils.rb', line 8

def partition(a, bottom, top)
  i = bottom
  j = top.succ
  v = a[bottom]
  loop do
    while a[i += 1] < v
      break if i == top
    end
    while v < a[j -= 1]
      break if j == bottom
    end
    break if i >= j
    cur_i = a[i]
    a[i] = a[j]
    a[j] = cur_i
  end
  cur_bottom = a[bottom]
  a[bottom] = a[j]
  a[j] = cur_bottom
  j
end