Selection sort algorithm in Python

Question

I'm learning basic algorithms and implementing them in Python. Critiques needed/welcome.

import pudb; pu.db
import random
def selection_sort(list_):
    """Implement selection_sort algorithm: iterate L to R in list, grab value
    if greatest and inserting into correct pos. After each loop, decrement
    length of iterated list by 1"""
    val_list, greatest = list(range(len(list_))), 0
    for num in range(len(list_)):
        greatest = val_list[-1]
        for val in val_list:
            if list_[greatest] < list_[val]:
                greatest = val
        if list_[greatest] > list_[val_list[-1]]:
            list_.insert(val, list_.pop(greatest))
            val_list.remove(val)
    return list_

if __name__ == '__main__':
    unsorted = list(range(9))
    random.shuffle(unsorted)
    assert selection_sort(unsorted) == list(range(9))

Answer 1

Most of my comments on your previous question apply here too, so I'll just summarize them quickly:

1. Debugging code that you forgot to remove.

2. Docstring written from the implementer's point of view.

3. Variable name respelled to avoid shadowing a built-in.

4. Test case not organized into a unit test.

5. Test case not very stringent (just 9 items).

In addition:

1. Given an array of length n, your algorithm makes n passes over the array, and in pass i it finds the ith largest item in the array (which at that point in the algorithm is the largest item in the first n − i positions) and swaps it into the position n − i − 1. This ought to be simple, but it's implemented in a very complex way, via the list val_list of indexes.

   Here's a much simpler implementation:

   def selection_sort(seq):
       """Sort the mutable sequence seq in place and return it."""
       for i in reversed(range(len(seq))):
           # Find the index of greatest item in seq[:i+1].
           greatest = 0
           for j in range(1, i + 1):
               if seq[j] > seq[greatest]:
                   greatest = j
           seq[i], seq[greatest] = seq[greatest], seq[i]
       return seq
   

   Note that I've avoided testing seq[greatest] > seq[i] before doing the swap, because I know that the only way this condition can fail is if greatest == i, and then the swap has no effect. So it's simplest to skip the test.

   I could simplify this still further using Python's built-in function max:

   def selection_sort(seq):
       """Sort the mutable sequence seq in place and return it."""
       for i in reversed(range(len(seq))):
           greatest = max(range(i + 1), key=seq.__getitem__)
           seq[i], seq[greatest] = seq[greatest], seq[i]
       return seq
   

   But this seems like it's avoiding the spirit of the exercise: I mean, if I can use max, then why not sorted?