сортировка буквенно-цифровой строки в Python - выборка, пузырьковая сортировка

Question

Вопрос
Напишите программу для сортировки строки без использования встроенного метода. Вход: "a390testai" вывод: "039aaiest"

Я заглянул на некоторые форумы, чтобы найти ответ на этот вопрос. Я нашел этот форум В Python, как я могу естественным образом отсортировать список буквенно-цифровых строк так, чтобы буквенные символы сортировались перед числовыми символами? , но не похоже, чтобы какое-либо из решений использовало выделение или пузырьковую сортировку. Мои вопросы:
1) Когда я сталкиваюсь с такой проблемой, нужно ли сначала преобразовывать строку в список? Например: str = list ("exam123ple")? Чтобы избежать "TypeError: объект 'str' не поддерживает назначение элемента"

2) Я пытался использовать выборочную сортировку и пузырьковую сортировку, но они не возвращают ожидаемый результат.

   #Selection sort
s="a390testai"
s=list(s)  # convert to list


for i in range(len(s)):
    min_val=min(s[i:])
    min_val_pos=s.index(min_val)

    s[i],s[min_val_pos]=s[min_val_pos],s[i]

print('s',s)

#Bubble sort
bs="a390testai"

bs=list(bs)
for i in range(0,len(bs)-1):
       if bs[i]>bs[i+1]:
           bs[i], bs[i+1]=bs[i+1],bs[i]

print(bs)

039testaai >> selection sort
390aestait >> bubble sort

Заранее спасибо за помощь и объяснения.

Answer 1

Для сортировки по пузырьку требуется более одного прохода. Каждый раз, когда вы проходите, вы проходите на один элемент меньше, так как последний «всплыл» на место.

В выбранной вами сортировке s.index возвращает индекс первого соответствующего элемента. Таким образом, если ваша строка содержит повторяющиеся буквы, она возвращает неправильную. Вам нужно искать внутри диапазона [i:] и добавлять i, чтобы найти правильный экземпляр.

Answer 2

Да, вы должны использовать список, поскольку строки неизменяемы, и вы не можете изменять их части.Вот пример пузырьковой сортировки.

s = list('a390testai')

is_sorted = False
while not is_sorted:
    for i in range(len(s)-1):
        if s[i] > s[i+1]:
            s[i+1], s[i] = s[i], s[i+1]
            break
    else:
        is_sorted=True

print("".join(s))