QUESTIONÁRIO 08 - 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: O método Quicksort tem esse nome por ser um método que é mais rápido ordenar dois vetores com n/2 elementos cada um,  do que um com n elementos (conceito dividir para conquistar).  Além da versão recursiva, existe também a versão iterativa 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?
Resposta: O primeiro passo é escolher o pivô. Uma vez escolhido o pivô, os elementos do vetor são movimentados de forma que o subvetor à esquerda do pivô contenha somente os elementos cujo valor é menor que o valor do pivô e o subvetor da direita contenha valores maiores que o valor do pivô. O procedimento é repetido até que o vetor esteja ordenado.

3)      Qual é a classificação do método quicksort? Qual o seu grau de complexidade?
Resposta: O método quicksort é um método recursivo. Existem dois tipos de complexidade: Complexidade de Tempo e Complexidade de Espaço.
Complexidade de Tempo θ(n lg₂ n) no melhor caso e θ(n) no caso médio e θ(n²) no pior caso;
Complexidade de espaço: θ(lg₂ n) no melhor caso e no caso médio e θ(lg₂ n) no pior caso. R. Sedgewick desenvolveu uma versão do Quicksort com partição recursão de cauda que tem complexidade θ(n²) no pior caso.

4)      Dê exemplo de aplicação do método quicksort, com as comparações, trocas e iterações.
a) Pivô é escolhido no meio do vetor. O elemento é colocado numa variável auxiliar trab;
b) São iniciados dois ponteiros i e j;
c) O vetor é percorrido a partir da esquerda até que se encontre um V[i] ≥ trab (i é incrementado no processo);
d) O vetor é percorrido a partir da direita até que se encontre um V[j] ≤ trab (j é decrementado no processo); 
e) Os valores V[i] e V[j] são trocados; i é incrementado de 1 e j é decrementado de 1;
f) O processo é repetido até que i e j se cruzem em algum ponto do vetor;
g) Quando são obtidos os dois segmentos do vetor por meio do processo de partição, realiza-se a ordenação de cada um deles de forma recursiva.

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

  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 ao pivô e outra parte direita maiores ou iguais. O vetor é percorrido a partir da direita até encontrar um V[j] ≤ V[i]. Os valores V[i] e V[j] são trocados, i é incrementado de 1 e j é decrementado de 1, o processo é repetido até que i e j se cruzem em algum ponto do vetor. Quando são obtidos os dois segmentos do vetor por meio do processo de partição, realiza-se a ordenação de cada um deles de forma recursiva.