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

i working through basic algorithm exercises, , confused implementation of selection sort:

def selection_sort(xs)   len = xs.length   len.times |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 use xs[xs.index(low)] = tmp instead of xs[xs.rindex(low)] = tmp, function not work on 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 mind, should not matter since index index whether coming right or left. wouldn't using rindex vs index change flow (for duplicate entries), still output ordered list?

what overlooking?

what's happening you're testing index after you've reassigned low value, not before you've reassigned value in low value's new position. so, let's consider:

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

now, assign xs[i] = low, means array looks [4,3,1,1]. @ point, xs.index(1) return 2, since put low value in position! using rindex gets 3, since find value used low value, rather value replaced.

you can make index call work lists have no duplicate values taking index before first replacement:

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

however, since lists testing have duplicate values, need use rindex proper offset, since can otherwise index outside of bounds of i...len range.

if wanted use index on lists can contain multiple values, have make sure find low value in slice you're operating on, offset slice start position:

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

additionally, getting index slice rather xs, don't have worry changes in xs resulting in getting incorrect index low.