View Full Version : Python selection sort; i am trying to do this using recursion

Mitko

12-03-2011, 12: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, 12: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, 06: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.

Powered by vBulletin® Version 4.2.2 Copyright © 2015 vBulletin Solutions, Inc. All rights reserved.