0

Не могу понять в чём проблема.

Прохожу курс python, и по заданию надо написать свой алгоритм сортировки. Я написал такой(по моей логике цикл проходит по каждому элементу списка и меняет его местами с минимальным элементом оставшегося среза списка):

    a = [78, -32, 5, 39, 58, -5, -63, 57, 72, 9, 53, -1, 63, -97, -21, -94, -47, 57, -8, 60, -23, -72, -22, -79, 90, 96,
     -41, -71, -48, 84, 89, -96, 41, -16, 94, -60, -64, -39, 60, -14, -62, -19, -3, 32, 98, 14, 43, 3, -56, 71, -71,
     -67, 80, 27, 92, 92, -64, 0, -77, 2, -26, 41, 3, -31, 48, 39, 20, -30, 35, 32, -58, 2, 63, 64, 66, 62, 82, -62, 9,
     -52, 35, -61, 87, 78, 93, -42, 87, -72, -10, -36, 61, -16, 59, 59, 22, -24, -67, 76, -94, 59]

n = len(a)

for i in range(n):
     a[i], a[a.index(min(a[i:]))] = min(a[i:]), a[i]
print(a)

но он, по непонятной мне причине, возвращает исходный список.

Далее, по совету, я задал индекс минимального значения в отдельную переменную и код стал такой:

a = [78, -32, 5, 39, 58, -5, -63, 57, 72, 9, 53, -1, 63, -97, -21, -94, -47, 57, -8, 60, -23, -72, -22, -79, 90, 96,
     -41, -71, -48, 84, 89, -96, 41, -16, 94, -60, -64, -39, 60, -14, -62, -19, -3, 32, 98, 14, 43, 3, -56, 71, -71,
     -67, 80, 27, 92, 92, -64, 0, -77, 2, -26, 41, 3, -31, 48, 39, 20, -30, 35, 32, -58, 2, 63, 64, 66, 62, 82, -62, 9,
     -52, 35, -61, 87, 78, 93, -42, 87, -72, -10, -36, 61, -16, 59, 59, 22, -24, -67, 76, -94, 59]

n = len(a)

for i in range(n):
     b = a.index(min(a[i:]))
     a[i], a[b] = a[b], a[i]
print(a)

Но и тут не выдало желаемого результата. Пошёл смотреть в визуализаторе как проходит цикл.

И первые три итерации всё работает как надо, а на четвёртой(i = 3) почему то b = a.index(min(a[i:])) принимает значение вне указанного среза: b = 2

Вот как это выглядит: введите сюда описание изображения

и дальше следовательно всё идёт наперекосяк.

Подскажите в чём причина? почему срез не работает или что то другое? Я не столько хочу решить задание и написать работающий алгоритм, сколько понять почему приведенные мной коды не работают.

Заранее спасибо.

1 ответ 1

1

Потому что вы ищете индекс во всём списке, а не в его остатке. При наличии одинаковых чисел будут проблемы (в данном случае спотыкается на повторе значения -94). К счастью, у .index() есть параметр для начала поиска

 b = a.index(min(a[i:]), i)

решит задачу.

Вы осознаете, что такой алгоритм довольно медленный из-за двукратного прохода по списку? По сути это алгоритм сортировки выбором, для её осуществления достаточно на каждом проходе один раз пройтись по остатку массива, запоминая индекс минимума вручную.

2
  • Спасибо! Я только начал знакомство с алгоритмами, поэтому пока что-то осознаю что-то не очень. А по теме индекса, если можно задать начало поиска, то нужен ли тогда срез a[i:]? я думал он будет выполнять эту функцию, или что он тогда делает? 19 авг 2022 в 4:17
  • Да, срез нужен для поиска минимума только в этой части массива, у функции минимума нет возможности ограничить диапазон
    – MBo
    19 авг 2022 в 5:20

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.