Quick Sort in Ruby language

Question

I am trying to implement Quick sort in ruby but stuck in how to call recursively after the first partition of pivot. Please help me to understand on how to proceed and also let me know whether my style of coding is good so far .

class QuickSort
    $array= Array.new()
    $count=0

    def add(val) #adding values to sort
        i=0
        while val != '000'.to_i
            $array[i]= val.to_i
            i=i+1
            val = gets.to_i
        end
    end

    def firstsort_aka_divide(val1,val2,val3) #first partition
        $count = $count+1
        @pivot = val1
        @left = val2
        @right =val3
        while @left!=@right do # first divide/ partition logic

            if $array[@right] > $array[@pivot] then
                @right= @right-1
            elsif $array[@right] < $array[@pivot] then
                @var = $array[@right]
                $array[@right] = $array[@pivot]
                $array[@pivot] = @var
                @pivot = @right
                @left = @left+1
            end 
            if $array[@left] < $array[@pivot]
                @left= @left+1
            elsif $array[@left] > $array[@pivot]
                @var = $array[@left]
                $array[@left] = $array[@pivot]
                $array[@pivot] = @var
                @pivot =@left
            end

        end
        puts "\n"                   # printing after the first partition i.e divide 
        print " Array for for divide ---> #{$array}"
        puts "\n"
        puts " pivot,left,right after first divide --> #{@pivot},#{@left},#{@right}"

        firstsort_aka_divide()  # Have to call left side of partition recursively -- need help
        firstsort_aka_divide()  # Have to call right side of partition recursively -- need help

    end
end

ob= QuickSort.new

puts " Enter the numbers you want to sort. \n Press '000' once you are done entering the values" 
val = gets.to_i
ob.add(val)
puts " Sorting your list ..."
sleep(2)
ob.firstsort_aka_divide(0,0,($array.size-1)) # base condition for partitioning

Answer 1

This is how I would implement quick sort in Ruby:

def quicksort(*ary)
  return [] if ary.empty?

  pivot = ary.delete_at(rand(ary.size))
  left, right = ary.partition(&pivot.method(:>))

  return *quicksort(*left), pivot, *quicksort(*right)
end

Actually, I would probably make it an instance method of Array instead:

class Array
  def quicksort
    return [] if empty?

    pivot = delete_at(rand(size))
    left, right = partition(&pivot.method(:>))

    return *left.quicksort, pivot, *right.quicksort
  end
end

Answer 2

def quicksort(array)
  # if array is empty or has only one element there is no need to sort
  return array if array.size <= 1 
  
  # for the sake of performance (ms performance :] ) we can always use the first element as a pivot
  pivot = array.delete_at(0) 

  # partition will split array into 2 sub arrays based on the condition passed
  # in this case everything smaller than the pivot will be the first array on the left => [[ e < pivot ], [e > pivot]]
  # the e qual to pivot will go on the bigger element 
  left, right = array.partition { |e| e < pivot } 

  # flatten the multiple sub arrays returned from recursive quicksorts
  return [quicksort(left), pivot, quicksort(right)].flatten 
end

Answer 3

def sort(ary)
  return ary if ary.size < 2

  pivot = ary[-1]
  sm_ary = []
  lg_ary = []

  ary[0..-2].each do |x|
    lg_ary.push(x) && next if x >= pivot

    sm_ary.push(x) && next if x < pivot
  end

  [*sort(sm_ary), pivot, *sort(lg_ary)]
end

arr = [10, 7, 8, 9, 7, 1, 5]
print sort(arr) 
# [1, 5, 7, 7, 8, 9, 10] 

Answer 4

My implementation based on recursive algorithm from Grokking-Algorithms book:

def quick_sort(arr)
  return arr if arr.size < 2

  pivot = arr[0]
  less = arr[1..].select {|el| el <= pivot}
  greater = arr[1..].select {|el| el > pivot}
  return *quick_sort(less), pivot, *quick_sort(greater)
end

Answer 5

here is another way to implement quicksort -- as a newbie I think it's easier to understand -- hope it helps someone :) in this implementation the pivot is always the last element in the array -- I'm following the Khan Academy course and that's where I got the inspiration from

def quick_sort(array, beg_index, end_index)
  if beg_index < end_index
    pivot_index = partition(array, beg_index, end_index)
    quick_sort(array, beg_index, pivot_index -1)
    quick_sort(array, pivot_index + 1, end_index)
  end
  array
end

#returns an index of where the pivot ends up
def partition(array, beg_index, end_index)
  #current_index starts the subarray with larger numbers than the pivot
  current_index = beg_index
  i = beg_index
  while i < end_index do
    if array[i] <= array[end_index]
      swap(array, i, current_index)
      current_index += 1
    end
    i += 1
  end
  #after this swap all of the elements before the pivot will be smaller and
  #after the pivot larger
  swap(array, end_index, current_index)
  current_index
end

def swap(array, first_element, second_element)
  temp = array[first_element]
  array[first_element] = array[second_element]
  array[second_element] = temp
end

puts quick_sort([2,3,1,5],0,3).inspect #will return [1, 2, 3, 5]

Answer 6

Here is a (very) naive quicksort implementation, based on Wikipedia's simple-quicksort pseudocode:

def quicksort(array) #takes an array of integers as an argument

You need a base case, otherwise your recursive calls never terminate

if array.length <= 1
  return array

Now pick a pivot:

else
  pivot = array.sample
  array.delete_at(array.index(pivot)) # remove the pivot
  #puts "Picked pivot of: #{pivot}"
  less = []
  greater = []

Loop through the array, comparing items to pivot and collecting them into less and greater arrays.

  array.each do |x|
    if x <= pivot
      less << x
    else
      greater << x
    end
  end

Now, recursively call quicksort() on your less and greater arrays.

  sorted_array = []
  sorted_array << self.quicksort(less)
  sorted_array << pivot
  sorted_array << self.quicksort(greater)

Return the sorted_array and you're done.

  # using Array.flatten to remove subarrays
  sorted_array.flatten!

You can test it with

qs = QuickSort.new

puts qs.quicksort([1, 2, 3, 4, 5]) == [1, 2, 3, 4, 5] # true
puts qs.quicksort([5]) == [5] # true
puts qs.quicksort([5, -5, 11, 0, 3]) == [-5, 0, 3, 5, 11] # true
puts qs.quicksort([5, -5, 11, 0, 3]) == [5, -5, 11, 0, 3] # false