CODEWITHSUNDEEP
pythonalgorithmsorting
Nate Bailey
Nate Bailey

Reputation: 21

Selection Sort in Python not working

I'm working on learning algorithms, started with bubble sort and now on to selection sort. Here's the code I'm working with:

test = [5, 3, 6, 1, 8, 7, 2, 4]

def selection_sort(items):
    for i in range(0, len(items)-1):
        minIndex = i
        for j in range(i + 1, len(items)):
            if items[j] < items[minIndex]:
                minIndex = j
            if minIndex != i:
                items[i], items[minIndex] = items[minIndex], items[i]

print("Before: ", test)
selection_sort(test)
print("After: ", test)

The problem is that the output I get from this is: [1, 3, 4, 2, 5, 6, 7, 8] When I run it again I get the correct output of: [1, 2, 3, 4, 5, 6, 7, 8]

Any idea why it gets caught up? Thanks!

Upvotes: 2

Views: 83

Answers (1)

Anand S Kumar
Anand S Kumar

Reputation: 90999

You are actually doing it wrongly, you are swapping the ith position element with minIndex , in every iteration, even if its not the actual minIndex (You are doing it inside the inner loop)

You need to do that swap outside the inner loop, so that in the inner loop you find out the index with the minimum value element and then swap ith and minIndex position elements.

Example -

>>> test = [5, 3, 6, 1, 8, 7, 2, 4]
>>> def selection_sort(items):
...     for i in range(0, len(items)-1):
...         minIndex = i
...         for j in range(i + 1, len(items)):
...             if items[j] < items[minIndex]:
...                 minIndex = j
...         if minIndex != i:
...             items[i], items[minIndex] = items[minIndex], items[i]
...
>>> selection_sort(test)
>>> test
[1, 2, 3, 4, 5, 6, 7, 8]

Upvotes: 2

Related Questions