Crie um programa que dado uma string, coloque as letras dela em ordem crescente pelo algoritmo bubble sort.

Passo 1

O enunciado pede um programa que receba uma string e ordene as letras dela em ordem crescente usando o algoritmo bubble sort. Vamos precisar entender como o bubble sort funciona e aplicar sobre a lista de caracteres da string.

Passo 2

Primeiro convertemos a string em uma lista de caracteres para podermos trocar elementos de posição, já que em muitas linguagens strings são imutáveis.
Depois aplicamos o bubble sort: repetimos passadas sobre a lista, e a cada passada comparamos pares de elementos adjacentes. Se o par estiver fora de ordem (o da esquerda for maior que o da direita), fazemos a troca.
Continuamos fazendo passadas até que nenhuma troca seja necessária, ou simplesmente fazemos n–1 passadas em uma lista de n caracteres, pois após cada passada o maior elemento ‘bolha’ para o fim.

Passo 3

Por fim, juntamos a lista ordenada de volta numa string e exibimos o resultado.

Resposta

def bubble_sort_string(s):
# Converte a string em lista de caracteres
chars = list(s)
n = len(chars)
# Bubble sort clássico
for i in range(n - 1):
# A cada iteração, o maior elemento da parte não ordenada vai para o fim
for j in range(n - 1 - i):
if chars[j] > chars[j + 1]:
# troca de lugar
chars[j], chars[j + 1] = chars[j + 1], chars[j]
# Reconstrói a string ordenada
return ‘’.join(chars)

Exemplo de uso

entrada = “exemplo”
resultado = bubble_sort_string(entrada)
print(resultado) # imprime “eelmopx”

Exercícios relacionados