Método de ordenação

INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DE MINAS GERAIS

CAMPUS SÃO JOÃO EVANGELISTA

Exercícios de Algoritmos e Estrutura de Dados

Assunto: Lista de Exercícios 6

Componentes: Wárlley Júnio Andrade

Curso: Superior em Sistemas de Informação Série/Turma: BSI111A Professor: Bruno Toledo

São João Evangelista, Maio de 2012.

INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DE MINAS GERAIS

CAMPUS SÃO JOÃO EVANGELISTA

1. Qual a ideia central do Quicksort? O Quicksort utiliza o conceito de divisão e conquista, ou seja, dividir o problema grande em subproblemas para a resolução, para isso ele utiliza a recursividade para que ele possa dividir o problema. 1 primeira parte do algoritmo seria encontra o pivô, o pivô nada mais é que a soma dos índices externos do vetor divididos por 2 , ou seja é o índice médio do vetor. 2 A principio o algoritmo separa os elementos maiores que o pivô para a direita e os elementos menores que o pivô para a esquerda pois vai ser com o pivô que ele vai comparar cada elemento para colocá-lo na ordem certa. 2. Descreva a utilidade da Partição do método Quicksort? A partição tem a função de rearranjar o vetor por meio da escolha de um pivô, de tal forma que ao final o vetor estará particionado com uma parte esquerda com todos os elementos anteriores ao pivô menores que ele, e outra parte onde todos os elementos posteriores ao pivô sejam maiores que ele. 3. Qual(ais) a(s) diferença(s) entre o pior caso e o melhor caso do método Quicksort? Pior caso: C(n) = O (n2)  O pior caso ocorre quando, sistematicamente, o pivô é escolhido como sendo um dos extremos de um arquivo já ordenado.  Isto faz com que o procedimento Ordena seja chamado recursivamente n vezes, eliminando apenas um item em cada chamada. Melhor caso:  C(n) = 2C(n/2) + n = n log n  Esta situação ocorre quando cada partição divide o arquivo em duas partes iguais. 4. Quais as vantagens do Quicksort? É extremamente eficiente para ordenar arquivos de