...

# Python selection sort; i am trying to do this using recursion

Mitko
12-03-2011, 01:38 AM
Hey I am a first year unversity student and my project was to do a selection sort using recursion. I have figured out how to do it, but i don't know how to do it with recursion any help please?

def selsort(l):
"""
sorts l in-place.
PRE: l is a list.
POST: l is a sorted list with the same elements; no return value.
"""

for pos in range(len(l)-1):
largest = l[pos]
largestpos = pos
for i in range(pos+1, len(l)):
if l[i] > largest:
largest = l[i]
largestpos = i
l[pos], l[largestpos] = l[largestpos], l[pos]

l.reverse()

Mitko
12-03-2011, 01:41 AM
My main problem right now is that i have no idea what the algorithm would be. I am fairly good at translating algorithms to Python, but I am having trouble getting the basic algorithm for it
Any help would be much obliged.

Apothem
12-05-2011, 07:50 PM
It's not that hard to think up of. You just need to make sure the recursion is "iterating" the array at every element (not in any particular language, but you should get it):

ssort(array, start_pos, inc_pos, swap_pos) {
if(inc_pos >= array.length) {
u = array[swap_pos];
array[swap_pos] = array[start_pos];
array[start_pos] = u;
if(start_pos != array.length - 1) {
return ssort(array, start_pos+1, start_pos+1, start_pos+1);
}
return array;
}

if(array[inc_pos] < array[swap_pos]) {
return ssort(array, start_pos, inc_pos+1, inc_pos);
} else {
return ssort(array, start_pos, inc_pos+1, swap_pos);
}
}

sorted_array = ssort(array, 0, 0, 0)

Though I am not sure if this is the most efficient way. This is the fully recursive method I thought up of, but I think others tend to just use a combination of recursion and iteration (i.e. a for loop within the recursive function). Hope this helps.