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?