Criação de algoritmos de ordenação para diferentes tipos de objetos em diferentes situações,...

Análise de Desempenho dos Algoritmos de Ordenação

Criação de algoritmos de ordenação para diferentes tipos de objetos em diferentes situações, gerando-se estatísticas para análise de desempenho.

Thiago Augusto Pavan RochaRafael Peretta Santos

Introdução

Objetivos do trabalho Metodologia

Cenário I Cenário II Cenário III

Cenário I - Impacto de diferentes estruturas de dados

Objetivo A escolha do tipo de dado a ser

utilizado Objeto Array de inteiros Lista duplamente encadeada

Processo

Cenário I - Diagrama de Sequência

Cenário I - Resultados

1 2 3 4 50

100020003000400050006000700080009000

10000110001200013000140001500016000170001800019000200002100022000230002400025000

16 78 235

6797

18406

0 0 31 313 7030 109 343

7250

24391

QuickSort Vetor Inteiros

QuickSort Lista Encadeada

QuickSort Vetor Registros

Tem

po(m

s)

Conjunto de Elementos

Cenário II - Impacto de variações do Quicksort

Objetivo As diferentes variações do Quicksort:

Quicksort Básico Quicksort Mediana Quicksort Iterativo Quicksort In-Place

Processo

Cenário II - Diagrama de Sequência

Cenário II - Resultados

1 2 3 4 50

10000

20000

30000

40000

50000

60000

70000

80000

90000

100000

110000

120000

130000

140000

150000

160000

170000

180000

16 140 437

15719

83125

0 0 16 16 320 0 0 47 780 110 422

15562

167875

QuickSort Basico

QuickSort InPlace

QuickSort Iterativo

QuickSort Mediano

Tem

po(m

s)

Conjunto de elementos

15,719

1647

15,562

Cenário III - Quicksort X Mergesort

Objetivo Melhor variação do Quicksort

Quicksort In-Place Mergesort Processo

Cenário III – Diagrama de Sequência

Cenário III - Resultados

1 2 3 4 5 60

25

50

75

100

125

150

175

200

225

250

275

300

325

350

375

400

425

450

0 0 016

31

297

0 016

3147

422

QuickSort InPlaceMerge Sort

Tem

po(m

s)

Conjunto de elementos

Resultados

Problemas encontrados Conclusões Espaço para perguntas