4
\$\begingroup\$

How does this recursive selection sort look to everyone here? Am I missing anything 'pythonic' about the way I have done it?

def selection_sort(li, out=None):
    if out is None:
        out = []    
        li = li[:]

    if len(li) == 0:
        return out

    small = min(li)
    li.remove(small)
    out.append(small)
    return selection_sort(li, out)
\$\endgroup\$
3
\$\begingroup\$
def selection_sort(li, out=None):

I dislike the name "li," I think abbreviations are bad.

    if out is None:
        out = []    
        li = li[:]

Rather then using the out parameter to do this, I suggest creating a seperate internal function which is called. Otherwise, it looks like the caller to the function might reasonable pass out = something, when its only meant to be used internally.

    if len(li) == 0:
        return out

Better to use if not li:

    small = min(li)
    li.remove(small)
    out.append(small)
    return selection_sort(li, out)

Its a little hard to gauge this code because you are doing two things you shouldn't, using recursion when its not necessary and implementing your own sort routine. But if you are doing so for learning purposes that's fine.

EDIT

Iterative solution:

def selection_sort(li):
    li = li[:]
    out = []

    while li:
        smallest = min(li)
        li.remove(smallest)
        out.append(smallest)

    return out

But why is this better than the recursive solution:

  1. There is a limit to your stack space. If you try to sort a large list using this function you'll get a RuntimeError
  2. Calling a function has extra overhead that iterating in a loop does not, the iterative version will be faster
  3. A loop is usually easier to read then recursion. The while loop makes it easy to see whats doing on, whereas the recursive version requires some thought about the code to see the logic.
\$\endgroup\$
  • \$\begingroup\$ Aye learning, and why not recursion for this situation? \$\endgroup\$ – Jakob Bowyer Jun 7 '11 at 19:06
  • \$\begingroup\$ @Jakob, see edit \$\endgroup\$ – Winston Ewert Jun 7 '11 at 19:18
  • \$\begingroup\$ +1: amplifying "don't have output parameters". Given Python's ability to return arbitrary tuples, there is never a reason to use an output parameter. For example: return (a_list, a_dict_of_dicts, status) is valid and idiomatic. Also pay attention to the difference between list.sort() and list.sorted() in the standard library (hint: one returns a value, the other doesn't, why?) \$\endgroup\$ – msw Jun 17 '11 at 1:09
  • \$\begingroup\$ @msw, I wouldn't quite say "never." For example, numpy has reasonable use of out parameters for efficiency reasons. \$\endgroup\$ – Winston Ewert Jun 17 '11 at 23:14
  • \$\begingroup\$ Fair 'nuff. How about "unless you know whyfor"? \$\endgroup\$ – msw Jun 18 '11 at 10:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.