Why is rindex vs. index changing the output of selection sort?

Question

I am working through some very basic algorithm exercises, and I am confused about this implementation of a selection sort:

def selection_sort(xs)
  len = xs.length
  len.times do |i|
    low = xs[i...len].min
    tmp = xs[i]
    xs[i] = low    
    xs[xs.rindex(low)] = tmp
  end
  xs
end

The code works fine, however, if I use xs[xs.index(low)] = tmp instead of xs[xs.rindex(low)] = tmp, the function does not work properly on the following tests:

selection_sort([3, 6, 2, 7, 4, 1, 4, 5, 6, 7, 8, 0])
selection_sort([0, 8, 7, 6, 5, 4, 1, 4, 7, 2, 6, 3])

In my mind, this should not matter since an index is an index whether it is coming from the right or the left. Wouldn't using rindex vs index just change the flow (for duplicate entries), but still output an ordered list?

What am I overlooking?

Answer 1

What's happening is that you're testing the index after you've reassigned the low value, but not before you've reassigned the value that was in the low value's new position. So, let's consider:

xs = [4,3,2,1]
i = 2
low = [2, 1].min = 1
tmp = xs[i] = 2

Now, you assign xs[i] = low, which means that your array now looks like [4,3,1,1]. At this point, xs.index(1) will return 2, since you just put the low value in that position! Using rindex gets you 3, since it will find the value that was used as the low value, rather than the value you just replaced.

You can make the index call work for lists that have no duplicate values by taking the index before you do the first replacement:

def selection_sort(xs)
  len = xs.length
  len.times do |i|
    low = xs[i...len].min
    tmp = xs[i]
    tmpindex = xs.index(low)
    xs[i] = low
    xs[tmpindex] = tmp
  end
  xs
end

However, since the lists that you are testing do have duplicate values, you need to use rindex to get the proper offset, since you can otherwise get an index outside of the bounds of your i...len range.

If you wanted to use index on lists that can contain multiple values, you have to make sure that you will only find the low value in the slice you're currently operating on, then offset it by the slice start position:

def selection_sort(xs)
  xs.length.times do |i|
    slice = xs[i..-1]
    low, tmp = slice.min, xs[i]
    xs[i], xs[i + slice.index(low)] = low, tmp
  end
  xs
end

Additionally, by getting the index from slice rather than from xs, we don't have to worry about changes in xs resulting in us getting an incorrect index for low.