Análise e projeto de algoritmos

Análise e projeto de algoritmos

1 – A linguagem: A linguagem usada para a resolução do problema de ordenação de vetores foi a linguagem JAVA. Por ser uma linguagem relativamente fácil de programar.

2 – Os Algoritmos: Os algoritmos escolhidos para a implementação do problema, são algoritmos relativamente simples, segue abaixo um breve comentário sobre os mesmos e seus respectivos pseudocódigos :

2.1 – InsertionSort: é um simples algoritmo de ordenação, eficiente quando aplicado a um pequeno número de elementos. Em termos gerais, ele percorre um vetor de elementos da esquerda para a direita e à medida que avança vai deixando os elementos mais à esquerda ordenados. O algoritmo de inserção funciona da mesma maneira com que muitas pessoas ordenam cartas em um jogo de baralho como o pôquer. Segue abaixo o seu respectivo código.

PSEUDOCÒDIGO:

INSERTION_SORT (A,size) for j←2 to size do key ← A[j] i ← j–1 and while i > 0 and A[i] > key do A[i+1] ← A[i] i ← i–1 A[i+1]← key

2.2 – SelectionSort : ordenação por seleção é um algoritmo de ordenação baseado em se passar sempre o menor valor do vetor para a primeira posição (ou o maior dependendo da ordem requerida), depois o de segundo menor valor para a segunda posição, e assim é feito sucessivamente com os (n-1) elementos restantes, até os últimos dois elementos.

PSEUDOCÓDIGO:

para i = 1 até tamanho-1, faça minimo = i para j = i+1 até tamanho, faça se vetor[j] < vetor[minimo], então minimo j fim-se fim-para temp = vetor[i] vetor[i] = vetor[minimo] vetor[minimo] = temp fim-para

2.3 – HeapSort: Tem um desempenho em tempo de execução muito bom em conjuntos ordenados aleatoriamente, tem um uso de memória bem comportado e o seu desempenho em pior cenário é praticamente igual ao desempenho em cenário médio. Alguns algoritmos de ordenação rápidos têm desempenhos espectacularmente ruins no