Selection Sort Python

Question

This may seem like a simple question but when I attempted to implement selection sort in Python, I do not get a sorted list. Is there something wrong with my implementation? The subsetting may be a problem.

source = [4,2,1,10,5,3,100]
for i in range(len(source)):
  mini = min(source[i:]) #find minimum element
  min_index = source[i:].index(mini)-1 #find index of minimum element
  source[i:][min_index]= source[i:][0] #replace element at min_index with first element
  source[i:][0] = mini                  #replace first element with min element
print source

Answer 1

I think there were a couple issues.

First, when your do source[i:], I believe that returns a new array of the sub-elements requested and not part of the original array, thus if you modify it, your don't modify the original. Second, you were subtracting 1 from an index when you shouldn't.

source = [4,2,1,10,5,3,100]
for i in range(len(source)):
    mini = min(source[i:]) #find minimum element
    min_index = source[i:].index(mini) #find index of minimum element
    source[i + min_index] = source[i] #replace element at min_index with first element
    source[i] = mini                  #replace first element with min element
print source

This gives:

[1, 2, 3, 4, 5, 10, 100]

Answer 2

Here is how I would rewrite your code. Of course in Python I would just use list.sort() to sort a list, but here is a selection sort in Python.

We make a generator expression that returns tuples of (value, i) for a value and its index from the list. Then when min() evaluates to find minimum, it finds the lowest tuple value; since the value comes first in the tuple before the index, the value will be the important part, and min() will find the lowest value. (If there is a tie, min() will use the second part of the tuple, the index, as a tie-breaker. But for sort we don't care how ties are broken.)

Now, instead of searching through the sub-list to find the min value, and then searching through it again to figure out the index, we search through it once and get both min value and index.

But we don't actually care about the min value; we care about the index. So after min() is done, we just throw away the actual value but keep the index. Adjust the index to be correct in the whole list (not in the slice of the list) and then we can swap.

We use the standard Python idiom for swapping two values. Python will build a tuple object to be the intermediate, then unpack this tuple into the left-hand-side.

lst = [4,2,1,10,5,3,100]

for i_sortpos in range(len(lst)):
    # Make a generator expression to return (value, i) pairs.
    genexp = ((n, i) for i, n in enumerate(lst[i_sortpos:]))
    # Use genexp with min() to find lowest and its index.
    # (Use '_' for variable name for the actual value; we don't use it.)
    _, i_min = min(genexp)
    # Adjust index to be correct in full list.
    i_min += i_sortpos
    # Swap the number at i_sortpos with the lowest found.
    lst[i_sortpos], lst[i_min] = lst[i_min], lst[i_sortpos]

print(lst)

EDIT: And here is a refinement of the above. A slice from a list actually allocates a new list; our code here doesn't need a new list, it just needs a convenient way to examine a sublist. The itertools module offers a function, islice(), that returns an iterator that iterates over a slice of a list. This avoids repeatedly creating and destroying lists as we examine each sublist.

I believe this is the most efficient way to do selection sort in Python. (You could get rid of the part where we bind the generator expression to the name genexp and save a few microseconds... just make the call to min() a long one-liner. But it's not really worth the loss of readability.)

import itertools as it

lst = [4,2,1,10,5,3,100]

for i_sortpos in range(len(lst)):
    # Make a generator expression to return (value, i) pairs.
    # Use it.islice() for to look at sublist.
    genexp = ((n, i) for i, n in enumerate(it.islice(lst, i_sortpos, len(lst))))
    # Use genexp with min() to find lowest and its index.
    # (Use '_' for variable name for the actual value; we don't use it.)
    _, i_min = min(genexp)
    # Adjust index to be correct in full list.
    i_min += i_sortpos
    # Swap the number at i_sortpos with the lowest found.
    lst[i_sortpos], lst[i_min] = lst[i_min], lst[i_sortpos]

print(lst)