Selection Sort in Python not working

Question

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!

Anand S Kumar · Accepted Answer · 2015-06-26 19:17:05Z

2

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]

answered Jun 26, 2015 at 19:17

Anand S Kumar

91.4k18 gold badges196 silver badges179 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Nate Bailey Over a year ago

Thank you! That makes so much sense. Much appreciated

Anand S Kumar Over a year ago

You are welcome, also please do remember to accept answers, if you think they helped you resolve your issue, would help the community.

Collectives™ on Stack Overflow

Selection Sort in Python not working

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related