Selection Sort in Python working in place-CodePudding

I have written this selection sort algorithm which works "in place". I want to sort the following list: [8,3,1,7,4,10,5,9,2,6]. When I run the algorithm I get the following output: [10, 2, 3, 4, 5, 6, 7, 8, 9, 10].

def selectionSortInPlace(listToSort):
    index = 0
    for i in range(0, len(listToSort)):
        value = listToSort[i]
        index = 0
        for j in range(i 1, len(listToSort)):
            if listToSort[j] < value:
                value = listToSort[j]
                index = j
        temp = listToSort[i]
        listToSort[i] = value
        listToSort[index] = temp
    
unsortedList = [8,3,1,7,4,10,5,9,2,6]
selectionSortInPlace(unsortedList)
print(unsortedList)

CodePudding user response：

Your bug is that you set index = 0 and value = listToSort[i], and proceed with the swap even if the for loop didn't update those values.

One way to fix this would be to set these values to None and then continue the loop if they don't have real values:

def selectionSortInPlace(listToSort):
    for i in range(0, len(listToSort)):
        value = None
        index = None
        for j in range(i 1, len(listToSort)):
            print(j)
            if listToSort[j] < value:
                value = listToSort[j]
                index = j
        if index is None:
            continue
        temp = listToSort[i]
        listToSort[i] = value
        listToSort[index] = temp

Another option would be to set index = i so that it stays synchronized with value even if the for loop never updates either (this simply makes the swap a no-op in that case):

def selectionSortInPlace(listToSort):
    for i in range(0, len(listToSort)):
        index = i
        value = listToSort[i]
        for j in range(i 1, len(listToSort)):
            print(j)
            if listToSort[j] < value:
                value = listToSort[j]
                index = j
        temp = listToSort[i]
        listToSort[i] = value
        listToSort[index] = temp

You can simplify the code a bit by making use of enumerate (which lets you iterate over the index and the value automatically rather than having to iterate by index and then look up the value), and tuple assignment (which lets you do the swap without a temp variable):

def selectionSortInPlace(listToSort):
    for i, a in enumerate(listToSort):
        k = i
        for j, b in enumerate(listToSort[i 1:], i 1):
            if b < a:
                k, a = j, b
        listToSort[i], listToSort[k] = listToSort[k], listToSort[i]

You can make it even simpler using the min function, since that will automatically do the inner iteration to find the smallest value for you:

def selectionSortInPlace(listToSort):
    for i, _ in enumerate(listToSort):
        j, _ = min(enumerate(listToSort[i:], i), key=lambda j_: j_[1])
        listToSort[i], listToSort[j] = listToSort[j], listToSort[i]