Quicksort Algorithm--Ruby Implementation

Question

Have been bashing my head in trying to debug my quicksort implementation and could use a new set of eyes. I'm following along Robert Sedgewick's Coursera Algorithms course and I have absolutely no idea what's wrong with the way I'm doing it (looks nearly identical to his java implementation). Any ideas? I know my partition method works since I've extensively stress-tested it (i.e if I submit low to be 0 and high as 2, then the array will be properly partitioned between those indices).

Also, I'm using quicksort as an in-place sort so that's why I'm not creating an auxiliary array.

def shuffle(arr)
  arr.each_index do |i|
    r = rand(0..i)
    arr[i], arr[r] = arr[r], arr[i]
  end
  arr
end

def partition!(arr,low, high)
  #debugger
  arr = shuffle(arr)
  i = low + 1 
  j = high
  while true 
    until arr[i] >= arr[low]
      break if i >= high
      i+=1
    end

    until arr[j] <= arr[low]
      j-=1
    end

    if i>=j 
      #done 
      arr[j], arr[low] = arr[low], arr[j]
      break 
    else 
      #swap and continue
      arr[i], arr[j] = arr[j], arr[i]
    end
  end 
end


def quicksort(arr, low = 0, high=arr.length-1)
  arr = shuffle(arr)
  quicksort!(arr, low, high)
end

def quicksort!(arr, low, high)
   #p "Quicksorting on low index #{low} and high index #{high}"
   return arr if (high <= low)
   j = partition!(arr, low, high)
   quicksort!(arr, low, j-1)
   quicksort!(arr, j+1, high)
end

Are you able to run this program? quicksort! method takes 4 arguments and you are calling it with 3 arguments. — dnsh
sorry about that-- I accidentally copied over a version that I was debugging. Fixed it now. — segue_segway
Which array do you try to sort, which method do you call and do you get an unsorted array, or do you get an error? — Eric Duminil

Eric Duminil Eric Duminil · Accepted Answer · 2016-12-26T23:33:43

You were almost there.

Problems

#1

partition should return j. See the corresponding java code.

#2

You already shuffle the array in quicksort, no need to shuffle it again and again in partition!

Also, note that your shuffle method shuffles the whole array, independently from j, low and high.

Shuffling only the left and right subarrays separately at each iteration would work, even though it would be unneeded.

#3

quicksort should return arr.

Complete code

def shuffle(arr)
  arr.each_index do |i|
    r = rand(0..i)
    arr[i], arr[r] = arr[r], arr[i]
  end
  arr
end

def partition!(arr,low, high)
  i = low + 1 
  j = high
  while true 
    until arr[i] >= arr[low]
      break if i >= high
      i+=1
    end

    until arr[j] <= arr[low]
      j-=1
    end

    if i>=j 
      #done 
      arr[j], arr[low] = arr[low], arr[j]
      break 
    else 
      #swap and continue
      arr[i], arr[j] = arr[j], arr[i]
    end
  end 
  j
end


def quicksort(arr, low = 0, high=arr.length-1)
  arr = shuffle(arr)
  quicksort!(arr, low, high)
  arr
end

def quicksort!(arr, low, high)
   return arr if (high <= low)
   j = partition!(arr, low, high)
   quicksort!(arr, low, j-1)
   quicksort!(arr, j+1, high)
end

arr = [3,2,1,4,5]
p quicksort(arr)
# => [1, 2, 3, 4, 5]

Quicksort Algorithm--Ruby Implementation

1 Answers

Problems

#1

#2

#3

Complete code