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?