Programação

Universidade Federal de Mato Grosso do Sul
Facom - Faculdade de Computacao ¸˜ ˆncia da Computacao Bacharelado em Cie ¸˜
´ Analise de Algoritmos Profa. Bianca de Almeida Dantas

Trabalho 1 - Algoritmos de Ordena¸˜o ca 1 Descri¸˜o ca

Os algoritmos de ordena¸˜o s˜o de importˆncia fundamental em diversas ´reas e seu ca a a a estudo ´ um dos principais temas da ciˆncia da computa¸˜o. Ao longo de nosso e e ca curso, temos estudado diversos m´todos de ordena¸ao, os quais diferem nas t´cnicas e c˜ e de desenvolvimento de algoritmos utilizadas e na complexidade de tempo de execu¸ao. c˜ O objetivo deste trabalho ´ implementar, utilizando a linguagem C++, e comparar e o desempenho dos seguintes algoritmos de ordena¸˜o: ca 1. Insertion-Sort 2. Mergesort 3. Quicksort 4. Heapsort

1.1

Formato da Entrada e da Sa´ ıda

Cada um dos algoritmos deve ser utilizado para ordenar sequˆncias contendo 1.000, e 10.000, 100.000 e 1.000.000 n´meros inteiros. O tempo necess´rio para realizar a u a ordena¸ao em cada um dos casos deve ser medido e comparado ao tempo gasto pelos c˜ demais algoritmos. O seu programa deve receber como entrada o nome do arquivo com os n n´meros u a serem ordenados e gerar como sa´ cinco arquivos: ıda 1. Quatro arquivos (um para cada algoritmo) contendo os n´meros ordenados (com u extens˜o .out), separados por um unico espa¸o em branco. Os arquivos dever˜o a ´ c a ser nomeados seguindo a regra: nomealgoritmo tamanhoentrada.out

1

2. Um arquivo com nome nomearquivoentrada.time contendo os tempos de execu¸ao c˜ em milissegundos de cada algoritmo para aquela entrada, de acordo com o seguinte formato: Insertion: xxxx Merge: xxxx Quick: xxxx Heap: xxxx Assim, quando for executada a seguinte linha de comando: ./nome programa teste 1000.in devem ser gerados os seguintes arquivos no diret´rio de execu¸ao: insertion 1000.out, o c˜ merge 1000.out, quick 1000.out, heap 1000.out e teste 1000.time. O arquivo de entrada conter´ em sua primeira linha o n´mero de