Estes exercícios podem ser feitos em qualquer linguagem diferente de Java e Prolog (não necessariamente C).

• Implemente o quicksort em alguma linguagem diferente de Java e Prolog, com a seguinte modificação: o algoritmo manterá um contador de repetições que será incrementado cada vez que passar em um laço ou que uma função recursiva tiver chamado a si mesma. Teste seu algoritmo. Use a função PARTICAO sem randomização.
• Teste seu quicksort com vetores ordenados em ordem crescente, decrescente e aleatória. Teste tambem com vetores que tenham muitos elementos repetidos, e informe os resultados, mostrando o valor do contador. Por "ordem aleatória" quero dizer que a distribuição dos elementos no vetor deve ser uniforme.
  • Em um loop aninhado, só conte a iteração de dentro (claro!)
  • Para realizar este teste, voce deve testar com vetores de tamanho 50, 100, 500, 1000 e 5000;
  • Cada experimento com o vetor em ordem aleatória deve ser repetido vinte vezes, cada vez com uma entrada diferente (e a entrada deve sempre ser uniformemente distribuída).
• Modifique sua função PARTICAO para escolher o pivô aleatoriamente. Refaça os experimentos e comente os resultados.
• Se você tiver que usar o heapsort em um vetor muito grande usando a implementação recursiva, acredita que tera problemas ou nao? Por que motivo?
• Prove que o counting sort é estável

Dicas:

• A seguinte função toma um vetor e reorganiza as posiçõs dos elementos, de forma que a novas posições são aleatóreas, uniformemente distribuídas:

  RANDOMIZA(vet, tam)
  	para i de 1 ate tam-1:
  		j = RANDOM (i+1, tam)
  		troca vet[i] <--> vet[j]