QUESTIONÁRIO 08 - ED II

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;

3.      Recursivamente ordene a sublista dos elementos menores e a sublista dos elementos maiores;

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 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.

Resposta:

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

Resposta:

                                                              

QUESTIONÁRIO 07 - ED II

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 método de ordenação Mergesort também é conhecido como “dividir para conquistar” e significa  ordenação por mistura (fusão).

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:

Sua idéia básica é muito fácil: criar uma sequência ordenada a partir de duas outras também ordenadas. Para isso, ele divide a sequência original em pares de dados, ordena-as; depois as agrupa em sequências de quatro elementos, e assim por diante, até ter toda a sequência dividida em apenas duas partes.

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

Resposta:

Método recursivo e sua ordem de complexidade do algoritmo recursivo deste método é O(n log n) .

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

Resposta:

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

Resposta:

// A função mergesort rearranja o vetor v[p..r-1]

// em ordem crescente.

void

mergesort (int p, int r, int v[])

{

   if (p < r-1) {

      int q = (p + r)/2;

      mergesort (p, q, v);

      mergesort (q, r, v);

      intercala (p, q, r, v);

   }

}

QUESTIONÁRIO 06 - ED II

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:

Leva o nome de seu inventor, Ronald L. Shell; consiste na aplicação do método da Inserção, em vários passos, a elementos não consecutivos (separados por determinados intervalos). A cada passo, esse intervalo decresce: primeiro, são ordenados entre si todos os elementos separados de quatro posições. Em seguida, são ordenados os elementos a duas posições de distância. Finalmente, são ordenados os elementos adjacentes. Há também a versão Shell-Metzner, antecessor a ele.Também conhecido por método 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:

Shell algoritmo de ordenação melhora a ordenação por inserção, comparando os elementos separados por um espaço de várias posições. Esto permite que un elemento haga "pasos más grandes" hacia su posición esperada. Isso permite que um elemento para fazer "passos maiores" em direção a sua posição esperada. Los pasos múltiples sobre los datos se hacen con tamaños de espacio cada vez más pequeños. A várias passagens sobre os tamanhos de dados são feitos espaço cada vez menores. El último paso del Shell sort es un simple ordenamiento por inserción, pero para entonces, ya está garantizado que los datos del vector están casi ordenados. A última etapa da espécie Shell é uma espécie de inserção simples, mas aí já é garantido que os dados são quase ordenada do vetor.

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

Resposta:

Shell sort é o mais eficiente algoritmo de classificação dentre os de complexidade quadrática. É um refinamento do método de inserção direta.

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

Resposta:

Execução:

Dado o vetor de entrada: 12, 43, 1, 6, 56, 23, 52, 9

12, 43, 1, 6, 56, 23, 52, 9
12, 43, 1, 6, 56, 23, 52, 9
1, 43, 12, 6, 56, 23, 52, 9
1, 6, 12, 23, 56, 43, 52, 9
1, 6, 12, 23, 52, 43, 56, 9
1, 6, 12, 23, 52, 9, 56, 43
1, 6, 12, 9, 52, 23, 56, 43
1, 6, 9, 12, 52, 23, 56, 43
1, 6, 9, 12, 23, 52, 56, 43
1, 6, 9, 12, 23, 52, 43, 56
1, 6, 9, 12, 23, 43, 52, 56

Em negrito estão os números trocados na atual iteração.
Após as seguintes trocas acima, obtemos o vetor ordenado: 1, 6, 9, 12, 23, 43, 52, 56.

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

Resposta:

//***************************************************************************
// Função shell_sorte – Recebe uma matriz desordenada e a ordena com
// algoritmo shell sort
//
// Entradas – matriz a ser ordenada e tamanho da matriz a ordenar
// Saídas - nenhuma
//***************************************************************************
void shell_sort(unsigned char matriz[], unsigned int tamanho){

    unsigned int i, gap;
    unsigned char temp, ret;

    gap = tamanho / 2;
    do {
       do{
          ret=0;
             for (i=0; i< tamanho – gap; i++)
                if (matriz[i] >matriz[i+gap]){
                   temp=array[i];
                      array[i]=array[i+gap];
                      array[i+gap]=temp;
                      ret=1;
                }
       } while(ret);
    } while (gap = gap / 2);
}