Projeto de analise de algoritimo

Ordenação

Belo Horizonte
2013

Selection Sort
Valores
Máximo
Mínimo
Médio
Tempo Médio de Execução

Selection Sort
100
1000
Comparações Trocas Comparações Trocas
5505
655
507125 8625
5439
589
506447 7947
5473
623
506798 8298
0,0000000

0,6896552

10000
Comparações
50079899
50076377
50078319

Trocas
94899
91377
93319

62,7241379

Melhor caso:
O(n2). O melhor caso é de vetor 100, onde possui menos trocas e comparações e o tempo médio de execução é muito baixo.

Pior caso:
O(n2). É o de vetor 10000. Como mostra a tabela e o gráfico. Seu tempo médio de execução é muito alto.

Mesmo havendo o melhor ou o pior caso, não fara diferença, pois o tempo de complexidade é o mesmo.

Insertion Sort

Valores
Máximo
Mínimo
Médio
Tempo Médio de Execução

InsertionSort
100
1000
10000
Comparações Trocas Comparações Trocas Comparações
Trocas
2976
5852
261416
521832
25264569
50519138
2260
4420
244824
488648
24639119
49268238
2570
5041
251640
502279
24955123
49900245
0,0333333

0,4666667

43,7000000

Melhor caso:
O melhor caso quando está ordenado. Complexidade O(n).

Pior caso:
O pior caso mantém-se no vetor de 10000, em ordem decrescente.
Complexidade O(n²).

Quick Sort
QuickSort
Valores

100
Comparações
1159
918
993

Máximo
Mínimo
Médio
Tempo Médio de Execução

1000
Trocas Comparações Trocas
726
16937
521832
645
13377
488648
681
14398
502279

0,0333333

0,0666667

10000
Comparações
195072
170546
180418

Trocas
136389
134187
135436

0,8333333

Melhor caso:
Acontece quando as partições têm sempre o mesmo tamanho, o que acarreta em partições balanceadas.
C(n) = 2C(n/2) + n = n log n – n + 1

Pior caso:
Acontece quando o pivô é sempre o maior ou menor elemento, o que acarreta em partições de tamanho desequilibrado.
C(n) = O(n2)

Shell Sort
ShellSort
Valores
Máximo
Mínimo
Médio
Tempo Médio de Execução

100
Comparações