Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Reference: Is this a faithful rendition of the selection sort algorithm?

I'm working through an elementary book on sort and search algorithms, and writing some sample code to test my understanding. Here, I've been fiddling with a Ruby implementation of a selection sort algorithm. My first attempt (see link) seemed to work, but used multiple arrays, and deleted from one and placed into a second. I was advised that an in-place approach would be more normal.

This is my first cut at that approach. Sadly, it's exactly sort of thing I wanted to avoid, as it feels nastily procedural, with nested loops. However, I think it's a faithful implementation.

class SelectionSorter

  def sort(list)
    sorted_boundary = (0..(list.length)-1)
    sorted_boundary.each do |sorted_index|
      smallest_index = sorted_index
      smallest_value = list[smallest_index]
      comparison = sorted_index + 1
      (comparison..(list.length-1)).each do |next_index|
        if list[next_index] < smallest_value
          smallest_index = next_index
          smallest_value = list[smallest_index]
        end
      end
      unless sorted_index == smallest_index
        list[smallest_index] = list[sorted_index]
        list[sorted_index] = smallest_value
      end
    end
    list
  end

end

Unit test here:

require 'minitest/autorun'
require_relative 'sort'

class SelectionSortTest < MiniTest::Test

  describe SelectionSorter do

    it 'sorts a randomly generated list' do
      list = (1..12).map { rand(100-1) + 1 }
      sorted_list = list.sort
      sorter = SelectionSorter.new
      sorter.sort(list).must_equal sorted_list
    end

  end

end

I'd love to do this in a more recursive fashion, with less stored state, and without nested loops. Any suggestions?

share|improve this question
    
Perhaps mention that selection sort is just one approach to doing a regular sort. Sample data not reqd. Also, you lost your link when moving the question from SO. –  Cary Swoveland Feb 2 at 23:42
    
Test added - I forgot to include this - it was in the original on SO. –  bbcmicro Feb 3 at 5:56
    
f you are satisfied with any of the answers, you should select the one that was most helpful to you. –  Cary Swoveland Feb 27 at 20:32

6 Answers 6

To be true to the spirit of the algorithm, you really should not make any array copies. Below is a recursive solution which accomplishes that except in one method, and that one method can easily be rewritten to avoid making any copies altogether. But I was aiming for clarity.

One of the reasons you're having trouble implementing this in a functional style is that the algorithm, at heart, is not functional. In much the same way, a true quicksort cannot be done in idiomatic haskell.

What I've done below is keep to the spirit of the original algorithm, while taking advantage of some of ruby's syntactic sugar, so that the algorithm is still slightly briefer and more readable than it would be in, say, C. But really, at the end of the day, you are faced with a choice:

  1. Be true to the algorithm but essentially write C code in ruby
  2. Don't but true to the algorithm, in which case you can do all sorts of things (the other answers show some of them).

But if we're in case 2, you have to start asking why not just use the built in ".sort" method?

class SelectionSorter

  def sort(list, start_index=0)
    return list if start_index == list.size-1
    swap(list, start_index, min_index(list, start_index))
    sort(list, start_index + 1)
  end

  def swap(list, start_index, min_index)
    temp = list[start_index]
    list[start_index] = list[min_index]
    list[min_index] = temp
  end

  def min_index(list, start_index)
    # this is a "cheat" but could be replaced with a standard loop to avoid 
    # any array copies
    unsorted = list[start_index..-1]
    start_index + unsorted.find_index(unsorted.min)
  end

end
share|improve this answer
1  
This is really helpful, thanks. As I move onto some of the other algorithms, I expect I'll encounter approaches that lend themselves to a more functional approach. –  bbcmicro Feb 3 at 5:39
    
Many traditional sorting algorithms do in place sorts, which by definition involves lots of mutation, and hence is incompatible with a functional approach. In some cases you can make tweaks and adapt the algos to a functional approach and, depending on your language and compiler, still get good performance. And some algorithms are specially designed for a functional approach, and if you really want to do functional programming it's best to just use those. –  Jonah Feb 3 at 6:13
    
To add one final comment: If your goal is just to practice your ruby skills and improve your idiomatic ruby, then the answer is simply to choose different problems to practice on: ones that are a natural fit. –  Jonah Feb 3 at 6:14
    
The goal is to understand the algorithms. Ruby is the language I know best, but my aesthetic sense makes me uncomfortable when I write what to me seems to be ugly Ruby. Part of the learning process is, I suspect, to understand which language most suits the algorithm! –  bbcmicro Feb 3 at 8:46
    
Jonah, I like the way you have broken this into three methods, but I wanted to point out that recursion isn't really buying you anything. You could keep your structure and simplify by replacing sort() with: def sort(list); (list.size-1).times { |start_index| swap(list, start_index, min_index(list, start_index)) }; list; end. end –  Cary Swoveland Feb 4 at 3:36

Here are a couple of Ruby-like approaches you might consider:

def sort(unsorted)
  sorted = []
  until unsorted.empty? do
    smallest = [unsorted.first, 0]
    (1...unsorted.size).each do |i|
      v = unsorted[i]
      smallest = [v, i] if v < smallest.first
    end  
    sorted << unsorted.delete_at(smallest.last)
  end
  sorted
end

a = [2, 5, 3, 1, 6, 3, 3, 4, 8, 3, 7]
b = sort(a)
#=> [1, 2, 3, 3, 3, 3, 4, 5, 6, 7, 8] 

This is quite straightforward, similar to what you would see when using a procedural language.

Here's a recursive approach:

def sort(unsorted, sorted = [])
  return sorted if unsorted.empty?
  m = unsorted.min
  sorted.concat([m]*(unsorted.count(m)))
  unsorted.delete(m)
  sort(unsorted, sorted)
end

sort(a)
#=> [1, 2, 3, 3, 3, 3, 4, 5, 6, 7, 8]  
  • First find m, the minimum of the unsorted elements.
  • Append unsorted.count(m) m's to the sorted list. sorted += [m]*(unsorted.count(m)) could be used instead of concat, but += creates a new array, whereas concat does not.
  • Delete all values m from the unsorted list.

The latter solution is relatively inefficient, as we make three passes through the unsorted list each time we move one or more values from the unsorted to the sorted list. That's mainly because I wanted to illustrate how the sort could be done without using indices.

This is a sort of "fake" recursion, because it doesn't exploit the power of recursion; we could have simply put the code that transfers the mins in a until unsorted.empty? do loop. I don't see how recursion can be used to advantage here.

share|improve this answer
    
Thanks! This bears some similarities to my original idea, although I elected not to use .min. I think yours is rather elegant, but thanks for helping me understand the tension between aesthetic principles and efficiency! I might have a crack at profiling them. –  bbcmicro Feb 3 at 5:44

If you really want to go down functional path you should learn a Haskell (for Great Good) or at least consult Haskell solutions. You can find compact Ruby solution there too. Ruby is not designed for recursive approach, you will suffer from performance issues or blown up stack. Anyway my translation of Haskell approach if you don't know Haskell (ineffective!):

def uninject(b, &block)
  result = []
  while ab = block[b]
    result << ab.first
    b = ab.last
  end
  result
end

def sort(list)
  uninject(list) do |slist|
    unless slist.empty?
      head, *tail = slist
      tail.inject([head, []]) do |(min_v, rest), v| 
        v < min_v ? [v, [min_v, *rest]] : [min_v, [v, *rest]]
      end
    end
  end
end
share|improve this answer
    
Yes, I was planning to try a pure functional approach, probably in Haskell. I've dabbled in Haskell, but not so much as to be confident to understand code. But it appeals to me very much. –  bbcmicro Feb 3 at 5:46
    
Is it true to say Ruby isn't designed for a recursive approach? Maybe it isn't optimised for such an approach, being an explicitly OO language, but it seems often Ruby adopts a recursive approach, or at least an approach that discourages side-effects? –  bbcmicro Feb 3 at 5:47
    
No tail call optimization means not designed for recursive approach in my books (that's why uninject in my code is a loop, while in Haskell unfoldr is recursive). Besides functional language should use immutable data structures to be efficient, otherwise it's just copying data from one place to another. –  Victor Moroz Feb 3 at 11:49

Here's how I'd tackle the in-place version leveraging Ruby's capabilities. It's not recursive, but it's structured fairly functionally.

class Array
  def swap!(i,j)
    self[i], self[j] = self[j], self[i] unless i == j
  end

  def min_index_from(i)
    (i...length).each.inject {|min, current| self[current] < self[min] ? current : min}
  end

  def selection_sort!
    (0...length-1).each {|i| swap!(i, min_index_from(i)) }
    self
  end
end

if __FILE__ == $0
  require 'test/unit'
  class SelectionSort_test < Test::Unit::TestCase
    def test_selection_sort
      10.times do
        a = Array.new(1000).map {rand}
        b = a.sort
        assert_equal a.selection_sort!, b
      end
    end
  end
end

If you try to do this recursively, the recursive subproblem is only one element smaller than the previous level's problem so you can quickly run into stack limits if you try to sort large vectors.

Instead, I tried to slim it down so the iterative aspects felt less "clunky", and to make it glaringly obvious that the nature of selection sort is to repeatedly find the minimum element of the remaining data and exchange it with the first element of the remaining data.

share|improve this answer
    
Hi, and welcome to CodeReview. Nice enough answer but you should consider adding some comment on why doing it iteratively is better than the recursive alternative (especially since the OP's intent was to make it 'more recursive' –  rolfl Feb 3 at 18:14
    
@rolfl Thanks for the welcome. Hopefully the additional comments clarify the intent. –  pjs Feb 3 at 22:17
    
That helps a lot... you already have my +1 –  rolfl Feb 3 at 22:26
class SelectionSorter
  attr_reader :list

  def sort(unsorted_list)
    @list = unsorted_list

    sorting(boundary(0)) do |sorted_index|
      sorting(boundary(sorted_index +1))
      compare_to_smallest_index(sorted_index)
    end

    list
  end

  private
  attr_accessor :smallest_value, :smallest_index

  def boundary(start)
    start..(list.length -1)
  end

  def compare_to_smallest(sorted_index)
    set_list_values unless sorted_index == smallest_index
  end

  def set_list_values(index)
    list[smallest_index] = list[index]
    list[index] = smallest_value
  end

  def set_smallest_value(index)
    @smallest_index = index
    @smallest_value = list[smallest_index]
  end

  def sorting(sort_boundary)
    sort_boundary.each do |index|
      set_smallest_value(index)

      yield(index)
    end
  end

end
share|improve this answer
4  
Please consider explaining how this works in relation to the OP's code. This isn't much of a review by itself. –  Jamal Feb 3 at 1:02
    
sure I'll add comments - it asked for refactoring –  Richard Jordan Feb 3 at 2:46

The implementation you posted in this question is fine, in my opinion. As you suspected, it is a "natural" approach for Ruby, and I wouldn't make major changes to it. You could get rid of the unless, since swapping an element with itself is a no-op.

Just for the sake of comparison, I'll offer two other implementations. First, define a helper function:

# Returns the index and value of the smallest among
#   array[start], array[start + 1], ..., array.last
#
# Implemented recursively, but you could substitute a more natural
# implementation using array.each_with_index.
def smallest(array, start=0)
  if start == array.length - 1
    return start, array[start]
  else
    j, val = smallest(array, start + 1)
    return array[start] < val ? [start, array[start]] : [j, val]
  end
end

Using that helper, you could implement a recursive, functional selection sort:

def functional_selection_sort(array)
  if array.empty?
    []
  else
    _, min = smallest(array)
    min, larger = array.partition { |item| item == min }
    min.concat(functional_selection_sort(larger))
  end
end

If you want to sort the array in place, though, it's hard to avoid using .each in some form or other:

def inplace_selection_sort!(array)
  array.each_with_index do |item, index|
    smallest_i, smallest = smallest(array, index)
    array[index], array[smallest_i] = smallest, item
  end
end

Note the use of ! in the name to emphasize that it works in place.

The behaviour:

a = [3, 1, 4, 1, 5, 9, 2, 6, 5]
functional_selection_sort(a)  #=> [1, 1, 2, 3, 4, 5, 5, 6, 9]
a                             #=> [3, 1, 4, 1, 5, 9, 2, 6, 5]
inplace_selection_sort!(a)    #=> [1, 1, 2, 3, 4, 5, 5, 6, 9]
a                             #=> [1, 1, 2, 3, 4, 5, 5, 6, 9]
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.