MÉTODOS SIMPLES DE ORDENAÇÃO

[pic 1][pic 2]

   

Nome do Aluno: Ramon Kenedy do Nascimento Data: 23/05/2016

Prof.: Renan Rodrigues de Oliveira

MÉTODOS SIMPLES DE ORDENAÇÃO

RESUMO

Ordenação é um processo de rearranjar um conjunto de objetos em uma ordem ascendente ou descendente.

A ordenação visa facilitar a recuperação posterior de itens do conjunto ordenado.

O objetivo principal deste trabalho é estudar a complexidade dos algoritmos de simples ordenação.

INTRODUÇÃO

         Um algoritmo consiste em um procedimento com um conjunto regras não ambíguas que especificam, para cada entrada, uma sequência finita de operações, resultando em uma saída correspondente (TOSCANI; VELOSO, 2002). Assim, analisar um algoritmo significa prever os recursos que o algoritmo necessitará (CORMEN et al., 2002).

A análise de algoritmos é um mecanismo para entender e avaliar um algoritmo em relação aos critérios destacados, bem como saber aplica-los á problemas práticos.

        A ordenação auxilia em diversas situações tais como teste de unicidade, remoção de duplicatas, busca, encontrar o i-ésimo maior (ou menor) elemento de uma coleção, contagem de frequência.

        Este trabalho terá como algoritmos principais de ordenação a serem estudados o bubble sorte, o selection sort e o insertion sort.

FUNDAMENTAÇÃO TEÓRICA / REVISÃO DA LITERATURA

Os métodos de ordenação podem ser classificados como internos e externos.

Interna: arquivo a ser ordenado cabe todo na memória principal. Em um método de ordenação interna, qualquer registro pode ser imediatamente acessado.

Externa: arquivo a ser ordenado não cabe na memória principal. Em um método de ordenação externa, os registros são acessados sequencialmente ou em grandes blocos.

Um método de ordenação é estável se a ordem relativa dos itens com chaves iguais não se altera durante a ordenação.

DESENVOLVIMENTO

Exercícios

1. Mostre um exemplo de entrada que demonstra que o SellSort não é estável.

Resposta: 11,4,5,23,7,29,11,7,6,8.

Pode-se observar que os elementos de entrada 7 e 11 estao sendo repetidos 2 vezes e que como entrada o 11 esta na posição do vetor 0 e 6 e o algarismo 7 esta na posição do vetor 4 e 7 porem na saída ordenada do algoritmo o algarismo 11 da posição 6 veio primeiro do que o da posição 0 e o algarismo 7 na posição do vetor 7 veio primeiro do que o algarismo 7 da posição 4 como demostrado na figura abaixo.  Segui código completo em anexo para analise.

[pic 3]

2. Dada a sequência de números: 3 4 9 2 5 1 8. Ordene em ordem crescente utilizando o algoritmo

MergeSort, apresentando a sequência dos números a cada passo (teste de mesa).

Resposta: segui código completo em anexo para analise.

3. Modifique o código dos seguintes algoritmos de forma a que a ordenação seja realizada por ordem decrescente.

a) Método da Bolha.

Resposta: segui código completo em anexo para analise.

[pic 4]

b) Ordenação por Seleção.

Resposta: segui código completo em anexo para analise.

[pic 5]

c) Ordenação por Inserção.

Resposta: segui código completo em anexo para analise.

[pic 6]

4. Considerando que o método de Ordenação por Seleção é instável, crie uma adaptação deste método para que este seja estável e que apresente a mesma complexidade do algoritmo original. Para isto, estenda a chave dos elementos no vetor de entrada com a posição (índice) do elemento no vetor de entrada (utilize Struct em C). Use a posição original do elemento no vetor de entrada como critério de desempate caso dois elementos tenham chaves iguais.