CODEWITHSUNDEEP
ruby
NickTerrafranca
NickTerrafranca

Reputation: 109

Implementing quick sort in Ruby

I am new to programing. I am trying to implement the quick sort algorithm in Ruby. I can't find many examples online that I can decipher well enough to use as examples. I have it working with floats, integers and strings. I need help getting it to work with duplicate items in the array. For example it works well with: [-13, 12, 589, 11, 0, 27, 36, 92, 7, -2, 1001] But not with: [3, 2, 1, 1, 2, 3]

Thank you in advance!

def quick_sort(list, start_point = nil, end_point = nil)
  if start_point && end_point
    if start_point >= end_point
     return list
    end
    left = start_point
    right = end_point
    pivot = left
  else
    left = 0
    right = list.count - 1
    pivot = left
  end

  min = left
  max = right

  while left < right
    if list[pivot] < list[right]
      right -= 1
    else
      list[pivot], list[right] = list[right], list[pivot]
      pivot = right
    end

    if list[pivot] > list[left]
      left += 1
    else
      list[pivot], list[left] = list[left], list[pivot]
    pivot = left
    end
  end
  quick_sort(list, min, pivot -1) 
  quick_sort(list, pivot +1, max) 
end

Upvotes: 0

Views: 171

Answers (1)

SteveTurczyn
SteveTurczyn

Reputation: 36860

The problem is the code you're using to determine the highest index value.

right = list.index(list[-1])

Which is basically saying "give me the index of the value in the last element" but the last element value is 3 and that unfortunately is also the value of the first element, so it's returning 0 (the first occurence of the value it finds).

Better would be...

right = list.count - 1

EDIT also, you should handle the condition of two values being the same when comparing the values... that condition should be treated the same as 'no swap required'

so instead of

if list[pivot] < list[right]
...
if list[pivot] > list[left]

do

if list[pivot] <= list[right]
...
if list[pivot] >= list[left]

Upvotes: 1

Related Questions