Selection sort implementation in python-CodePudding

I am trying to implement a selection sort in python, which I have done so far. The output of this function is not sorted at all. What do you think I am doing wrong here? as I am storing the index of the smallest element in the array and swapping that. If someone can point out the flaw in my logic this would serve as an example for others doing the same thing.

def selection_sort(array):
    for i in range(len(array)):
        index = 0
        smallest = array[i]
        for j in range(len(array)):
            if array[j] < smallest:
                smallest = array[j]
                index = j
        temp = array[i]
        array[i] = smallest
        array[index] = temp
    return array


to_sort = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0]
print(selection_sort(to_sort))

Output: [44, 6, 2, 1, 5, 63, 87, 283, 4, 99, 0]

CodePudding user response：

Selection sort looks ahead from the current index i, so the inner loop should only iterate over that range. Secondly the index should be initialised at the current i, as it must indicate where smallest comes from:

def selection_sort(array):
    for i in range(len(array)):
        index = i  # corrected
        smallest = array[i]
        for j in range(i   1, len(array)):  # corrected
            if array[j] < smallest:
                smallest = array[j]
                index = j
        temp = array[i]
        array[i] = smallest
        array[index] = temp
    return array

CodePudding user response：

There is some optimization of code: one if instead of nested for if construction that makes your code O(N) instead of O(N^2)

def selection_sort(array):
    for i in range(len(array) - 1):
        index = i  # already corrected
        smallest = array[i]

        # only one if instead for if 
        if min(array[i   1:]) < smallest:
            smallest = min(array[i   1:]) 
            index = array[i:].index(min(array[i   1:]))   i

        temp = array[i]
        array[i] = smallest
        array[index] = temp
    return array

Hope its helpful.