I am trying to sort a random array of 15 element before creating a Binary Search Tree using Quicksort and an error pops up. I can't seem to find where the problem is.
This is the error:
C:/Users/K/Desktop/odin/FullStack/Ruby_on_Rails/Ruby/projects/binary-search-trees/lib/tree.rb:197:in `<=': comparison of Integer with nil
failed (ArgumentError)
from C:/Users/K/Desktop/odin/FullStack/Ruby_on_Rails/Ruby/projects/binary-search-trees/lib/tree.rb:197:in `block in partition'
from C:/Users/K/Desktop/odin/FullStack/Ruby_on_Rails/Ruby/projects/binary-search-trees/lib/tree.rb:194:in `each'
from C:/Users/K/Desktop/odin/FullStack/Ruby_on_Rails/Ruby/projects/binary-search-trees/lib/tree.rb:194:in `partition'
from C:/Users/K/Desktop/odin/FullStack/Ruby_on_Rails/Ruby/projects/binary-search-trees/lib/tree.rb:181:in `quick_sort'
from C:/Users/K/Desktop/odin/FullStack/Ruby_on_Rails/Ruby/projects/binary-search-trees/lib/tree.rb:185:in `quick_sort'
from C:/Users/K/Desktop/odin/FullStack/Ruby_on_Rails/Ruby/projects/binary-search-trees/lib/tree.rb:10:in `initialize'
from ./lib/main.rb:5:in `new'
from ./lib/main.rb:5:in `<main>'
The quick sort method is :
def quick_sort(array, s, e)
if s < e
p = partition(array, s, e)
quick_sort(array, s, p - 1)
quick_sort(array, p + 1, e)
end
array.uniq!
array
end
The problem is in the helper method below:
def partition(array, s, e)
x = array[e]
i = s - 1
(s...e).each do |j|
next unless array[j] <= x
i += 1
swap(array, i, j)
end
swap(array, (i + 1), e)
i + 1
end
In full the code looks like this:
def quick_sort(array, s, e)
if s < e
p = partition(array, s, e)
quick_sort(array, s, p - 1)
quick_sort(array, p + 1, e)
end
array.uniq!
array
end
def partition(array, s, e)
x = array[e]
i = s - 1
(s...e).each do |j|
next unless array[j] <= x
i += 1
swap(array, i, j)
end
swap(array, (i + 1), e)
i + 1
end
def swap(array, i, j)
temp = array[i]
array[i] = array[j]
array[j] = temp
array
end
I found that the problem was in the destructive method uniq! in the quick_sort method which modifies the array, but the boundaries s and e stay the same. I changed it to return the uniq elements in the array. Here is the answer
def quick_sort(array, s, e)
if s < e
p = partition(array, s, e)
quick_sort(array, s, p - 1)
quick_sort(array, p + 1, e)
end
array.uniq
end