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))
    return list_

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

1 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 ni positions) and swaps it into the position ni − 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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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