Primeiro exerc cio programa

1º Exercício-programa de Pesquisa e Ordenação
Prof. Glauber Cintra – Entrega: 22/set/14

Este EP vale 6 pontos e deve ser feito por grupos de no mínimo 3 e no máximo 4 alunos.

Escreva um programa em C (ou Java) para comparar o desempenho dos métodos de ordenação bolha com flag, cocktailsort, inserção, seleção, shellsort, mergesort, quicksort determinístico e quicksort probabilístico, countingsort, bucketsort, radixsort e heapsort. No quicksort determinístico utilize como pivô o primeiro elemento do intervalo. No quicksort, probabilístico, utilize como pivô um elemento do intervalo escolhido pseudo-aleatoriamente. Implemente o heapsort com ordenação in situ e com construção do heap em tempo linear. Implemente duas versões do radixsort, uma usando o countingsort como subrotina, outra usando o bucketsort como subrotina.

Seu programa deverá receber pela linha de comando o tamanho da lista e um código indicando o tipo da lista: 1 = lista gerada aleatoriamente, 2 = lista em ordem decrescente e 3 = lista já em ordem crescente. Por exemplo, a linha de comando:

ordena 1000 1 (ou, java ordena 1000 1)

serve para ordenar uma lista gerada pseudo-aleatoriamente com 1000 elementos. A lista deverá ser constituída de números inteiros entre zero e o tamanho da lista multiplicado por 10. As listas deverão ser colocadas sempre em ordem crescente.

Indique o número de comparações, o número de movimentações (uma movimentação consiste em atribuir um valor a uma posição da lista ou atribuir o valor de uma posição da lista a uma variável) e o tempo requerido por cada método (em milissegundos). Seu programa deverá produzir informações como as do exemplo abaixo para cada um dos métodos de ordenação.

Seleção (1000 elementos – Aleatória)
Comparações: 499500 Movimentações: 999 Tempo: 3.76 ms

Ao ordenar uma lista com menos de 100 elementos com um método de ordenação, seu programa deverá escrever no arquivo saida.txt o conteúdo da lista antes e depois da execução do método. O arquivo