CODEWITHSUNDEEP
ruby
rememberThis123
rememberThis123

Reputation: 123

How could I improve this super simple sorting method? - Beginning Ruby

I'm learning Ruby from Chris Pine's "Learn To Program" book and I've been asked to write a method that sorts a set of given words in alphabetical order either with loops or recursion. I first gave looping a try. 

def sort words
    i = 0
    checked = 0
    while true
        if (i+1 < words.length)
            if (words[i]>words[i+1])
                temp = words[i] 
                words[i] = words[i+1]
                words[i+1] = temp
            else
                checked+=1
            end 
            i+=1
        elsif (checked == words.length-1)
            break
        else
            i =0
            checked =0
        end
    end
    return words
end

The code works, but I wanted to see if any seasoned ruby-ists could offer some input on how to make it more efficient.

Thank You!

Upvotes: 2

Views: 62

Answers (2)

tadman
tadman

Reputation: 211610

The first thing to learn when you're beginning to understand optimization is that the most obvious fixes are often the least productive. For example, you could spend a lot of time here tweaking some of these comparisons or switching to a slightly different way of evaluating the same thing and get a 5-10% performance increase.

You could also use a completely different algorithm and get a 5x-10x increase. Bubble-sort, which is what you have here, is nearly the worst performing sorting algorithm ever made. This is a technique you should learn if only to understand that it's terrible and you should immediately move on to other methods, like Quicksort which is not all that hard to implement if you approach the problem systematically.

So in other words, before you start tweaking little things, step back and ask yourself "Am I approaching this problem the right way?" Always consider other angles when you have a performance problem.

That being said, here's how to make your code more Ruby-like:

def sort(words)
  # Make a copy so the original isn't mangled
  words = words.dup

  # Iterate over ranges:
  #   (n..m) goes from N to M inclusive
  #   (n...m) goes from N up to but not including M
  (0...words.length-1).each do |i|
    (0...words.length-1-i).each do |j|
      # Examine the pair of words at this offset using an array slice
      a, b = words[j, 2]

      # If A is ahead of B then...
      if (a > b)
        # ...swap these elements.
        words[j, 2] = [ b, a ]
      end
    end
  end

  words
end

# Quick test function that uses randomized data
p sort(%w[ a c d f b e ].shuffle)

To improve as a developer you should always try and measure your progress somehow. Tools like Rubocop will help identify inefficient coding practices. Test-driven development can help to identify flaws early in your programming and to make sure that changes don't cause regressions. Benchmarking tools help you better understand the perfomance of your code.

For example:

require 'benchmark'

CHARS = ('a'..'z').to_a

def random_data
  Array.new(1000) { CHARS.sample }
end

count = 100

Benchmark.bm do |bm|
  bm.report('my sort:') do
    count.times do
      sort(random_data)
    end
  end

  bm.report('built-in sort:') do
    count.times do
      random_data.sort
    end
  end
end

#                     user     system      total        real
# my sort:       19.220000   0.060000  19.280000 ( 19.358073)
# built-in sort:  0.030000   0.000000   0.030000 (  0.025662)

So this algorithm is 642x slower than the built-in method. I'm sure you can get a lot closer with a better algorithm.

Upvotes: 4

Shiva
Shiva

Reputation: 12524

Firstly, you dont have to reinvent the Wheel. I mean, see this example:

> ['a', 'abc', 'bac', 'cad'].sort
# => ["a", "abc", "bac", "cad"]

Ruby has a extensively huge set of libraries. Common stuffs are so efficiently supported by Ruby. You just have to have enough knowledge to use the language features efficiently.

I would recommend you to go through the Ruby core libraries and learn to use to combine the features to achieve something special.

Give a try to this Ruby Koans http://rubykoans.com/

RubyKoans is the most efficient to achieve mastery over Ruby language.

Here is a list of Sorting algorithm examples by type in this site https://www.sitepoint.com/sorting-algorithms-ruby/

You have to choose between algorithms wisely based on size of problems domain and usecases.

Upvotes: 0

Related Questions