Selection sorter

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?

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:

• Be true to the algorithm but essentially write C code in ruby

• 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


StackExchange Code Review Q#40700, answer score: 7