Trabalho Faculdade

Atividade:
O trabalho consiste em três etapa:
1ª Etapa:
Pesquisar os algoritmos abaixo e analisar o comportamento deles com relação ao custo de tempo, custo de memória, estabilidade de ordenação, invariantes e corretude. OS algoritmos são
•    BubbleSort
•    CountingSort
•    SelectSort
•    MergeSort
2ª Etapa:
Implementar os quatro algoritmos acima de forma que sejam testadas a execução de cada um com os seguintes parâmetros:
•    Cada algoritmo ordenará 30 vetores de cada um dos tamanhos abaixo
o    1.000 inteiros
o    10.000 inteiros
o    100.000 inteiros
•    Cada um dos 30 vetores será gerado aleatoriamente, e cada geração deverá rodar em todos os 4 algoritmos. Cada posição do vetor receberá um inteiro aleatório de valor entre 1 e 1000
•    Serão tomados os tempos de cada execução dos algoritmos e inseridos um uma planilha.


Será acrescido no corpo do trabalho uma tabela semelhante ao abaixo com o cálculo do tempo médio
Algorimos    n=1.000    N=10.000    N = 100.000
BubbleSort            
InsertionSort            
SelectSort            
MergeSort            

Obs. : Basta implementar as funções de ordenação no código anexo e compilar mudando para o tamanho de cada entrada na linha #define max xxxxx , e copiar o resultado da média ao fim da execução.
3ª Etapa:
Tendo as informações das etapas anteriores, analisar e responder porque ocorre a diferença de execução de tempo entre os quatro algoritmos e qual o trecho de código justifica as respostas da primeira etapa para cada algoritmo.