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.

QUESTIONÁRIO 07 - ORDENAÇÃO – MÉTODO MERGESORT

1) Por que o método mergesort têm esse nome? Existe outra versão do método? Ele é conhecido por qual outro nome?
 Resposta: O mergesort ou ordenação por mistura (fusão), é um exemplo de algoritmo de ordenação do tipo dividir-para-conquistar.

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

      Resposta: Complexidade de tempo. É (n log₂ n). É possível implementar o mergesort utilizando somente um vetor auxiliar ao longo de toda a execução.

      3) Qual é a classificação do método mergesort? Qual o seu grau de complexidade?
      Resposta: O   Mergesort é classificado como ordenação por partição, que parte do princípio de "dividir para conquistar". Este princípio é uma técnica que foi utilizada pela primeira vez por Anatolii Karatsuba em 1960 e consiste em dividir um problema maior em problemas pequenos, e sucessivamente até que o mesmo seja resolvido diretamente. 
      Esta técnica realiza-se em três fases:
      Divisão: o problema maior é dividido em problemas menores e os problemas menores obtidos são novamente divididos sucessivamente de maneira recursiva. 
      Conquista: o resultado do problema é calculado quando o problema é pequeno o suficiente.
     Combinação: os resultados dos problemas menores são combinados até que seja obtida a solução do problema maior. Algoritmos que utilizam o método de partição são caracterizados por serem os mais rápidos dentre os outros algoritmos pelo fato de sua complexidade ser, na maioria das situações, O(nlogn). Os dois representantes mais ilustres desta classe são o quicksort e o mergesort.
     

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

     

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

                              

Clique na figura para visualizar

QUESTIONÁRIO 06 - INSERÇÃO E MÉTODO SHELL

1)    Por que o método shell têm esse nome? Existe outra versão do método? Ele é conhecido por qual outro nome?

Resposta: O Método Shell leva o nome do seu inventor Donald L. Shell, formado em Ciência da Computação e teve seu PH.D. em matemática após a publicação  do algoritmo de ordenação shell. A versão que existe é a versão 1.2 e em relação ao nome, ela também pode ser conhecida como concha, pois lembra o formato de uma concha. 

2)    A ordenação pelo método shell é um dos mais simples. Qual a principal característica do método ou como ele funciona?
Resposta: A principal característica do método shell é que ele trabalha com 2 vetores: Vetor Ordenado e Vetor Desordenado. Com o funcionamento e evolução do método shell, o vetor desordenado vai diminuindo seus elementos, enquanto o vetor ordenado vai aumentando seus elementos, ou seja, os elementos que estavam desordenados vai se ordenando até que o vetor ordenado fique com todos os elementos completo e o vetor desordenado não haja mais nenhum elemento, ou seja, se torna um vetor vazio (null).

3)    Qual é a classificação do método shell? Qual o seu grau de complexidade?
Resposta: O método shell é classificado como método de simples implementação e o seu grau de complexidade é quadrática.

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

Resposta: O primeiro elemento está no vetor ordenado e os demais no vetor desordenado;

Retira-se o primeiro elemento do vetor desordenado, colocando-o no vetor ordenado. Nesse processo, são realizadas as comparações necessárias para inserí-lo na sua posição correta;

Repete-se o processo até que todos os elementos do vetor desordenado tenham passado para o vetor ordenado.

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