Selection Sort (low to high) python

Question

I am trying to write a selection sort algorithm for sorting lists of numbers from lowest to highest.

def sortlh(numList):
    if type(numList) != list:
        print("Input must be a list of numbers.")
    else:
        inf = float("inf")
        sortList = [0]*len(numList)
        count = 0
        while count < len(numList):          
            index = 0
            indexLowest = 0
            lowest = numList[index]
            while index < (len(numList) - 1):
                if numList[index + 1] < numList[index]:
                    lowest = numList[index + 1]
                    indexLowest = index + 1
                    index = index + 1
                else:
                    index = index + 1
            sortList[count] = lowest
            numList[indexLowest] = inf
            count = count + 1
    return sortList

When I run this code on:

sortlh([9,8,7,6,5,4,3,2,1])

I get (as expected):

[1, 2, 3, 4, 5, 6, 7, 8, 9]

However, when I try another example, I get:

sortlh([1,3,2,4,5,7,6,9,8])

[8, 6, 9, 2, 4, 5, 7, 1, 3]

Does anyone see what is going on here?

Why are you doing this? If its for anything other than trying to improve your skills you should look here, the docs for the builtin sorted() function. — wnnmaw
– wnnmaw, Commented Dec 23, 2013 at 22:26
As a side note, the kind of type-checking you do up top is usually not helpful. In this case, your code would have already raised a nice TypeError explaining that numList isn't iterable, but instead you're making it print some output with less information and return None, and meanwhile you're excluding all other types of sequences (even subclasses of list) for no good reason. — abarnert
– abarnert, Commented Dec 23, 2013 at 22:27
Also, instead of "pre-filling" sortList, why not just do sortList = [], then sortList.append(lowest), and while len(sortList) < len(numList), eliminating count entirely? — abarnert
– abarnert, Commented Dec 23, 2013 at 22:29
When you do lst = [] you have an empty list. Trying to access it with any index will give an out of bounds error. But you can then do lst.append() and that works fine. — steveha
– steveha, Commented Dec 23, 2013 at 22:54
In case you're curious, I have a moderately large collection of sorts in Python and/or Cython at stromberg.dnsalias.org/~dstromberg/sort-comparison — dstromberg
– dstromberg, Commented Dec 23, 2013 at 22:59

steveha · Accepted Answer · 2013-12-23 22:53:24Z

Here is how I would suggest rewriting your program.

def sortlh(lst_input):
    lst = list(lst_input) # make a copy of lst_input
    i = 0
    while i < len(lst):
        j = i + 1
        i_lowest = i
        lowest = lst[i_lowest]
        while j < len(lst):
            if lst[j] < lowest:
                i_lowest = j
                lowest = lst[i_lowest]
            j += 1
        lst[i], lst[i_lowest] = lst[i_lowest], lst[i]  # swap
        i += 1
    return lst

test = [9,8,7,6,5,4,3,2,1]
assert sortlh(test) == sorted(test)
test = [1,3,2,4,5,7,6,9,8]
assert sortlh(test) == sorted(test)

We don't test the type of the input. Anything that acts like a list will work, and even an iterator will work.
We don't "mutate" the original input list. We only work on a copy of the data.
When we find the lowest number, we swap it with the first number, and then only look at the remaining numbers. Thus we have less work to do on each loop as we have fewer and fewer unsorted numbers.

EDIT:

If you are a beginner, this part might seem too tricky. If it confuses you or you don't like it, just ignore it for now.

This is a more-advanced way to solve this problem in Python. The inner loop simply finds the lowest number and the index of the lowest number. We can use the Python built-in function min() to do this!

We build a "generator expression" that loops over the list, yielding up tuples. Each tuple is the number and its position. Since we want lower numbers to sort lower, we put the number first in the tuple so that min() can properly compare the tuples. Then min() will find the lowest tuple and we get the value and index.

Also, the outer loop is now a for loop with enumerate rather than a while loop using indexing.

def sortlh(lst_input):
    lst = list(lst_input) # make a copy of lst_input
    for i, x in enumerate(lst):
        lowest, i_lowest = min((n, j) for j, n in enumerate(lst) if j >= i)
        lst[i], lst[i_lowest] = lst[i_lowest], lst[i]  # swap
    return lst

test = [9,8,7,6,5,4,3,2,1]
assert sortlh(test) == sorted(test)
test = [1,3,2,4,5,7,6,9,8]
assert sortlh(test) == sorted(test)

Collectives™ on Stack Overflow

Selection Sort (low to high) python

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related