Faça um programa que leia
nomes inserindo-os em uma lista de forma ordenada utilizando a ideia do algoritmo insertion sort. No final, o programa deve mostrar todos os nomes ordenados alfabeticamente.
18. Crie um programa que dado uma string, coloque as letras dela em ordem crescente pelo algoritmo bubble sort.
19. Faça um programa que leia
nomes e ordene-os pelo tamanho utilizando o algoritmo selection sort
18. Crie um programa que dado uma string, coloque as letras dela em ordem crescente pelo algoritmo bubble sort.
19. Faça um programa que leia
Passo 1
O enunciado pede três programas separados, cada um usando um dos algoritmos de ordenação clássicos (insertion sort, bubble sort e selection sort) para ordenar sequências de dados (nomes ou caracteres). Vamos implementar cada um em Python do zero, sem usar funções de ordenação prontas.
Passo 2
Para o insertion sort de nomes em ordem alfabética, a ideia é manter a porção inicial da lista sempre ordenada. A cada iteração, pegamos o próximo nome e inserimos na posição correta, deslocando à direita os nomes maiores.
Implementamos a função insertion_sort_names(lst) que recebe uma lista de strings e a ordena in-place. Percorremos do segundo elemento até o fim, armazenamos o valor “key”, comparamos com os anteriores e deslocamos esses maiores até encontrar a posição de inserção.
Implementamos a função insertion_sort_names(lst) que recebe uma lista de strings e a ordena in-place. Percorremos do segundo elemento até o fim, armazenamos o valor “key”, comparamos com os anteriores e deslocamos esses maiores até encontrar a posição de inserção.
Passo 3
No bubble sort para os caracteres de uma string, vamos transformar a string em lista de caracteres, percorrer várias vezes essa lista trocando pares adjacentes fora de ordem, até não ocorrerem mais trocas. Esse processo garante que, a cada passagem, o maior caracter “borbulha” para o final.
Criamos a função bubble_sort_string(s) que faz essa transformação, aplica o bubble sort nos caracteres e devolve a nova string ordenada.
Criamos a função bubble_sort_string(s) que faz essa transformação, aplica o bubble sort nos caracteres e devolve a nova string ordenada.
Passo 4
No selection sort por tamanho de nome, tratamos uma lista de strings e para cada posição i, buscamos na sublista i…end o índice do nome de menor tamanho e fazemos a troca com a posição i. Repetimos até ordenar toda a lista.
Implementamos selection_sort_by_length(lst) que varre a lista, para cada i encontra min_index comparando len(lst[j]) e faz swap. O resultado é a lista ordenada ascendentemente pelo tamanho das strings.
Implementamos selection_sort_by_length(lst) que varre a lista, para cada i encontra min_index comparando len(lst[j]) e faz swap. O resultado é a lista ordenada ascendentemente pelo tamanho das strings.
Passo 5
Por fim, apresentamos os três programas completos, incluindo leitura de entrada e impressão do resultado formatado.
Resposta
Programa 1: insertion sort de nomes alfabeticamente
def insertion_sort_names(lst):
for i in range(1, len(lst)):
key = lst[i]
j = i - 1
# desloca enquanto o nome anterior for maior que key
while j >= 0 and lst[j] > key:
lst[j + 1] = lst[j]
j -= 1
lst[j + 1] = key
for i in range(1, len(lst)):
key = lst[i]
j = i - 1
# desloca enquanto o nome anterior for maior que key
while j >= 0 and lst[j] > key:
lst[j + 1] = lst[j]
j -= 1
lst[j + 1] = key
Exemplo de uso:
n = int(input("Quantos nomes? "))
names = [input().strip() for _ in range(n)]
insertion_sort_names(names)
print(“Nomes ordenados:”)
for nome in names:
print(nome)
names = [input().strip() for _ in range(n)]
insertion_sort_names(names)
print(“Nomes ordenados:”)
for nome in names:
print(nome)
Programa 2: bubble sort de caracteres de uma string
def bubble_sort_string(s):
chars = list(s)
n = len(chars)
# passa várias vezes até não haver trocas
for i in range(n):
swapped = False
for j in range(0, n - i - 1):
if chars[j] > chars[j + 1]:
chars[j], chars[j + 1] = chars[j + 1], chars[j]
swapped = True
if not swapped:
break
return ‘’.join(chars)
chars = list(s)
n = len(chars)
# passa várias vezes até não haver trocas
for i in range(n):
swapped = False
for j in range(0, n - i - 1):
if chars[j] > chars[j + 1]:
chars[j], chars[j + 1] = chars[j + 1], chars[j]
swapped = True
if not swapped:
break
return ‘’.join(chars)
Exemplo de uso:
s = input("Digite uma string: ")
print(“String ordenada:”, bubble_sort_string(s))
print(“String ordenada:”, bubble_sort_string(s))
Programa 3: selection sort de nomes por tamanho
def selection_sort_by_length(lst):
n = len(lst)
for i in range(n - 1):
min_idx = i
for j in range(i + 1, n):
if len(lst[j]) < len(lst[min_idx]):
min_idx = j
lst[i], lst[min_idx] = lst[min_idx], lst[i]
n = len(lst)
for i in range(n - 1):
min_idx = i
for j in range(i + 1, n):
if len(lst[j]) < len(lst[min_idx]):
min_idx = j
lst[i], lst[min_idx] = lst[min_idx], lst[i]
Exemplo de uso:
n = int(input("Quantos nomes? "))
names = [input().strip() for _ in range(n)]
selection_sort_by_length(names)
print(“Nomes ordenados por tamanho:”)
for nome in names:
print(nome)
names = [input().strip() for _ in range(n)]
selection_sort_by_length(names)
print(“Nomes ordenados por tamanho:”)
for nome in names:
print(nome)