Sorting strings in array without sorting function - Ruby

Question

I'm trying to create a sorting algorithm without the sorting function in Ruby. I've based it of the idea of insertion sort. The idea is that the function checks whether the nth value of each two words are same, and if so n increases by one until one value is larger than the other. In that case the words might get switched. However, my function keeps freezing. Any ideas why?

words = ["my","favorite","animal", "are", "the", "elephant", "and", "the", "antelope", "and", "the", "favela"]

#Convert all letters into numbers. Output individual words as arrays.
converted_words = words.map(&:chars).map { |letters| letters.map { |letter| letter.to_i 36 } }
puts converted_words.to_s

i = 1
x = 0
while i < converted_words.length
  if converted_words[i][x] == converted_words[i-1][x]
    x = x + 1
  else
    if converted_words[i][x] < converted_words[i-1][x]
      converted_words[i], converted_words[i-1] = converted_words[i-1], converted_words[i]
      i = 0
      x = 0
    else
      i = i + 1
    end
  end
end
puts converted_words.to_s

As @YvesDaoust pointed out, there are conditions in which you don't increment i. And, yes, you have problems with x. Whenever you change i, you must reset x. Also, if you set i=0 and then try to access converted_words[i-1][0], you're going off back end of the array. And you don't have a termination condition to stop at the end of a word. You need to fire up your debugger and single-step through your code to see where it's going off the rails. — Jim Mischel
– Jim Mischel, Commented Oct 18, 2018 at 15:54
Also, what you have here is a horribly inefficient sorting algorithm that bears little resemblance to insertion sort. If I'm reading intention correctly, you search forward until you find an item that's out of place. You swap items, and then start over from the beginning. So if you wanted to move an item from the end of the array to the beginning, it would take n passes over the array. That makes for an O(n^3) algorithm. Given a sufficiently large array, it wouldn't actually go into an infinite loop; it would just seem like an infinite loop. — Jim Mischel
– Jim Mischel, Commented Oct 18, 2018 at 15:57

Cary Swoveland · Accepted Answer · 2018-10-18 20:38:55Z

2

Your code does not "freeze"; running it raises this exception:

NoMethodError (undefined method '<' for nil:NilClass)

in the line:

if converted_words[i][x] < converted_words[i-1][x]

We immediately see the problem, though the cause is not yet known. The receiver of the method < is converted_words[i][x]. As the error message says that nil does not have a method <, we infer that converted_words[i][x] is nil.¹ That means that an index is out-of-range (examples of an index being out-of-range are [1,2][412] #=> nil and [1,2][-3] #=> nil). If i were out-of-range the expression would reduce to nil[x] < ..., which would raise an exception that nil does not have a method NilClass#\[\]]. That's not our exception message so we conclude that x must be out-of-range.

To see why this is happening, suppose:

words = ["a", "ab"]

Then

converted_words =
  words.map(&:chars).map { |letters| letters.map { |letter| letter.to_i 36 } }
  #=> [[10], [10, 11]] 
i = 1
x = 0
while i < converted_words.length
  #=> while 1 < 2 => while true, so enter the loop
if converted_words[i][x] == converted_words[i-1][x]
  #=> if converted_words[1][0] == converted_words[0][0] => if 10 == 10 => true

so execute

x = x + 1
  #=> x = 0 + 1 => 1

and attempt to repeat the loop.

while i < converted_words.length
  #=> while 1 < 2 => while true, so repeat the loop
if converted_words[i][x] == converted_words[i-1][x]
  #=> if converted_words[1][1] == converted_words[0][1] => if 11 == nil => false

so execute (else).

if converted_words[i][x] < converted_words[i-1][x]
  #=> converted_words[0][1] < converted_words[-1][1] => if nil < 11
  #=> NoMethodError (undefined method '<' for nil:NilClass)

Error messages contain valuable information. Study them carefully!

^{1 The error message "nil has no method <" is here equivalent to, "NilClass has no instance method <".}

edited Oct 18, 2018 at 20:38

answered Oct 18, 2018 at 17:49

Cary Swoveland

111k6 gold badges69 silver badges105 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Benisburgers Over a year ago

Thank you so so much. That is what I was looking for. Thank you for all the hard work. But how were you able to access the error message? My terminal simply stops and does nothing.

Cary Swoveland Over a year ago

I just copied and pasted your code into IRB and ran it. (Ruby v2.5.1, but I don’t think it’s a version issue.)

Benisburgers · Accepted Answer · 2018-10-22 08:40:46Z

I believe I have solved the issue. Thank you for all your help.

I reordered my algorithm: First checking if converted_words[i][x] < converted_words[i-1][x], and then checking if converted_words[i][x] == converted_words[i-1][x].

I also need to check whether if converted_words[i][x] != nil && converted_words[i-1][x] != nil, in order to avoid a NoMethodError (thanks Cary Swoveland). Finally I combined the two algorithms.

I also realized that I did not need to convert the letters to numbers, as ruby knows which letters are larger. So instead, I left the characters as letters.

I'm aware that the code is not very efficent. If you have any suggestions on how to improve or simplify the algorithm, I would be happy to hear them.

Here's the code:

words = ["my","favorite","animals", "are", "the", "elephant", "and", "the", "antelope", "and", "the", "favela"]
puts words.to_s
#Convert all letters into numbers. Output individual words as arrays.
ordered_words = words.map(&:chars).map { |letters| letters.map { |letter| letter } }

i = 1
x = 0
while i < ordered_words.length
  if ordered_words[i][x] != nil && ordered_words[i-1][x] != nil
    if ordered_words[i][x] < ordered_words[i-1][x]
      ordered_words[i], ordered_words[i-1] = ordered_words[i-1], ordered_words[i]
      i = 1
      x = 0
    else
      if ordered_words[i][x] == ordered_words[i-1][x]
        x = x + 1
      else
        i = i + 1
        x = 0
      end
    end
  else
    if ordered_words[i][x] == nil && ordered_words[i-1][x] == nil
      i = i + 1
      x = 0
    else
      if ordered_words[i][x] == nil
        ordered_words[i], ordered_words[i-1] = ordered_words[i-1], ordered_words[i]
        i = 1
        x = 0
      else
        i = i + 1
        x = 0
      end
    end
  end
end

joined_words = []
ordered_words.each do |word|
  joined_words.push(word.join)
end
puts joined_words.to_s

Collectives™ on Stack Overflow

Sorting strings in array without sorting function - Ruby

2 Answers 2

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related