Method: Algorithms::Sort.partition

Defined in:

lib/algorithms/sort.rb

.partition(data, left, right) ⇒ Object

Quicksort: A divide-and-conquer sort that recursively partitions a container until it is sorted. Requirements: Container should implement #pop and include the Enumerable module. Time Complexity: О(n log n) average, O(n^2) worst-case Space Complexity: О(n) auxiliary Stable: No

Algorithms::Sort.quicksort [5, 4, 3, 1, 2] => [1, 2, 3, 4, 5]

def self.quicksort(container)

return [] if container.empty?

x, *xs = container

quicksort(xs.select { |i| i <  x }) + [x] + quicksort(xs.select { |i| i >= x })

end

# File 'lib/algorithms/sort.rb', line 154

def self.partition(data, left, right)
  pivot = data[front]
  left += 1

  while left <= right do
    if data[frontUnknown] < pivot
      back += 1
      data[frontUnknown], data[back] = data[back], data[frontUnknown] # Swap
    end

    frontUnknown += 1
  end

  data[front], data[back] = data[back], data[front] # Swap
  back
end