QUESTIONÁRIO 08 - ORDENAÇÃO E MÉTODO 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?

R: O método quicksort tem esse nome por ser o método mais veloz e ordenando dois vetores com n/2 elementos cada um , do que um com n de elementos e além de versões recursiva, existe também a versão interativa do quicksort.


2 - A ordenação pelo método quicksort é um dos mais simples. Qual a principal característica do método ou como ele funciona?

R:  É conhecida pela característica rápida de ordenar dois vetores com 2 elementos cada um , do que com N elemento.

3 - Qual é a classificação do método quicksort? Qual o seu grau de complexidade?

R: Método recursivo de complexidade de ordem algoritima recursivo. O método é 0)n log n).

4 - Dê exemplo de aplicação do método quicksort, com as comparações, trocas e iterações.

R: Para matrizes com muitos elementos este é o método de ordenação mais rápido. Neste tipo de ordenação o programa considera sua matriz uma lista de valores. Inicialmente é selecionado o valor que está posicionado no meio da lista que chamaremos de elemento central. Depois a matriz é dividida e ordenada em duas listas menores separando numa os elementos cujo valor é maior que o valor do elemento central e e na outra os elementos cujo valor é menor que o valor do elementro central. A partir daí o mesmo processo é feito com cada uma das listas recursivamente. Isso continua até que a matriz esteja toda ordenada.

Considere a matriz formada pelos valores inteiros: 6, 2, 1, 3, 4, 5, 8, 7 e 0. A figura abaixo mostra como poderíamos classificar esta matriz em ordem crescente usando o quick sort.

5 - Demonstre o código-fonte do método quicksort e comente o mesmo.

R:

A parte muito importante do algoritmo é a escolha de um pivô , o vetor estará particionado ao final em uma parte esquerda com chaves menores ou iguais . O vetor é percorrido a partir da direita até encontrar um V[i] < V[i] . Os valores V[i] e V[i] são trocados , i é incrementado de 1 e j é decrementado de 1 , o processo é repetido até que i e j se cruzem em um ponto do vetor . Quando são obitidos os dois segmentos do vetor por meio do processo de participação , realiza-se a ordenação de cada um deles de forma recursiva.