cutoffde algoritmos de ordenação
E16.1 Escreva a expressão polonesa equivalente à expressão infixa
(A + B) * D + E / (F + A * D) + C
Procure imaginar o algoritmo que converte qualquer expressão infixa na correspondente polonesa.
E16.2 Escreva uma função que receba uma expressão polonesa posf e uma tabela de valores das variáveis e devolva o valor da expressão. DETALHES: A expressão polonesa posf é uma string não vazia com no máximo 100 caracteres. Suponha que posf contém somente os operadores +, -, * e / (todos exigem dois operandos). Suponha também que a expressão não tem constantes e que todos os nomes de variáveis consistem em uma única letra maiúscula. Suponha que o vetor tabela é organizado assim:
tabela[0] é o valor da variável A,
tabela[1] é o valor da variável B, etc.
e os valores são todos inteiros. Imagine que você tem uma pilha de números à disposição e uma função empilha (x) que coloca um número x na pilha e uma função desempilha ( ) que tira um número da pilha (e devolve esse número).
E16.3
Escreva uma versão do algoritmo Quicksort com cutoff
para vetores pequenos:
quando o vetor a ser ordenado tem 15 elementos ou menos,
a ordenação é feita por um algoritmo de inserção.
Esse truque é usado na prática porque o algoritmo de inserção é mais rápido que o Quicksort puro quando o vetor é pequeno. [O fenômeno é muito geral: algoritmos sofisticados só são mais rápidos que algoritmos simplórios quando o volume da dados é grande. Veja a tarefa E, por exemplo.]
E16.4 Escreva uma variante (iterativa) do algoritmo Mergesort que quebra o vetor em segmentos crescentes maximais e depois intercala cada dois segmentos consecutivos. Exemplo: os segmentos crescentes maximais do vetor 1 2 3 0 2 4 6 4 5 6 7 8 9 são 1 2 3 , 0 2 4 6 e 4 5 6 7 8 9 .
(A propósito, veja o verbete Timsort na Wikipedia.)