AEDS II

Trabalho Prático Algoritmos e Estrutura de Dados II

Descreva o funcionamento de cada algoritmo em termos do invariante de cada um ou do seu comportamento recursivo.

Insertion Sort:

Este método, considera-se o vetor (vetor) a ordenar como um vetor dividido em dois subvetores (esquerdo e direito), com o da esquerda ordenado e o da direita desordenado. Os elementos são retirados um de cada vez do subvetor da direita (não ordenado), e move-se esse elemento para o subvetor da esquerda, inserindo-o na posição correta por forma a manter o subvetor da esquerda ordenado, terminando o processo quando o subvetor da direita ficar vazio. Quik Sort:

O vetor X[p..r] é particionado em dois subvetores não vazios X[p..q] e X[q+1..r], tais que cada elemento de X[p..q] é menor ou igual a cada elemento de X[q+1..r]. Para determinar o índice q, escolhe-se o elemento que se encontra na metade do vetor original, chamado de pivô, e rearranjam-se os elementos do vetor de forma que os da esquerda de q são menores (ou iguais) e os da direita são maiores (ou iguais) ao pivô. Os dois subvetores são ordenados X[p..q] e X[q+1..r] por chamadas recursivas ao QUICK SORT. Os elementos vão sendo ordenados no próprio vetor, sem processamento nesta etapa.

Heap Sort:

O método de ordenação heapsort consiste numa árvore binária completa que obedece às seguintes propriedades: se o nó x é pai do nó y, então chave(x) > chave(y) , no último nível da árvore as folhas são colocadas em sequencia da esquerda para a direita. A ordenação heapsort requer apenas operações sem dar importância à ordem de entrada.

Implemente os algoritmos usando C++.

Insertion Sort:

void insertion(int a[], int t) { int i,j,chave; for (int i=1; i< t; i++){ chave = a[i]; j = i-1; while (chave=0) { a[j+1] = a[j]; j=j-1; }