Algoritmos de ordenação

Dupla: Abdiel Brilhante e Daniel Franklin Meira
Prof: Alexandre Correia Cirqueira

INTRODUÇÃO

O programa (feito em C++) deverá ordenar valores de um vetor através dos seguintes algoritmos:

Complexidade quadrática: Complexidade logarítmica:

1)Selection Sort 5)Quick Sort 2)Insertion Sort 6)Heap Sort 3)Bubble Sort 7)Merge Sort 4)Shell Sort

O vetor deve ser criado através das seguintes formas:

-Com valores digitados pelo usuário separadamente na mesma linha
-Com valores gerados aleatoriamente, sendo a quantidade determinada pelo usuário
-Fazendo um vetor ordenado
-Fazendo um vetor inversamente ordenado

O usuário também deverá determinar se a ordenação será crescente ou decrescente. O programa deverá mostrar o vetor sendo ordenado passo-a-passo (só com o vetor gerado manualmente, já que, nos outros casos, se o usuário tiver determinado um tamanho muito grande para o vetor gerado automaticamente, mostrar cada passo não seria viável) e guardar num arquivo .txt os valores do vetor antes e depois da ordenação, assim como o número de comparações e movimentações de valores feitas e o tempo decorrido durante o processo de ordenação (este último só com o vetor gerado aleatoriamente), que também deverão ser exibidos na tela durante a execução do programa.

Uma diferença entre este programa e o do trabalho anterior é que agora, ao invés de usarmos a função clock() para obtermos os tempos de ordenação, usamos gettimeofday(), que possui uma precisão muito superior.

IMPLEMENTAÇÃO

Utilização do programa

Na tela inicial, o usuário deve escolher o(s) algoritmo(s) de ordenação a ser(em) utilizado(s). Para realizar mais de uma ordenação (usando algoritmos diferentes ou não), ele deverá digitar os números dos algoritmos desejados separados por espaço e depois confirmar com ENTER. Por exemplo: uma entrada “2 3 4 4 5” fará com que as ordenações a serem feitas sejam Insertion, Bubble, Shell (duas vezes seguidas), e por