# Help refactor this to be less procedural and more recursive

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?

-
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 '14 at 23:42
Test added - I forgot to include this - it was in the original on SO. –  bbcmicro Feb 3 '14 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 '14 at 20:32

## 5 Answers

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

-
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 '14 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 '14 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 '14 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 '14 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 '14 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.

-
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 '14 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

-
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 '14 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 '14 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 '14 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.

-
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 '14 at 18:14
@rolfl Thanks for the welcome. Hopefully the additional comments clarify the intent. –  pjs Feb 3 '14 at 22:17
That helps a lot... you already have my +1 –  rolfl Feb 3 '14 at 22:26

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]

-