Às vezes, a melhor maneira de descrever um algoritmo não é escrevendo.

https://www.youtube.com/watch?v=lyZQPjUT5B4

a) Faça um teste de mesa para um vetor com elementos $(5, 4, 3, 2, 1)$ e para um vetor com elementos $(1, 4, 3, 2, 5)$. Conte o número de vezes que trocamos dois elementos

b) Você consegue dizer por que o algoritmo tem esse nome?
Inconformado com a ordenação por bolha, em que os maiores elementos flutuam até o topo, como uma bolha, Joãozinho disse que esses elementos deveriam afundar até o fundo, como uma âncora. Assim, decidiu criar seu próprio algoritmo de ordenação.
```
def anchor_sort(lista):
    n = len(lista)
    for i in range(1, n):
        a = i
        while a > 0:
            if lista[a] > lista[a-1]:
                trocar(lista, a, a-1)
            a = a - 1
```
a) Você concorda que algoritmo de Joãzinho está correto? Justifique.

b) Explique o que esse algoritmo faz.
Reescreva a função insertion_sort para que ela não utilize funções auxiliares.
Escreva uma função para ordenar uma lista de pessoas em ordem decrescente de idade e, havendo empate, em ordem crescente de nome. Uma pessoa é representada por uma tupla como ("Ana", 18), que representa a Ana que tem 18 anos.

Exercícios criativos

Suponha que um time de voleibol é representado por uma string contendo o nome. Além disso, existe uma lista de tuplas representando os confrontos dos times, e.g.,
```
confrontos = [
    ("Estaleiro", "Mavista"),
    ("Estaleiro", "Manos"),
    ("Estaleiro", "São Saulo"),
    ("Mavista", "Manos"),
    ("Mavista", "São Saulo"),
    ("Mavista", "Tio de Janeiro"),
    ("Tio de Janeiro", "Estaleiro"),
    ("Tio de Janeiro", "Manos"),
    ("Manos", "São Saulo"),
    ("São Saulo", "Tio de Janeiro"),
]
```
Essa lista representa que o Estaleiro venceu o Mavista, mas foi derrotado pelo Tio de Janeiro.

a) Para ordenar uma lista de times, não basta olhar para os nomes dos times: devemos prestar atenção às regras do campeonato! Crie uma função ordenar_times que respeita as regras do campeonato. Para isso, o algoritmo receberá como entrada, além da lista de nomes, uma função funcao_comparar. Essa função é chamada como funcao_comparar(time_x, time_y, confrontos) e devolve True sempre que time_x puder aparecer antes de time_y em uma lista ordenada.
```
def ordenar_time(lista_nomes, funcao_comparar, confrontos):
    pass
```
b) Implemente agora uma função comparar para ser usada como parâmetro da função de ordenação. Nesse campeonato, vem primeiro o time com maior número de vitórias; se houver empate, a ordem é desempatada pelo confronto direto.
```
def comparar(time_x, time_y, confrontos):
    pass
```
Obter números aleatórios é um aspecto delicado de Computação. A noção de aleatoriedade em Computação é bem distinta da noção da linguagem natural. Normalmente, quando falamos de números aleatórios estamos falando de uma sequência que satisfaz determinadas propriedades, chamada sequência pseudoaleatória. Em muitos casos, essa distinção é irrelevante; por exemplo quando queremos apenas embaralhar um conjunto de cartas. Em Python, a maneira de obter números aleatórios é usando o módulo random. Por exemplo, para escolher um número aleatório entre 1 e 10, incluindo os extremos, fazemos:
```
import random

numero = random.randint(1, 10)
chute = int(input("Adivinhe em qual número pensei: "))
if chute == numero:
    print("Você é de mais!")
else:
    print(f"O número era {numero}.")
```
Uma pessoa com humor aleatório, mas que está bem em 80% dos dias, bem poderia registrar o seguinte diário
```
import random

for dia in range(1, 11):
    if random.random() < 0.8:
        print(f"No dia {dia} estive feliz =)")
    else:
        print(f"No dia {dia} estive triste :(")
```
Execute várias vezes os códigos acima e procure a documentação do módulo random.

O objetivo dessa questão é escrever uma função que embaralha uma lista de inteiros. Você não pode utilizar uma lista auxiliar.