Class: QuickSort

Inherits:
Object
  • Object
show all
Defined in:
lib/simms_structures/quick_sort.rb

Class Method Summary collapse

Class Method Details

.partition(array, start, length = array.length, &prc) ⇒ Object 



39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
 
# File 'lib/simms_structures/quick_sort.rb', line 39

def self.partition(array, start, length = array.length, &prc)
  prc ||= Proc.new { |a, b| a <=> b }

  first_right_idx = nil
  (start + 1).upto(start + length - 1) do |idx|
    case prc.call(array[start], array[idx])
    when -1
      first_right_idx ||= idx
    when 1
      if first_right_idx
        array[first_right_idx], array[idx] = array[idx], array[first_right_idx]
        first_right_idx += 1
      end
    end
  end

  # swap pivot with last 'left' element
  if first_right_idx
    array[start], array[first_right_idx - 1] = array[first_right_idx - 1], array[start]
    (first_right_idx - 1)
  else
    start
  end
end

.sort1(array) ⇒ Object

Not in-place. Uses O(n) memory.



6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
# File 'lib/simms_structures/quick_sort.rb', line 6

def self.sort1(array)
  return array if array.length < 2
  pivot = array.first

  left = []
  right = []

  array.drop(1).each do |el|
    if el < pivot
      left << el
    elsif el > pivot
      right << el
    end
  end

  QuickSort.sort1(left) + [pivot] + QuickSort.sort1(right)
end

.sort2!(array, start = 0, length = array.length, &prc) ⇒ Object

In-place.



25
26
27
28
29
30
31
32
33
34
35
36
37
 
# File 'lib/simms_structures/quick_sort.rb', line 25

def self.sort2!(array, start = 0, length = array.length, &prc)
  return array if length < 2
  prc ||= Proc.new { |a, b| a <=> b }

  pivot_idx = QuickSort.partition(array, start, length, &prc)

  left_length = pivot_idx - start
  right_length = length - (left_length + 1)

  sort2!(array, start, left_length, &prc)
  sort2!(array, pivot_idx + 1, right_length, &prc)
  array
end