Алгоритм сортировки

Question

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

Прохожу курс 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

Вот как это выглядит:

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

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

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

Answer 1

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

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

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

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

БЛОГ НА HUSL

Алгоритм сортировки

Ответы (1 шт):