Crie um programa que dado uma string, coloque as letras dela em ordem decrescente usando o algoritmo quick sort.

Passo 1

O exercício pede para criar um programa que receba uma string e ordene suas letras em ordem decrescente usando o algoritmo Quick Sort. O conteúdo envolvido é ordenação (dividir e conquistar) e manipulação de strings (que em muitas linguagens são imutáveis). Vamos precisar conhecer como funciona o Quick Sort e como converter uma string em um tipo mutável (lista de caracteres).

Passo 2

Para aplicar o Quick Sort em Python, primeiro convertemos a string em uma lista de caracteres, pois strings são imutáveis em Python e não permitem trocas diretas de posições. Basta fazer arr = list(s).
Implementamos a função partition adaptada para ordenação decrescente. Escolhemos como pivô o elemento na posição high. Inicializamos i = low - 1 e, para cada j de low até high-1, comparamos arr[j] com o pivô. Se arr[j] >= pivot, incrementamos i e trocamos arr[i] com arr[j]. No final, colocamos o pivô na posição i+1 e retornamos esse índice.

Passo 3

Implementamos a função recursiva quick_sort(arr, low, high). Se low < high, chamamos primeiro partition para obter o índice do pivô pi, depois aplicamos quick_sort em ambas as metades: de low até pi-1 e de pi+1 até high. Isso garante a estratégia dividir e conquistar.
No programa principal, lemos a string do usuário, convertemos em lista, chamamos quick_sort(arr, 0, len(arr)-1) e depois usamos para reconstruir a string já ordenada em ordem decrescente. Por fim, exibimos esse resultado.

Resposta

def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] >= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[high] = arr[high], arr[i+1]
return i + 1
def quick_sort(arr, low, high):
if low < high:
pi = partition(arr, low, high)
quick_sort(arr, low, pi-1)
quick_sort(arr, pi+1, high)
def sort_string_desc(s):
arr = list(s)
quick_sort(arr, 0, len(arr) - 1)
return ‘’.join(arr)
if name == “main”:
s = input("Digite uma string: ")
print(sort_string_desc(s))

Exercícios relacionados