Selection Sort in Python not sorting

Question

I wrote a program for selection sort by first creating a function that finds the minimum element in the array. Then I iterate through the array placing the smallest element in the correct place in the array while replacing the smallest element. This is my code :

a=[int(input()) for _ in range(6)]
def smallest_element(arr,x):
    smallest = arr[x]
    d = x
    for j in range(x+1,len(arr)):
        if arr[j] < smallest:
            smallest = arr[j]
            d = j
    return d
for i in range(0,len(a)):
    c = a[i]
    if(c > a[smallest_element(a,i)]):
        a[i] = a[smallest_element(a,i)]
        a[smallest_element(a,i)] = c
print(a)

But the problem is my array is not getting sorted.
Input - [5,2,4,6,1,3]
Output - [5,2,4,6,1,3]

Endzeit · Accepted Answer · 2019-11-17 15:12:59Z

The error seems to be in your loop.

You assign the smallest value found to the current index.

a[i] = a[smallest_element(a,i)]

You then assign the value that was originally stored to the index where the smallest element is located.

a[smallest_element(a,i)] = c

You do however re-calculate the index of the smallest element, which always is the current index - because you just copied the smallest value to the current index.

first approach

I know of two solutions to this problem. First you may only search the index of the smallest element once per loop round. That way you do not re-calculate the index and write to the correct position.

for i in range(0, len(a)):
    c = a[i]
    indexOfSmallestElement = smallest_element(a, i)
    smallestElement = a[indexOfSmallestElement]

    if c > smallestElement:
        a[i] = smallestElement
        a[indexOfSmallestElement] = c

second approach

Another solution is to search the element starting from the current index + 1 instead of the current index, and thus skipping the entry that you've already changed.

Exchange a[smallest_element(a, i)] = c with a[smallest_element(a, i + 1)] = c.

I do however recommend to use the first approach as it recudes the amount of times the array is iterated over.

teddcp · Accepted Answer · 2019-11-17 12:32:01Z

First, in your code, you have called the smallest_element(arr,x) 3 times which will consume more time for larger arrays. Instead we can store that value to a variable rather calling 3 times.

Secondly you are swapping 2 times one in function body and in if block.

So in the function body , find the current smallest element. Then return that index to main.Then if it is smaller than the present element (in the main for loop), then swap it.

#Find the smallest element
def smallest_element(arr,x):
    small = x
    for j in range(x+1,len(arr)):
        if arr[j] < arr[small]:
            small=j
    return small

#now compare  it with the current element  
for i in range(0,len(a)):
    c = a[i]
    curr=smallest_element(a,i)

    if(c > a[curr] and curr!=i):
        a[i] = a[curr]
        a[curr] = c


    print(a)

Collectives™ on Stack Overflow

Selection Sort in Python not sorting

2 Answers 2

first approach

second approach

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

first approach

second approach

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related