QUICKSORT
1) Por que o método quicksort têm esse nome? Existe outra versão do método? Ele é conhecido por qual outro nome?
Resposta:
C.A.R. Hoare criou o 'Quicksort ao tentar traduzir um dicionário de inglês para russo, ordenando as palavras, tendo como objetivo reduzir o problema original em subproblemas que possam ser resolvidos mais facil e rapidamente.
2) A ordenação pelo método quicksort é um dos mais simples. Qual a principal característica do método ou como ele funciona?
Resposta:
O Quicksort adota a estratégia de divisão e conquista. A estratégia consiste em rearranjar as chaves de modo que as chaves "menores" precedam as chaves "maiores". Em seguida o Quicksort ordena as duas sublistas de chaves menores e maiores recursivamente até que a lista completa se encontre ordenada. [3]Os passos são:
1. Escolha um elemento da lista, denominado pivô;
2. Rearranje a lista de forma que todos os elementos anteriores ao pivô sejam menores que ele, e todos os elementos posteriores ao pivô sejam maiores que ele. Ao fim do processo o pivô estará em sua posição final e haverá duas sublistas não ordenadas. Essa operação é denominada partição;
A base da recursão são as listas de tamanho zero ou um, que estão sempre ordenadas. O processo é finito, pois a cada iteração pelo menos um elemento é posto em sua posição final e não será mais manipulado na iteração seguinte.
3) Qual é a classificação do método quicksort? Qual o seu grau de complexidade?
Resposta:
Método Recursivo, complexidade de tempo e espaço:
· Complexidade de espaço: θ(lg2 n) no melhor caso e no caso médio e θ(lg2 n) no pior caso. R. Sedgewick desenvolveu uma versão do Quicksort com partição recursão de cauda que tem complexidade θ(n2) no pior caso.
4) Dê exemplo de aplicação do método quicksort, com as comparações, trocas e iterações.
Resposta:
5) Demonstre o código-fonte do método quicksort e comente o mesmo.
Resposta:
Nenhum comentário:
Postar um comentário