Análise Quicksort

UNIVERSIDADE FEDERAL DE VIÇOSA

CAMPUS RIO PARANAÍBA

CURSO DE SISTEMAS DE INFORMAÇÃO

SIN 213 – PROJETO DE ALGORITMOS

LARISSA GONÇALVES DE ARAÚJO – 2467

RELATÓRIO DE ANÁLISE DE DESEMPENHO DO ALGORITMO QUICKSORT NA VERSÃO 1, 2 E 3

Rio Paranaíba, 2015

Sumário

1. Primeiro resultado        

2. Segundo Resultado        

3. Terceiro Resultado        

3.1 Tabela Quicksort versão 1        

3.2 Tabela Quicksort versão 2        

3.3 Tabela Quicksort versão 3        

4. Quarto Resultado        

4.1 Gráfico Quicksort versão 1        

4.2 Gráfico Quicksort versão 2        

4.3 Gráfico Quicksort versão 3        

5. Quinto Resultado – Conclusão        

Introdução

Algoritmos, em geral, são um conjunto de passos que tem como propósito a resolução de um certo problema. Existem diversos tipos de algoritmos, e uns dos principais são os algoritmos de ordenação, que são usados para ordenar uma lista de números ou palavras conforme sua exigência.

São várias as implementações de algoritmos de ordenação, como por exemplo Insertionsort, Selectionsort, Mergesort, dentre outros. Cada uma possui suas características, que diferem em relação ao tempo de execução e o gasto de memória no melhor e no pior caso.

Neste trabalho será realizada uma análise o algoritmo Quicksort que, por comparação, é o algoritmo de ordenação mais eficiente. Ele utiliza da estratégia de divisão e conquista e tem como base o particionamento chamado de forma recursiva. Sua complexidade de tempo é O(n log 2 n) no melhor caso e O(n²) no pior caso.

A ideia básica do Quicksort é dividir o problema de ordenar (um conjunto com n itens) em dois problemas menores. Para isso, ele utiliza como base um elemento pivô que é arranjado de maneira que fique entre os menores e os maiores valores do conjunto. Porém, existem outras implementações que diferem da ideia principal do algoritmo.

O objetivo deste trabalho é implementar três versões distintas do algoritmo Quicksort. Em cada uma dessas versões, o pivô é definido de formas diferentes, escolhendo o pivô através das extremidades ou usando a mediana.

Será levado em consideração o tempo gasto para tamanhos de instância que vão de 10 a 1000000, nas ordens crescente, decrescente e aleatória, isso para cada uma das versões. A partir da análise do resultado desses diferentes algoritmos, será possível concluir qual versão do Quicksort tem mais desempenho em relação ao tempo de processamento.

1. Primeiro resultado

Porque o procedimento particiona tem tempo linear O(n)?

Particiona(A, p, r)

x = A[r]                                                   O(1)

i = p−1                                                     O(1)

for j = p até r − 1 do                                O(n)

               if A[j] ≤ x then                         O(n)

                      i = i + 1                              2 O(n)

                     A[i] ↔ A[j]                         2 O(n)

A[i+1] ↔ A[r]                                         2 O(1)

devolva i + 1                                                 2 O(1)

O(1) + O(1) + O(n) + O(n) + 2 O(n) + 2 O(n) + 2 O(1) + 2 O(1) = 6 O(1) + 6 O(n)

6 O(n) -> Maior valor de complexidade.

Independente das entradas, cada elemento do vetor é comparado com o pivô, trocando os elementos de posição. Por isso o procedimento particiona tem tempo linear.

2. Segundo Resultado

Porque o quicksort não tem a fase de combinação?

O método de ordenação do Quicksort utiliza do princípio da divisão e conquista, que diz que classificar dois vetores de tamanho n/2 é mais fácil que classificar um vetor de tamanho n.

Dividir: O arranjo A[p..r] é reorganizado em dois subarranjos (possivelmente vazios) A[p..q-1] e A[q+1..r] tais que cada elemento de A[p..q-1] é menor que ou igual a A[q] que, por sua vez, é igual ou menor a cada elemento de A[q+1..r]. O índice q é calculado como parte desse procedimento de particionamento.

Conquistar: Os dois subarranjos A[p..q-1] e A[q+1..r] são ordenados por chamadas recursivas a quicksort.

Combinar: Como os subarranjos são ordenados localmente, não é necessário nenhum trabalho para combiná-los: o arranjo A[p..r] inteiro agora está ordenado.

3. Terceiro Resultado

3.1 Tabela Quicksort versão 1

Tamanho da instância	Crescente	Decrescente	Randômico
10	0	0	0
100	0	0	0
1000	0	0,001	0,001
10000	0,004	0,004	0,007
100000	0,051	0,04	0,083
1000000	0,539	0,547	1,028

3.2 Tabela Quicksort versão 2

Tamanho da instância	Crescente	Decrescente	Randômico
10	0	0	0
100	0	0	0
1000	0	0	0,001
10000	0,001	0,003	0,001
100000	0,03	0,019	0,023
1000000	0,171	0,213	0,243

3.3 Tabela Quicksort versão 3

Tamanho da instância	Crescente	Decrescente	Randômico
10	0	0	0
100	0	0	0
1000	0	0	0
10000	0,001	0,001	0,005
100000	0,019	0,014	0,061
1000000	0,265	0,161	0,623

4. Quarto Resultado

4.1 Gráfico Quicksort versão 1

[pic 1]

4.2 Gráfico Quicksort versão 2

[pic 2]

4.3 Gráfico Quicksort versão 3

[pic 3]

5. Quinto Resultado – Conclusão

Após a execução das três versões do algoritmo quicksort, foi possível ver que ambas possuem um bom desempenho, porém, dependendo da ordenação que se encontra o vetor e da escolha do pivô, pode ocorrer problema de complexidade alta.