Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Results 1 to 3 of 3
  1. #1
    New to the CF scene
    Join Date
    Dec 2011
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts

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

    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()

  • #2
    New to the CF scene
    Join Date
    Dec 2011
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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.

  • #3
    Regular Coder Apothem's Avatar
    Join Date
    Mar 2008
    Posts
    380
    Thanks
    36
    Thanked 25 Times in 25 Posts
    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):

    Code:
    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.
    Last edited by Apothem; 12-05-2011 at 07:55 PM.


  •  

    Tags for this Thread

    Posting Permissions

    • You may not post new threads
    • You may not post replies
    • You may not post attachments
    • You may not edit your posts
    •