Search code examples
ruby-on-railsrubyalgorithmdata-structuresquicksort

Comparison of Integer with nil failed in quicksort helper method


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

Solution

  • 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