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

Finkle

DO NOT USE GLOBAL VARIABLES! It kills the whole purpose of the class. – Ribosome

Oh, thank you ill take care of it. Can you suggest me how to call the process recursively ?..im stuck – Finkle

Have you implemented QuickSort in other language? – Neocene

nope.. i have seen a tutorial on its working and coding as per my understanding. – Finkle

Ok,then we need to focus primarily in the algorithm rather than the language. – Neocene

i am good with algorithm, when it comes to code ..i am new to recursion, so i want some suggestion related to my code. – Finkle

Why do you write the qsort algo for yourself? – Shipmaster

because,its best way to practice logical thinking and coding skills. And its how interviews work. – Finkle

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

Hyphen

Is it possible for you to analyse my code and tell where i am going wrong ? – Finkle

pivot = ary.delete_at(rand(ary.size)) it's possible to select nil pivot there. Also you have extra method call for each array.size = 1 – Forerun

@ryaz: Yes, you can select nil as a pivot, if the Array contains nil elements. It's up to the caller to ensure that the elements of the Array are Comparable, I don't think it's the responsibility of the sorting method to check that. – Papandreou

@JörgWMittag What about extra method call if, for example, left.size = 1 ? – Forerun

this is, imo, really beautiful code -- very like the haskell version. but i think it suffers the same issue. partition is creating new arrays, so technically we're not really sorting in place anymore, are we? wouldn't we need a partition! method? – Verst

Hello, this implementation is rather beautiful. However, it is destructive on the input array. It does not need to be, you can re-insert the pivot element after partitioning the array and thus leave the input intact. – Normalie

lol did you pull your code from rails.devcamp.com/ruby-programming/ruby-algorithms/… or did they pull it from you – Joleenjolene

@Seal: No, I didn't. That would be illegal, un-ethical, and a violation of Stack Overflow's Terms of Service. I don't know whether they copied the code from here, but if they did, that would be illegal and un-ethical as well. – Papandreou

I've seen this implementation in a couple of courses (possibly copied from this post?). Although I understand what it is doing, there's some bizarre stuff going on with the splat operators in the return statement; I hope someone could shed some light on how they work in this context. There's a small gotcha in this implementation: it will remove repeated elements. – Mercy

@Cenobyte321: Can you explain under which precise conditions it would remove repeated elements? I cannot see anything in the logic that would cause that, nor can I provoke this behavior in testing, e.g. [1, 1, 1].quicksort #=> [1, 1, 1]. – Papandreou

Yes, you're right, my bad, let's say I just messed up my test cases. Could you please explain how the splat operator works in the return statement? As I see it, in the simplest case [1].quicksort => pivot = 1, left = [], right = [], left.quicksort = [], right.quicksort = [] => return [ [] ,1, [] ]. If I write a function that just returns *array it doesn't affect the array passed, it just coerces nil to an empty array. – Mercy

While this is short and sweet, be careful as mentioned above, the sorting does not happen in-place. 3 new arrays are created for each element in the array (left, right, and returned combined) as they get sorted. – Trehalose

Answer 2

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

Intersexual

Sure, ill go through this. Can you let me know how is my code so far ? i mean to say the logic or the style of programming ? As i am a newbie i want to get some suggestions to improve. – Finkle

@rahulinsane There's some good links / resources at the ruby tag. I'd start there. Reading & contributing to other people's code is a good way to learn too. – Intersexual

It's worth noting that this base case will not work if you have any repeated elements. For example, if you have [7, 4,4], and the pivot is 4, then you'll always end up with your less array having 2 elements ([4,4]). So to handle such cases, the base case should be array.length <= 1 || array.uniq.count == 1 – Stephanus

no need to use sorted_array, you can just return quicksort(less) + [pivot] + quicksort(greater) – Villagomez

Answer 3

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]

Salesman

This looks great, thanks. I would maybe use multiple assignments instead of temp assignments to make it cleaner: array[i], array[current_index] = array[current_index], array[i] – Inscribe

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

Meraz

Answer 5

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] 

Braynard

Answer 6

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

Spiry