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
.
Implementamos a função partition adaptada para ordenação decrescente. Escolhemos como pivô o elemento na posição . Inicializamos
e, para cada
de
até
, comparamos
com o pivô. Se
, incrementamos
e trocamos
com
. No final, colocamos o pivô na posição
e retornamos esse índice.
Implementamos a função partition adaptada para ordenação decrescente. Escolhemos como pivô o elemento na posição
Passo 3
Implementamos a função recursiva quick_sort(arr, low, high). Se
, chamamos primeiro partition para obter o índice do pivô
, depois aplicamos quick_sort em ambas as metades: de
até
e de
até
. 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.
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
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)
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)
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))
s = input("Digite uma string: ")
print(sort_string_desc(s))