Selection sort algorythm using recursive definition

[kvard]

Hello,

I've stumbled upon question I can't solve on my own. What I need is to write a program in python that would perform selection sort, but here's trick - it has to be recursive.

So, for example I have
l = [3,2,1]
after using sort(l), l = [1,2,3]

I've this far:

def sort(l):
if len(l) <= 1:
return l
else:
l.append(#the largest element#)
return selsort(l[1:])

So, basically I don't know how to extract maximum element using recursion. If anyone knows how to do - pls help :)

Thanks in advance :)

[masterofpuppets]

hi,
here's a hint:

you can find the largest element using a for loop like this:

maxV = l[ 0 ]   # l is the array you call the function with
for el in l:
    if el > maxV:
        maxV = el

print maxV
# -> should output the largest number in the list

the tricky part in the recursion sort algorithm, at least for me, was that once you place the element in first place, you have to start from the second element the next time, so you'll need a counter that keeps track of which element you're currently checking. Here's what I mean:

selectionSort( [ 4, 2, 6 ] ) would do something like this:
1) find the largest/smallest element
2) replace it with the element in first/last place
3) call selectionSort( with the array starting from 1 not from 0, because 0 is already occupied by the largest/smallest element )

hope this doesn't make it too confusing :)

if you need some more help, just post a message with your code here and pls use code tags next time :)

[kvard]

Hi,

Thanks for the reply.

However, you confused me a little - isn't the whole point of recursions is not to use loops? At least it explained to me that way - a recursion would call function on itself many times, solving small parts of the problem.

[vegaseat]

A selection sort of a list of numbers is pretty simple. You start with two lists, let's call the original unsorted list the start_list and you have another list call it the end_list which is empty at the start.

If you want to sort ascending (lowest value first) you get the lowest value of start_list using lowest = min(start_list) and append it to the end_list with end_list.append(lowest). Now remove this value from the start_list with start_list.remove(lowest) and repeat until the start_list is empty and return the end_list with the sorted values.

The repeat can be done with a while loop using while len(start_list):, or you can replace the while loop with a recursive call to the sort function with the shortened start_list as an argument. In this case you have to use an if len(start_list) < 1: to leave the recursion and return the finished end_list.