Pesquisa e Ordenação - Aula 07 - Métodos de Ordenação (Bin sort - Bucket sort)

Slides da aula de Pesquisa e Ordenação

1. # Pesquisa e Ordenação #
Aula 07 –Métodos de Ordenação
(Bin Sort-BucketSort)
Prof. Leinylson Fontinele Pereira

2. Na aula anterior...
Métodos de Ordenação
#QuickSort
09:21
Pesquisa e Ordenação: Aula 07 –Métodos de Ordenação (Bin Sort-BucketSort)

3. O que vamos aprender?
Métodos de Ordenação
#BucketSort
09:21
Pesquisa e Ordenação: Aula 07 –Métodos de Ordenação (Bin Sort-BucketSort)

4. Vamos começar?
09:21 4
Pesquisa e Ordenação: Aula 07 –Métodos de Ordenação (Bin Sort-BucketSort)

5. 09:21 5
Ordenação com
BucketSort
Pesquisa e Ordenação: Aula 07 –Métodos de Ordenação (Bin Sort-BucketSort)

6. Ordenação com BucketSort
09:36
Pesquisa e Ordenação: Aula 07 –Métodos de Ordenação (Bin Sort-BucketSort)
Pressupõequeaentradaconsisteemnúmerosinteiros
distribuídosuniformementesobreumintervalo
Ouseja,háumlimitenosvaloresdaschaves.
Ointervaloéentãodivididoem??????subintervalosde
tamanhosiguais,oschamadosbuckets(baldes)
Cadachavevaiparaobaldecorrespondenteàsua
faixadevalor

7. Ordenação com BucketSort
09:20
Pesquisa e Ordenação: Aula 07 –Métodos de Ordenação (Bin Sort-BucketSort)
Complexidade:??????(??????)
Quantidadededados:
Muitos,porém,comvaloreslimitados.
UmBucketSortcomapenasdoisbucketsénaverdadeo
Quicksort(compivoteamentoruim).
EstabilidadeeAdaptabilidade
Dependemdoalgoritmodeordenaçãointernadosbuckets.

8. Ordenação com BucketSort
09:36
Pesquisa e Ordenação: Aula 07 –Métodos de Ordenação (Bin Sort-BucketSort)

9. Ordenação com BucketSort
09:36
Pesquisa e Ordenação: Aula 07 –Métodos de Ordenação (Bin Sort-BucketSort)
A lista de idades é:
41,15,17,32,18,28,77??????54

10. Ordenação com BucketSort
09:36
Pesquisa e Ordenação: Aula 07 –Métodos de Ordenação (Bin Sort-BucketSort)
A lista de idades é:
41,15,17,32,18,28,77??????54

11. Ordenação com BucketSort
09:36
Pesquisa e Ordenação: Aula 07 –Métodos de Ordenação (Bin Sort-BucketSort)

12. Ordenação com BucketSort
09:36
Pesquisa e Ordenação: Aula 07 –Métodos de Ordenação (Bin Sort-BucketSort)
A lista final será:
15,17,18,28,32,41,54,77

13. Ordenação com BucketSort
09:36
Pesquisa e Ordenação: Aula 07 –Métodos de Ordenação (Bin Sort-BucketSort)

14. Ordenação com BucketSort
09:36
Pesquisa e Ordenação: Aula 07 –Métodos de Ordenação (Bin Sort-BucketSort)
Cadabaldeéposteriormenteordenado,isoladamentedosdemais

15. Ordenação com BucketSort
09:36
Pesquisa e Ordenação: Aula 07 –Métodos de Ordenação (Bin Sort-BucketSort)
Considerandoolimite[0,1),echavescomdoisdígitos
decimais,determinamosonúmerodebaldescomo:
N=10(0,…9)
Afunçãoparadeterminaçãodoíndicebaldecorretoé
�[??????∗�[??????]]

16. Ordenação com BucketSort
09:36
Pesquisa e Ordenação: Aula 07 –Métodos de Ordenação (Bin Sort-BucketSort)
�=(0.5,0.1,0.3,0.4,0.3,0.2,0.1,0.1,0.5,0.4,0.5)
Listaordenada
0.1,0.1,0.1,0.2,0.3,0.3,0.4,0.4,0.5,0.5,0.5

17. Bucket
A
1 2 3 4 5 6
.74.17.26.72.39.21

18. Bucket: Loop 1
A
1 2 3 4 5 6
.74.17.26.72.39.21
B
0 1 2 3 4 5
n=6

19. Bucket: Loop 2
A
1 2 3 4 5 6
.17.26.72.39.21
B
0 1 2 3 4 5
B[ n A[i] ] = B[ 6X.74 ]=B[ 4.44 ]=B[4]
Para n=6, i=1
.74

20. Bucket: Loop 2
A
1 2 3 4 5 6
.74 .26.72.39.21
B
0 1 2 3 4 5
B[ n A[i] ] = B[ 6X.17 ]=B[ 1.02]=B[1]
Para n=6, i=2
.17
.74

21. Bucket: Loop 2
A
1 2 3 4 5 6
.74.17 .72.39.21
B
0 1 2 3 4 5
B[ n A[i] ] = B[ 6X.26 ]=B[ 1.56]=B[1]
Para n=6, i=3
.74
.26
.17

22. Bucket: Loop 2
A
1 2 3 4 5 6
.74.17.26 .39.21
B
0 1 2 3 4 5
B[ n A[i] ] = B[ 6X.72 ]=B[ 4.32]=B[4]
Para n=6, i=4
.74
.72
.17
.26

23. Bucket: Loop 2
A
1 2 3 4 5 6
.74.17.26.72 .21
B
0 1 2 3 4 5
B[ n A[i] ] = B[ 6X.39 ]=B[ 2.34]=B[2]
Para n=6, i=5
.74
.39
.17
.26
.72

24. Bucket: Loop 2
A
1 2 3 4 5 6
.74.17.26.72.39
B
0 1 2 3 4 5
B[ n A[i] ] = B[ 6X.94 ]=B[ 5.64]=B[5]
Para n=6, i=6
.74
.94
.17
.26
.72
.39

25. Bucket: Fimdo Loop 2
A
1 2 3 4 5 6
.74.17.26.72.39.94
B
0 1 2 3 4 5
.74
.17
.26
.72
.39
.94

26. Bucket: Loop 3
A
1 2 3 4 5 6
.74.17.26.72.39.94
B
0 1 2 3 4 5
Aplicainsertion sort emcadabalde
.17.26 .72.74 .94.39

27. Bucket
A
1 2 3 4 5 6
.74.17.26.72.39.94
B
0 1 2 3 4 5
Concatenaosbaldesemordem
.17.26 .72.74 .94.39
B
0 1 2 3 4 5
.17.26.39.72.74.94
Saídaordenada

28. Exemplo-Bucket Sort
.78
.17
.39
.26
.72
.94
.21
.12
.23
.68
0
1
2
3
4
5
6
7
8
9
1
2
3
4
5
6
7
8
9
10
.21
.12/
.72/
.23/
.78
.94/
.68 /
.39 /
.26
.17
/
/
/
/
A B
Distribuindodentrodos buckets

29. Exemplo-Bucket Sort
0
1
2
3
4
5
6
7
8
9
.23
.17/
.78/
.26/
.72
.94/
.68/
.39/
.21
.12
/
/
/
/
Ordenandocadabucket

30. Exemplo-Bucket Sort
.17.12 .23 .26.21 .39 .68 .78.72 .94 /
Vetorordenado

31. Ordenação com BucketSort
09:36
Pesquisa e Ordenação: Aula 07 –Métodos de Ordenação (Bin Sort-BucketSort)

32. Ordenação com BucketSort
09:36
Pesquisa e Ordenação: Aula 07 –Métodos de Ordenação (Bin Sort-BucketSort)

33. Ordenação com BucketSort
09:36
Pesquisa e Ordenação: Aula 07 –Métodos de Ordenação (Bin Sort-BucketSort)

34. Ordenação com BucketSort
09:36
Pesquisa e Ordenação: Aula 07 –Métodos de Ordenação (Bin Sort-BucketSort)

35. Ordenação com BucketSort
09:36
Pesquisa e Ordenação: Aula 07 –Métodos de Ordenação (Bin Sort-BucketSort)

36. Ordenação com BucketSort
09:36
Pesquisa e Ordenação: Aula 07 –Métodos de Ordenação (Bin Sort-BucketSort)

37. Ordenação com BucketSort
09:36
Pesquisa e Ordenação: Aula 07 –Métodos de Ordenação (Bin Sort-BucketSort)

38. Ordenação com BucketSort
09:36
Pesquisa e Ordenação: Aula 07 –Métodos de Ordenação (Bin Sort-BucketSort)

39. Ordenação com BucketSort
09:36
Pesquisa e Ordenação: Aula 07 –Métodos de Ordenação (Bin Sort-BucketSort)

40. Ordenação com BucketSort
09:36
Pesquisa e Ordenação: Aula 07 –Métodos de Ordenação (Bin Sort-BucketSort)

41. Ordenação com BucketSort
09:36
Pesquisa e Ordenação: Aula 07 –Métodos de Ordenação (Bin Sort-BucketSort)

42. Ordenação com BucketSort
09:36
Pesquisa e Ordenação: Aula 07 –Métodos de Ordenação (Bin Sort-BucketSort)

43. Ordenação com BucketSort
09:36
Pesquisa e Ordenação: Aula 07 –Métodos de Ordenação (Bin Sort-BucketSort)

44. Ordenação com BucketSort
09:36
Pesquisa e Ordenação: Aula 07 –Métodos de Ordenação (Bin Sort-BucketSort)

45. Concluindo...
09:36 45
Pesquisa e Ordenação: Aula 07 –Métodos de Ordenação (Bin Sort-BucketSort)

46. Teorema do macaco infinito
09:36
Pesquisa e Ordenação: Aula 07 –Métodos de Ordenação (Bin Sort-BucketSort)

47. BozoSort(BogoSort)
09:36
Pesquisa e Ordenação: Aula 07 –Métodos de Ordenação (Bin Sort-BucketSort)

48. BozoSort
09:36
Pesquisa e Ordenação: Aula 07 –Métodos de Ordenação (Bin Sort-BucketSort)

49. Nesta aula aprendemos...
Métodos de Ordenação
#BucketSort
09:36
Pesquisa e Ordenação: Aula 07 –Métodos de Ordenação (Bin Sort-BucketSort)

50. Na próxima aula veremos...
Métodos de Ordenação
#Shell Sort
09:36
Pesquisa e Ordenação: Aula 07 –Métodos de Ordenação (Bin Sort-BucketSort)

51. Material: https://sites.google.com/site/leinylsonnassau
09:36
Material baseado nas aulas de:
MD. ShakhawatHossain, Student of Computer Science &
Engineering Dept. University of Rajshahi
Pesquisa e Ordenação: Aula 07 –Métodos de Ordenação (Bin Sort-BucketSort)

52. Alguma Dúvida?
09:36
Até a próxima aula...
[email protected]