QUESTIONÁRIO 8 - Método Quicksort

1 - Por que o método quicksort tem esse nome ? Existe outra versao do método ? Ele é conhecido pro qual outro nome ?

R: O método quicksort tem esse nome por ser o método mais rápido e ordenado dois vetores com n/2 elementos cada um , do que um com n de elementos . 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 caracteristica do método ou como ele funciona ?

R: Adotando a estratégia dividir para conquistar o funcionamento resume-se a dividir o problema de ordenar um vetor de n posições em dois outros menores recursivamente ate atingir o objetivo de rearranjar todo vetor .

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

R: Método recursivo e sua ordem de complexidade do algoritmo recursivo deste método é 0)n log n).

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

Usando o 5 como pivô:



5 - Demostre o codígo-fonte do método quicksort e coemente 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 . 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.

QUESTIONÁRIO 7 - Ordenação Método Mergersort

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

R: Merge sort , ou ordenação por mistura (fusão) e um exemplo algoritmo de ordenação do tipo dividir-para-conquistar.

2 - A ordenação pelo método mergesort é um dos mais simples . Qual principal caracteristica do metodo ou como ele funciona ?

R: Sua principal caracteristica e ordenação do tipo dividir para conquistar . Sua ideia básica é criar uma seguência ordenada a partir de duas outras também ordenadas . Para isso,ele divide a sequência original em pares de dados , ordena-das ; depois as agrupa em sequências de quatro elementos , e assim por diante , ate ter toda a sequência dividida em apenas duas partes .

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

R: Método recursivo e sua ordem de complexidade do algoritmo recursivo desde método é 0 (n log n).

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




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




Na quinta e sexta linha do código definimos os ponteiros para o vetor 1 e 2 . A função de copia do vetor temporário para o que retornara atualizado se encontra no segundo for . Na parte final do código é definida a função principal do mergesort que determina a metade do vetor depois a primeira metade e a segunda metade a ultima linha combina as metades já ordenadas.