sorting an alphanumeric string in Python- selection sort, bubble sort

Question

The question is
Write a program to sort a string without using built in method. Input: "a390testai" output: "039aaiest"

I have looked at some forums to find answer for this. I found this forum In Python, how can I naturally sort a list of alphanumeric strings such that alpha characters sort ahead of numeric characters? but it does not look like any of the solutions were using selection or bubble sort. My questions are:
1) When dealing with such a problem do I have to 1st convert the string to a list? For example: str=list("exam123ple") ? To avoid "TypeError: 'str' object does not support item assignment"

2) I tried using selection sort and bubble sort but they are not returning intended result.

   #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

Thanks in advance for your help and explanation.

`str` is already iterable through some implementations make it easier to turn it to a list. I would recommend merge sort. — Error - Syntactical Remorse, Apr 18 '19 at 18:58

score 1 · Answer 1 · answered Apr 18 '19 at 19:30

1

Bubble sort needs more than one pass. Each time through, you go through one less element, since the last one has "bubbled" into place.

In your selection sort, s.index returns the index of the first matching item. So if your string has duplicate letters it returns the wrong one. You need to search inside the [i:] range and add i, to find the right instance.

answered Apr 18 '19 at 19:30

AShelly

34,686
15
91
152

Your explanation makes sense, that string had duplicates. Thanks – Sheikh Rahman Apr 18 '19 at 19:42

score 0 · Accepted Answer · answered Apr 18 '19 at 19:30

Yes, you have to use list as strings are immutable and you can't change parts of them. Here is an example of bubble sort.

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))

sorting an alphanumeric string in Python- selection sort, bubble sort

2 Answers2