Почему эта программа выбора-сортировки на питоне работает некорректно?

Я написал реализацию сортировки выбором, которая не работает. Я не могу понять, почему.

#!/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],

Также может кто-нибудь объяснить, почему я должен ставить #!/usr/bin в начале этой программы?


python sorting selection-sort
person Lucifer    schedule 14.03.2017    source источник
comment
Можете ли вы предоставить более подробную информацию?   -  person Jesse    schedule 14.03.2017
comment
Первая строка должна читаться как #!/usr/bin/env python. Это хеш-банг или шебанг. Хотя алгоритм глючит   -  person slezica    schedule 14.03.2017
comment
@slezica Это должно сработать.   -  person Lucifer    schedule 14.03.2017
comment
Примечание. Не используйте list в качестве имени переменной, так как это функция Python.   -  person Martin Evans    schedule 14.03.2017
comment
получил это спасибо. @МартинЭванс   -  person Lucifer    schedule 14.03.2017

Ответы (1)


arrow_upward
1
arrow_downward

С вашим кодом после каждой второй итерации результатом было следующее:

[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

Как вы можете ясно видеть, он игнорирует последний элемент!

xrange в основном генерирует от начала до конца-1 (xrange(начало,конец))!

Внутренний цикл должен иметь диапазон от i+1 до n, а не 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

Пример,

Вход:

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

Выход:

0 2 3 7 12 22 25 43 77 87

Использование #!/usr/bin в начале этой программы можно легко понять по вики-ссылке, опубликованной в комментариях. Это дало бы четкое представление о том же самом!

Надеюсь, поможет!

person Keerthana Prabhakaran    schedule 14.03.2017
comment
Да! Спасибо, Киртана, но не могли бы вы подробно рассказать, почему i+1 to n, а не n-1? - person Lucifer; 14.03.2017
comment
потому что вы игнорировали последний элемент во время итерации! Я добавил правки! Это ответило на ваш вопрос? - person Keerthana Prabhakaran; 14.03.2017
comment
xrange(N) генерирует числа от 0 до N -1 (не N). Следовательно, xrange(n-2) предоставляет числа от 0 до n-3 и т. д. - person Dmitry; 14.03.2017