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?
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!