Ordenação

1. Revisão de Conceitos

O que é uma Ordenação Estável?

Imagine que você tem dois restaurantes empatados com nota 5.0. Se você ordená-los por nota usando um algoritmo estável, o restaurante que apareceu primeiro na lista original continuará na frente após a ordenação. Algoritmos instáveis misturam essa ordem original. Como o enunciado sugere, se você usar um Bubble Sort, Insertion Sort ou a própria função nativa do Python (.sort()), você estará usando métodos estáveis, o que é fundamental para o próximo conceito.

O Truque das Múltiplas Prioridades

Se o usuário quer ordenar por [custo, tempo, nota], como você faz isso sem criar dezenas de ifs complexos? A resposta está na Observação 1: ordene de trás para frente!

  1. Primeiro, ordene toda a lista pelo critério menos importante (nota).
  2. Depois, pegue essa mesma lista e ordene pelo critério do meio (tempo).
  3. Por fim, ordene pelo critério mais importante (custo). Como sua ordenação é estável, quando você ordenar pelo custo, os restaurantes com o mesmo custo já estarão perfeitamente organizados pelo tempo (e os com o mesmo tempo, pela nota).

Crescente vs. Decrescente

Nem tudo se ordena do menor para o maior!

  • Custo e Tempo: O usuário quer o menor possível (Crescente: do menor para o maior).
  • Nota e Custo-Benefício: O usuário quer o maior possível (Decrescente: do maior para o menor).

2. Dicas de Estruturação (Por onde começar?)

Passo A: Leitura e Limpeza dos Dados Leia as linhas contendo os restaurantes. Como os dados vêm separados por vírgulas, você pode usar a função .split(','). Cuidado: Ao dividir a string "Pizza Boa, $$, 35, 4.5", os valores podem vir com espaços em branco sobrando (ex: " $$" em vez de "$$"). Use .strip() para limpar as bordas de cada informação.

Passo B: Tipagem e Preparação da Lista Você não pode calcular custo-benefício ou ordenar números se eles estiverem no formato de texto (string).

  1. O tempo pode ser transformado em que tipo de número?
  2. A nota pode ser transformada em que tipo de número?
  3. Como comparar so "$$"?? Dica: o que faz "$" ser menor que "$$"?

Passo C: Calculando o Custo-Benefício Com os valores numéricos em mãos, aplique a fórmula nota / custo_numerico. Use a função nativa round(valor, 1) para garantir que o resultado tenha apenas uma casa decimal, conforme exigido.

Passo D: A Lógica de Ordenação Leia a linha de prioridades. Como a ideia é usar um algortimo de ordenação estável, a primeira ordenação a ser feita deve ser a menor importância. Lembre-se que alguns critérios de ordenação pedem para ordernar em decrescente, outros, crescente.

3. Breve revisão do .sort()

Digamos que você vai guardar as informações de um restaurante em uma tupla como ("nome", "$", tempo, nota, custo_benefício), onde tempo, nota e custo_benefício são os correspondentes números. Se você fizer uma lista dessas tuplas, chamaremos de l, você pode orderná-las utilizando o método .sort().

l.sort()

A questão é que o Python, por padrão, irá ordernar pela primeira coordenada das tuplas, neste caso, o nome. É possível mudar esse comportamento passando para o método .sort() uma função que retorna o elemento que será utilizado na comparação. Por exemplo, se queremos ordernar por nota e nota é o quarto elemento da tupla (índice 3), podemos escrever uma função como esta:

def get_nota(e):
    return e[3]

l.sort(key=get_nota)

Agora, ao ordernar, o Python não vai mais olhar o primeiro elemento, mas sim o retorno da função get_nota para cada elemento da lista, pois o especificamos no parâmetro key do método .sort().

Um outro exemplo (que não necessariamente vai ser utilizado nessa atividade): digamos que queremos ordernar pelo tamanho do nome do restaurante. Podemos fazer algo assim:

def get_len_nome(e):
    nome = e[0] # pega no nome na primeira entrada do elemento
    return len(nome)

l.sort(key=get_len_nome)

O método .sort() também aceita um outro parâmetro: o reverse. Ele é um valor booleano (True ou False) que indica se o python deve ordernar de forma inversa ou não. Ou seja, chamar algo como:

def get_nota(e):
    return e[3]

l.sort(reverse=True, key=get_nota)

fará com que o Python ordene a lista de restaurantes em ordem decrescente de nota.

4. Problemas e Erros Comuns

Fique de olho nestas armadilhas clássicas que costumam complicar os testes no SuSy:

Comparação de Strings vs. Números:

Se você esquecer de converter os dados, o Python vai ordenar de forma alfabética. Na ordem alfabética de strings, "100" vem antes de "20", porque o caractere '1' é menor que o '2'. Sempre converta tempos para int e notas para float antes de ordenar.

Não limpar as strings após o split():

Se o usuário digitar custo, tempo, nota, um .split(',') vai gerar a lista ['custo', ' tempo', ' nota']. Note o espaço antes de “tempo”. Se você fizer um if criterio == 'tempo':, ele vai dar falso, pois ' tempo' é diferente de 'tempo'. Limpe os dados!

A ordem reversa na ordenação:

Se a lógica de ordenar do menos para o mais importante estiver confusa, pegue papel e caneta e simule o Teste 01 na mão. Ordene primeiro por nota, depois escreva a nova ordem e ordene por tempo, e assim por diante. Visualizar isso salva horas de código.

Bom trabalho no desenvolvimento do código! Testem cada comando isoladamente antes de juntar tudo no programa final e podem me mandar as dúvidas por email!