class QuickSort

Public Class Methods

partition(array, start, length = array.length, &prc) click to toggle source
# 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) click to toggle source

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

# 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) click to toggle source

In-place.

# 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