Exercícios

Aula prática nº 9

Exercícios


  1. Dado o seguinte vector v={5, 9, 30, 10, 3, 9, 50, 20, 12, 1, 6}, qual o conteúdo de v após a terceira iteração do algoritmo de ordenação insertion? E do selection? E do bubble?
  2. Concretize os seguintes algoritmos de ordenação elementares:
    1. selection
    2. insertion
    3. bubble
  3. Defina e concretize o ADT de 1ª ordem respeitante a um gerador de sequências de números pseudo-aleatórios. O gerador deverá aceitar três parâmetros:
Número de chaves a gerar
Valor máximo de cada chave
Semente para iniciar o gerador de números aleatórios
 
e retornar um vector com os números gerados aleatóriamente. Este gerador é cliente dum ADT, Item, cuja funcionalidade é a seguinte:

void ITEMrandInit(int seed, Item max); /* inicializa a semente utilizada para gerar numeros pseudo-aleatórios e o valor máximo de um Item a ser gerado*/
Item ITEMrand(); /* gera um Item pseudo-aleatório */
void ITEMshow(Item); /* escreve no écran o Item indicado no argumento */

Desta forma, mudando o tipo de Item, não temos que mudar o cliente, que neste caso é o gerador (o qual também e'um ADT).
  1. Concretize uma função que recebe um vector v de elementos do tipo Item, um ponteiro para uma função de ordenação (void (*sort)(Item [], int l, int r)), os dois extremos do vector a ordenar e calcula o tempo que demora a ordenar o vector v utilizando a função de ordenação indicada.
  2. Utilizando a função anterior e o ADT gerador de sequências de números pseudo-aleatórios, realize um programa que compare os tempos de desempenho dos algoritmos elementares de ordenação. Na comparação deve utilizar números inteiros (tipo do Item) e vectores com tamanhos superiores a 10000.
  3. Repita a alínea anterior mas agora considerando algoritmos de ordenação eficientes: quick sort e merge sort.