Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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))
share|improve this question
add comment

1 Answer

up vote 8 down vote accepted

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?

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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