Why doesn't this selection-sort program in python work correctly?

Question

I wrote a selection sort implementation that doesn't work. I can't figure out why.

#!/usr/bin
def sel_sort(list):
    for i in xrange(n-2):
        imin=i
        for j in xrange(i+1,n-1):
            if list[j]<list[imin]:
                imin=j
        list[imin],list[i]=list[i],list[imin]

n=int(raw_input("Enter number of elements : "))
x=[]
for t in xrange(n):
    x.append(int(raw_input()))

sel_sort(x)

for k in xrange(n):
    print x[k],

Also could anyone explain why I should place #!/usr/bin at the beginning of this program?

The first line should read #!/usr/bin/env python. It's a hashbang, or shebang. The algorithm is buggy though — salezica
– salezica, Commented Mar 14, 2017 at 16:25
Note: Don't use list as a variable name, as it is a Python function. — Martin Evans
– Martin Evans, Commented Mar 14, 2017 at 16:30

Community · Accepted Answer · 2017-05-23 12:09:26Z

1

With your code, after every other iteration the following was the result,

[0, 3, 77, 25, 87, 22, 12, 7, 2, 43]
[0, 2, 77, 25, 87, 22, 12, 7, 3, 43]
[0, 2, 3, 25, 87, 22, 12, 7, 77, 43]
[0, 2, 3, 7, 87, 22, 12, 25, 77, 43]
[0, 2, 3, 7, 12, 22, 87, 25, 77, 43]
[0, 2, 3, 7, 12, 22, 87, 25, 77, 43]
[0, 2, 3, 7, 12, 22, 25, 87, 77, 43]
[0, 2, 3, 7, 12, 22, 25, 77, 87, 43]
[0, 2, 3, 7, 12, 22, 25, 77, 87, 43]
0 2 3 7 12 22 25 77 87 43

As you can clearly see, it ignores the last element!

xrange basically generates from start to end-1 (xrange(start,end))!

The inner loop should be of range i+1 to n and not n-1

def sel_sort(list):
    for i in xrange(n-2):
        imin=i
        #here range is i+1 to n
        for j in xrange(i+1,n):
            if list[j]<list[imin]:
                imin=j
        list[imin],list[i]=list[i],list[imin]
        print list

Example,

Input:

x=[7, 3, 77, 25, 87, 22, 12, 0, 2, 43]

Output:

0 2 3 7 12 22 25 43 77 87

The use of #!/usr/bin at the beginning of this program can be well understood by wiki link shared in comments. This would give a clear insight about the same!

Hope it helps!

edited May 23, 2017 at 12:09

CommunityBot

11 silver badge

answered Mar 14, 2017 at 16:29

Keerthana Prabhakaran

3,8071 gold badge16 silver badges25 bronze badges

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

3 Comments

Lucifer Over a year ago

Yes! Thank You Keerthana, but could you provide details why i+1 to n and not n-1 ?

Keerthana Prabhakaran Over a year ago

because you were ignoring the last element while iterating! I've added the edits! Did that answer you question?

Dmitry Over a year ago

xrange(N) generates numbers from 0 to N -1 (not N). Consequently xrange(n-2) provides numbers form 0 to n-3 etc.

Collectives™ on Stack Overflow

Why doesn't this selection-sort program in python work correctly?

1 Answer 1

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related