Selectionsort не выводит правильный результат Python

Question

Здравствуйте, я боролся с реализацией этой сортировки уже несколько дней. Я чувствую, что мой код близок к этому, но не могу понять, почему я его не получаю.

Вот мой код с комментариями

def selectionSort(aList):

    #For each index in the list...
    for i in range(len(aList)):

        #Assume first that current item is already correct...
        minIndex = i

        #For each index from i to the end...
        for j in range(i + 1, len(aList)):

            if aList[j] >= aList[j - 1]:
                break
            aList[j], aList[j - 1] = aList[j - 1], aList[j]
            minIndex = aList.index(aList[j - 1])

        #Save the current minimum value since we're about
        #to delete it
        minValue = aList[minIndex]

        #Delete the minimum value from its current index
        del aList[minIndex]

        #Insert the minimum value at its new index
        aList.insert(i, minValue)

    #Return the resultant list
    return aList

Это результат получаю

[4, 2, 1, 3, 5]

Вместо этого:

[1, 2, 3, 4, 5]

заранее спасибо за помощь

Answer 1

Вот рабочий код, ребята:

def selectionSort(aList):

    #For each index in the list...
    for i in range(len(aList)):

        minIndex = i

        #For each index from i+1 to the end...
        for j in range(i + 1, len(aList)):

            if aList[minIndex] > aList[j]:
            minIndex = j

        #Save the current minimum value since we're about
        #to delete it
        minValue = aList[minIndex]

        #Delete the minimum value from its current index
        del aList[minIndex]

        #Insert the minimum value at its new index
        aList.insert(i, minValue)

    #Return the resultant list
    return aList

Еще раз спасибо. Не могу поверить, что только две строки кода дали мне кошмар. pheew

Answer 2

Вам не нужно удалять и вставлять, просто поменяйте их!

def selectionSort(aList):

        #For each index in the list (not the last one)
        for i in range(len(aList)-1):

            #initialized minIndex
            minIndex = i

            #For each index from i+1 to the end...
            for j in range(i + 1, len(aList)):
                #find the min of the list and update minIndex
                if aList[j] < aList[minIndex]:
                    minIndex = j;

            #if minIndex changed, swap i and minIndex values
            if minIndex != i:
                aList[i], aList[minIndex] = aList[minIndex], aList[i]

        #Return the resultant list
        return aList

Answer 3

for j in range(i + 1, len(aList)):

        if aList[j] >= aList[j - 1]:
            break
        aList[j], aList[j - 1] = aList[j - 1], aList[j]
        minIndex = aList.index(aList[j - 1])

Сортировка выбора - это сортировка путем итеративного поиска минимального элемента в списке. Просто установите первый элемент как минимальный, итерируйте по списку, если текущий элемент меньше минимального, затем запишите его как минимальный и запишите его индекс. Часть после верна.