TGR3_Ordenacion_2015
-
Upload
redaayjimenez -
Category
Documents
-
view
216 -
download
0
Transcript of TGR3_Ordenacion_2015
-
7/25/2019 TGR3_Ordenacion_2015
1/389
Seminario:Algoritmos de ordenacin
Alberto Valderruten y scar Fontenla Romero{alberto.valderruten, oscar.fontenla}@udc.es
Grado en Ingeniera Informtica
-
7/25/2019 TGR3_Ordenacion_2015
2/389
Introduccin
Ejemplos de los siguientes algoritmos de ordenacin:
Shell
Montculos (heapsort)
Fusin (mergesort)
Ordenacin rpida (quicksort)
-
7/25/2019 TGR3_Ordenacion_2015
3/389
Ordenacin de Shell
Ejercicio 1: mostrar el estado del siguiente vector tras cada una de
las iteraciones de su ordenacin mediante el algoritmo de Shell conincrementos (6, 2, 1).
10 4 9 7 8 5 13 3 0 6
1 2 3 4 5 6 7 8 9 10
1 14
11 12
2 11
13 14
-
7/25/2019 TGR3_Ordenacion_2015
4/389
Ordenacin de Shell
Solucin:
10 4 9 7 8 5 13 3 0 6
1 2 3 4 5 6 7 8 9 10
1 14
11 12
2 11
13 14
-
7/25/2019 TGR3_Ordenacion_2015
5/389
Ordenacin de Shell
Solucin:
Incremento = 6
104
97
85
133
06
1 2 3 4 5 6 7 8 9 10
114
11 12
211
13 14
i
-
7/25/2019 TGR3_Ordenacion_2015
6/389
Ordenacin de Shell
Solucin:
Incremento = 6
49
78
5
30
6
1 2 3 4 5 6 7 8 9 10
114
11 12
11
13 14
i
10 13 2
-
7/25/2019 TGR3_Ordenacion_2015
7/389
Ordenacin de Shell
Solucin:
Incremento = 6
39
78
5
40
6
1 2 3 4 5 6 7 8 9 10
114
11 12
11
13 14
i
10 13 2
-
7/25/2019 TGR3_Ordenacion_2015
8/389
Ordenacin de Shell
Solucin:
Incremento = 6
39
78
5
40
6
1 2 3 4 5 6 7 8 9 10
114
11 12
11
13 14
i
10 13 2
-
7/25/2019 TGR3_Ordenacion_2015
9/389
Ordenacin de Shell
Solucin:
Incremento = 6
30
78
5
49
6
1 2 3 4 5 6 7 8 9 10
114
11 12
11
13 14
i
10 13 2
-
7/25/2019 TGR3_Ordenacion_2015
10/389
Ordenacin de Shell
Solucin:
Incremento = 6
30
78
5
49
6
1 2 3 4 5 6 7 8 9 10
114
11 12
11
13 14
i
10 13 2
-
7/25/2019 TGR3_Ordenacion_2015
11/389
Ordenacin de Shell
Solucin:
Incremento = 6
30
68
5
49
7
1 2 3 4 5 6 7 8 9 10
114
11 12
11
13 14
i
10 13 2
-
7/25/2019 TGR3_Ordenacion_2015
12/389
Ordenacin de Shell
Solucin:
Incremento = 6
30
68
5
49
7
1 2 3 4 5 6 7 8 9 10
114
11 12
11
13 14
i
10 13 2
-
7/25/2019 TGR3_Ordenacion_2015
13/389
Ordenacin de Shell
Solucin:
Incremento = 6
30
61
5
49
7
1 2 3 4 5 6 7 8 9 10
814
11 12
11
13 14
i
10 13 2
-
7/25/2019 TGR3_Ordenacion_2015
14/389
Ordenacin de Shell
Solucin:
Incremento = 6
30
61
5
49
7
1 2 3 4 5 6 7 8 9 10
814
11 12
11
13 14
i
10 13 2
-
7/25/2019 TGR3_Ordenacion_2015
15/389
Ordenacin de Shell
Solucin:
Incremento = 6
30
61
5
49
7
1 2 3 4 5 6 7 8 9 10
814
11 12
11
13 14
i
10 13 2
-
7/25/2019 TGR3_Ordenacion_2015
16/389
Ordenacin de Shell
Solucin:
Incremento = 6
30
61
5
49
7
1 2 3 4 5 6 7 8 9 10
814
11 12
11
13 14
i
2 10 13
-
7/25/2019 TGR3_Ordenacion_2015
17/389
Ordenacin de Shell
Solucin:
Incremento = 6
30
61
5
49
7
1 2 3 4 5 6 7 8 9 10
814
11 12
11
13 14
i
2 10 13
-
7/25/2019 TGR3_Ordenacion_2015
18/389
Ordenacin de Shell
Solucin:
Incremento = 6
3 0 6 1 5 4 9 7
1 2 3 4 5 6 7 8 9 10
8 14
11 12
11
13 14
2 10 13
Array 6-ordenado
-
7/25/2019 TGR3_Ordenacion_2015
19/389
Ordenacin de Shell
Solucin:
Incremento = 2
3 0 6 1 5 4 9 7
1 2 3 4 5 6 7 8 9 10
8 14
11 12
11
13 14
2 10 13
-
7/25/2019 TGR3_Ordenacion_2015
20/389
Ordenacin de Shell
Solucin:
Incremento = 2
30
61
5 49
7
1 2 3 4 5 6 7 8 9 10
814
11 12
11
13 14
2 10 13
-
7/25/2019 TGR3_Ordenacion_2015
21/389
Ordenacin de Shell
Solucin:
Incremento = 2
i
30
61
5 49
7
1 2 3 4 5 6 7 8 9 10
814
11 12
11
13 14
2 10 13
-
7/25/2019 TGR3_Ordenacion_2015
22/389
Ordenacin de Shell
Solucin:
Incremento = 2
i
32
61
5 49
7
1 2 3 4 5 6 7 8 9 10
814
11 12
11
13 14
0 10 13
-
7/25/2019 TGR3_Ordenacion_2015
23/389
Ordenacin de Shell
Solucin:
Incremento = 2
i
32
61
5 49
7
1 2 3 4 5 6 7 8 9 10
814
11 12
11
13 14
0 10 13
-
7/25/2019 TGR3_Ordenacion_2015
24/389
Ordenacin de Shell
Solucin:
Incremento = 2
i
32
61
5 49
7
1 2 3 4 5 6 7 8 9 10
814
11 12
11
13 14
0 10 13
-
7/25/2019 TGR3_Ordenacion_2015
25/389
Ordenacin de Shell
Solucin:
Incremento = 2
i
31
62
5 49
7
1 2 3 4 5 6 7 8 9 10
814
11 12
11
13 14
0 10 13
-
7/25/2019 TGR3_Ordenacion_2015
26/389
Ordenacin de Shell
Solucin:
Incremento = 2
i
31
62
5 49
7
1 2 3 4 5 6 7 8 9 10
814
11 12
11
13 14
0 10 13
-
7/25/2019 TGR3_Ordenacion_2015
27/389
Ordenacin de Shell
Solucin:
Incremento = 2
i
31
52
6 49
7
1 2 3 4 5 6 7 8 9 10
814
11 12
11
13 14
0 10 13
-
7/25/2019 TGR3_Ordenacion_2015
28/389
Ordenacin de Shell
Solucin:
Incremento = 2
i
31
52
6 49
7
1 2 3 4 5 6 7 8 9 10
814
11 12
11
13 14
0 10 13
-
7/25/2019 TGR3_Ordenacion_2015
29/389
Ordenacin de Shell
Solucin:
Incremento = 2
i
31
52
6 49
7
1 2 3 4 5 6 7 8 9 10
814
11 12
11
13 14
0 10 13
-
7/25/2019 TGR3_Ordenacion_2015
30/389
Ordenacin de Shell
Solucin:
Incremento = 2
i
31
42
5 69
7
1 2 3 4 5 6 7 8 9 10
814
11 12
11
13 14
0 10 13
-
7/25/2019 TGR3_Ordenacion_2015
31/389
Ordenacin de Shell
Solucin:
Incremento = 2
i
31
42
5 69
7
1 2 3 4 5 6 7 8 9 10
814
11 12
11
13 14
0 10 13
-
7/25/2019 TGR3_Ordenacion_2015
32/389
Ordenacin de Shell
Solucin:
Incremento = 2
i
31
42
5 610
7
1 2 3 4 5 6 7 8 9 10
814
11 12
11
13 14
0 9 13
-
7/25/2019 TGR3_Ordenacion_2015
33/389
Ordenacin de Shell
Solucin:
Incremento = 2
i
31
42
5 610
7
1 2 3 4 5 6 7 8 9 10
814
11 12
11
13 14
0 9 13
-
7/25/2019 TGR3_Ordenacion_2015
34/389
Ordenacin de Shell
Solucin:
Incremento = 2
i
31
42
5 610
7
1 2 3 4 5 6 7 8 9 10
814
11 12
11
13 14
0 9 13
d d h ll
-
7/25/2019 TGR3_Ordenacion_2015
35/389
Ordenacin de Shell
Solucin:
Incremento = 2
i
31
42
5 69
7
1 2 3 4 5 6 7 8 9 10
1014
11 12
11
13 14
0 8 13
d i d h ll
-
7/25/2019 TGR3_Ordenacion_2015
36/389
Ordenacin de Shell
Solucin:
Incremento = 2
i
31
42
5 69
7
1 2 3 4 5 6 7 8 9 10
1014
11 12
11
13 14
0 8 13
O d i d Sh ll
-
7/25/2019 TGR3_Ordenacion_2015
37/389
Ordenacin de Shell
Solucin:
Incremento = 2
i
31
42
5 69
7
1 2 3 4 5 6 7 8 9 10
1014
11 12
11
13 14
0 8 13
O d i d Sh ll
-
7/25/2019 TGR3_Ordenacion_2015
38/389
Ordenacin de Shell
Solucin:
Incremento = 2
i
31
42
5 69
7
1 2 3 4 5 6 7 8 9 10
1014
11 12
11
13 14
0 8 13
O d i d Sh ll
-
7/25/2019 TGR3_Ordenacion_2015
39/389
Ordenacin de Shell
Solucin:
Incremento = 2
i
31
42
5 69
7
1 2 3 4 5 6 7 8 9 10
1011
11 12
14
13 14
0 8 13
O d i d Sh ll
-
7/25/2019 TGR3_Ordenacion_2015
40/389
Ordenacin de Shell
Solucin:
Incremento = 2
3 1 4 2 5 6 9 7
1 2 3 4 5 6 7 8 9 10
10 11
11 12
14
13 14
0 8 13
Array 2-ordenado (y 6 ordenado)
O d i d Sh ll
-
7/25/2019 TGR3_Ordenacion_2015
41/389
Ordenacin de Shell
Solucin:
Incremento = 1
3 1 4 2 5 6 9 7
1 2 3 4 5 6 7 8 9 10
10 11
11 12
14
13 14
0 8 13
O d i d Sh ll
-
7/25/2019 TGR3_Ordenacion_2015
42/389
Ordenacin de Shell
Solucin:
Incremento = 1
3 1 4 2 5 6 9 7
1 2 3 4 5 6 7 8 9 10
10 11
11 12
14
13 14
0 8 13
O d i d Sh ll
-
7/25/2019 TGR3_Ordenacion_2015
43/389
Ordenacin de Shell
Solucin:
Incremento = 1
3 1 4 2 5 6 9 7
1 2 3 4 5 6 7 8 9 10
10 11
11 12
14
13 14
0 8 13
i
Ordenacin de Shell
-
7/25/2019 TGR3_Ordenacion_2015
44/389
Ordenacin de Shell
Solucin:
Incremento = 1
3 1 4 2 5 6 9 7
1 2 3 4 5 6 7 8 9 10
10 11
11 12
14
13 14
0 8 13
i
Ordenacin de Shell
-
7/25/2019 TGR3_Ordenacion_2015
45/389
Ordenacin de Shell
Solucin:
Incremento = 1
1 3 4 2 5 6 9 7
1 2 3 4 5 6 7 8 9 10
10 11
11 12
14
13 14
0 8 13
i
Ordenacin de Shell
-
7/25/2019 TGR3_Ordenacion_2015
46/389
Ordenacin de Shell
Solucin:
Incremento = 1
1 3 4 2 5 6 9 7
1 2 3 4 5 6 7 8 9 10
10 11
11 12
14
13 14
0 8 13
i
Ordenacin de Shell
-
7/25/2019 TGR3_Ordenacion_2015
47/389
Ordenacin de Shell
Solucin:
Incremento = 1
1 3 4 2 5 6 9 7
1 2 3 4 5 6 7 8 9 10
10 11
11 12
14
13 14
0 8 13
i
Ordenacin de Shell
-
7/25/2019 TGR3_Ordenacion_2015
48/389
Ordenacin de Shell
Solucin:
Incremento = 1
1 2 3 4 5 6 9 7
1 2 3 4 5 6 7 8 9 10
10 11
11 12
14
13 14
0 8 13
i
Ordenacin de Shell
-
7/25/2019 TGR3_Ordenacion_2015
49/389
Ordenacin de Shell
Solucin:
Incremento = 1
1 2 3 4 5 6 9 7
1 2 3 4 5 6 7 8 9 10
10 11
11 12
14
13 14
0 8 13
i
Ordenacin de Shell
-
7/25/2019 TGR3_Ordenacion_2015
50/389
Ordenacin de Shell
Solucin:
Incremento = 1
1 2 3 4 5 6 9 7
1 2 3 4 5 6 7 8 9 10
10 11
11 12
14
13 14
0 8 13
i
Ordenacin de Shell
-
7/25/2019 TGR3_Ordenacion_2015
51/389
Ordenacin de Shell
Solucin:
Incremento = 1
1 2 3 4 5 6 9 7
1 2 3 4 5 6 7 8 9 10
10 11
11 12
14
13 14
0 8 13
i
Ordenacin de Shell
-
7/25/2019 TGR3_Ordenacion_2015
52/389
Ordenacin de Shell
Solucin:
Incremento = 1
1 2 3 4 5 8 9 7
1 2 3 4 5 6 7 8 9 10
10 11
11 12
14
13 14
0 6 13
i
Ordenacin de Shell
-
7/25/2019 TGR3_Ordenacion_2015
53/389
Ordenacin de Shell
Solucin:
Incremento = 1
1 2 3 4 5 8 9 7
1 2 3 4 5 6 7 8 9 10
10 11
11 12
14
13 14
0 6 13
i
Ordenacin de Shell
-
7/25/2019 TGR3_Ordenacion_2015
54/389
Ordenacin de Shell
Solucin:
Incremento = 1
1 2 3 4 5 8 9 7
1 2 3 4 5 6 7 8 9 10
10 11
11 12
14
13 14
0 6 13
i
Ordenacin de Shell
-
7/25/2019 TGR3_Ordenacion_2015
55/389
Ordenacin de Shell
Solucin:
Incremento = 1
1 2 3 4 5 7 8 9
1 2 3 4 5 6 7 8 9 10
10 11
11 12
14
13 14
0 6 13
i
Ordenacin de Shell
-
7/25/2019 TGR3_Ordenacion_2015
56/389
Ordenacin de Shell
Solucin:
Incremento = 1
1 2 3 4 5 7 8 9
1 2 3 4 5 6 7 8 9 10
10 11
11 12
14
13 14
0 6 13
i
Ordenacin de Shell
-
7/25/2019 TGR3_Ordenacion_2015
57/389
Ordenacin de Shell
Solucin:
Incremento = 1
1 2 3 4 5 7 8 9
1 2 3 4 5 6 7 8 9 10
10 11
11 12
14
13 14
0 6 13
i
Ordenacin de Shell
-
7/25/2019 TGR3_Ordenacion_2015
58/389
Ordenacin de Shell
Solucin:
Incremento = 1
1 2 3 4 5 7 8 9
1 2 3 4 5 6 7 8 9 10
10 11
11 12
14
13 14
0 6 13
i
Ordenacin de Shell
-
7/25/2019 TGR3_Ordenacion_2015
59/389
Ordenacin de Shell
Solucin:
Incremento = 1
1 2 3 4 5 7 8 9
1 2 3 4 5 6 7 8 9 10
10 11
11 12
14
13 14
0 6 13
i
Ordenacin de Shell
-
7/25/2019 TGR3_Ordenacion_2015
60/389
Ordenacin de Shell
Solucin:
Incremento = 1
1 2 3 4 5 7 8 9
1 2 3 4 5 6 7 8 9 10
10 11
11 12
14
13 14
0 6 13
Array 1-ordenado (ordenado)
Ordenacin de Shell
-
7/25/2019 TGR3_Ordenacion_2015
61/389
Ordenacin de Shell
Solucin:
1 2 3 4 5 7 8 9
1 2 3 4 5 6 7 8 9 10
10 11
11 12
14
13 14
0 6 13
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
62/389
Ordenacin de Shell: ejemplo del peor caso
Ejercicio 2: mostrar el estado del siguiente vector tras cada una de
las iteraciones de su ordenacin mediante el algoritmo de Shell conincrementos (8, 4, 2, 1).
8 16 7 15 6 14 5 13 4 12
1 2 3 4 5 6 7 8 9 10
3 11
11 12
2 10
13 14
1 9
15 16
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
63/389
j p p
Solucin:
8 16 7 15 6 14 5 13 4 12
1 2 3 4 5 6 7 8 9 10
3 11
11 12
2 10
13 14
1 9
15 16
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
64/389
j p p
Solucin:
8 167
156
145
13
4 12
1 2 3 4 5 6 7 8 9 10
311
11 12
210
13 14
1
9
15 16
Incremento = 8
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
65/389
j p p
Solucin:
4 167
156
145
13
8 12
1 2 3 4 5 6 7 8 9 10
311
11 12
210
13 14
1
9
15 16
Incremento = 8
i
-
7/25/2019 TGR3_Ordenacion_2015
66/389
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
67/389
j p p
Solucin:
4 127
156
145
13
8 16
1 2 3 4 5 6 7 8 9 10
311
11 12
210
13 14
1
9
15 16
Incremento = 8
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
68/389
j p p
Solucin:
4 127
156
145
13
8 16
1 2 3 4 5 6 7 8 9 10
311
11 12
210
13 14
1
9
15 16
Incremento = 8
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
69/389
j p p
Solucin:
4 123
156
145
13
8 16
1 2 3 4 5 6 7 8 9 10
711
11 12
210
13 14
1
9
15 16
Incremento = 8
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
70/389
Solucin:
4 123
156
145
13
8 16
1 2 3 4 5 6 7 8 9 10
711
11 12
210
13 14
1
9
15 16
Incremento = 8
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
71/389
Solucin:
4 123
116
145
13
8 16
1 2 3 4 5 6 7 8 9 10
715
11 12
210
13 14
1
9
15 16
Incremento = 8
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
72/389
Solucin:
4 123
116
145
13
8 16
1 2 3 4 5 6 7 8 9 10
715
11 12
210
13 14
1
9
15 16
Incremento = 8
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
73/389
Solucin:
4 123
112
145
13
8 16
1 2 3 4 5 6 7 8 9 10
715
11 12
610
13 14
19
15 16
Incremento = 8
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
74/389
Solucin:
4 123
112
145
13
8 16
1 2 3 4 5 6 7 8 9 10
715
11 12
610
13 14
19
15 16
Incremento = 8
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
75/389
Solucin:
4 123
112
105
13
8 16
1 2 3 4 5 6 7 8 9 10
715
11 12
614
13 14
19
15 16
Incremento = 8
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
76/389
Solucin:
4 123
112
105
13
8 16
1 2 3 4 5 6 7 8 9 10
715
11 12
614
13 14
19
15 16
Incremento = 8
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
77/389
Solucin:
4 123
112
101
13
8 16
1 2 3 4 5 6 7 8 9 10
715
11 12
614
13 14
59
15 16
Incremento = 8
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
78/389
Solucin:
4 123
112
101
13
8 16
1 2 3 4 5 6 7 8 9 10
715
11 12
614
13 14
59
15 16
Incremento = 8
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
79/389
Solucin:
4 123
112
101
9
8 16
1 2 3 4 5 6 7 8 9 10
715
11 12
614
13 14
513
15 16
Incremento = 8
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
80/389
Solucin:
4 12 3 11 2 10 1 9 8 16
1 2 3 4 5 6 7 8 9 10
7 15
11 12
6 14
13 14
5 13
15 16
Incremento = 8
Array 8-ordenado
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
81/389
Solucin:
4 12 3 11 2 10 1 9 8 16
1 2 3 4 5 6 7 8 9 10
7 15
11 12
6 14
13 14
5 13
15 16
Incremento = 4
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
82/389
Solucin:
4 123
11
2 101
9
8 16
1 2 3 4 5 6 7 8 9 10
715
11 12
6 14
13 14
513
15 16
Incremento = 4
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
83/389
Solucin:
2 123
11
4 101
9
8 16
1 2 3 4 5 6 7 8 9 10
715
11 12
6 14
13 14
513
15 16
Incremento = 4
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
84/389
Solucin:
2 123
11
4 101
9
8 16
1 2 3 4 5 6 7 8 9 10
715
11 12
6 14
13 14
513
15 16
Incremento = 4
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
85/389
Solucin:
2 103
11
4 121
9
8 16
1 2 3 4 5 6 7 8 9 10
715
11 12
6 14
13 14
513
15 16
Incremento = 4
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
86/389
Solucin:
2 103
11
4 121
9
8 16
1 2 3 4 5 6 7 8 9 10
715
11 12
6 14
13 14
513
15 16
Incremento = 4
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
87/389
Solucin:
2 101
11
4 123
9
8 16
1 2 3 4 5 6 7 8 9 10
715
11 12
6 14
13 14
513
15 16
Incremento = 4
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
88/389
Solucin:
2 101
11
4 123
9
8 16
1 2 3 4 5 6 7 8 9 10
715
11 12
6 14
13 14
513
15 16
Incremento = 4
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
89/389
Solucin:
2 101
9
4 123
11
8 16
1 2 3 4 5 6 7 8 9 10
715
11 12
6 14
13 14
513
15 16
Incremento = 4
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
90/389
Solucin:
2 101
9
4 123
11
8 16
1 2 3 4 5 6 7 8 9 10
715
11 12
6 14
13 14
513
15 16
Incremento = 4
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
91/389
Solucin:
2 101
9
4 123
11
8 16
1 2 3 4 5 6 7 8 9 10
715
11 12
6 14
13 14
513
15 16
Incremento = 4
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
92/389
Solucin:
2 101
9
4 123
11
8 16
1 2 3 4 5 6 7 8 9 10
715
11 12
6 14
13 14
513
15 16
Incremento = 4
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
93/389
Solucin:
2 101
9
4 123
11
8 16
1 2 3 4 5 6 7 8 9 10
715
11 12
6 14
13 14
513
15 16
Incremento = 4
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
94/389
Solucin:
2 101
9
4 123
11
8 16
1 2 3 4 5 6 7 8 9 10
715
11 12
6 14
13 14
513
15 16
Incremento = 4
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
95/389
Solucin:
2 101
9
4 123
11
6 16
1 2 3 4 5 6 7 8 9 10
715
11 12
8 14
13 14
513
15 16
Incremento = 4
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
96/389
Solucin:
2 101
9
4 123
11
6 16
1 2 3 4 5 6 7 8 9 10
715
11 12
8 14
13 14
513
15 16
Incremento = 4
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
97/389
Solucin:
2 101
9
4 123
11
6 14
1 2 3 4 5 6 7 8 9 10
715
11 12
8 16
13 14
513
15 16
Incremento = 4
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
98/389
Solucin:
2 101
9
4 123
11
6 14
1 2 3 4 5 6 7 8 9 10
715
11 12
8 16
13 14
513
15 16
Incremento = 4
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
99/389
Solucin:
210
19
412
311
614
1 2 3 4 5 6 7 8 9 10
515
11 12
816
13 14
713
15 16
Incremento = 4
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
100/389
Solucin:
210
19
412
311
614
1 2 3 4 5 6 7 8 9 10
515
11 12
816
13 14
713
15 16
Incremento = 4
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
101/389
Solucin:
210
19
412
311
614
1 2 3 4 5 6 7 8 9 10
513
11 12
816
13 14
715
15 16
Incremento = 4
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
102/389
Solucin:
2 10 1 9 4 12 3 11 6 14
1 2 3 4 5 6 7 8 9 10
5 13
11 12
8 16
13 14
7 15
15 16
Incremento = 4
Array 4-ordenado
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
103/389
Solucin:
2 10 1 9 4 12 3 11 6 14
1 2 3 4 5 6 7 8 9 10
5 13
11 12
8 16
13 14
7 15
15 16
Incremento = 2
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
104/389
Solucin:
210
19
412
311
614
1 2 3 4 5 6 7 8 9 10
513
11 12
816
13 14
715
15 16
Incremento = 2
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
105/389
Solucin:
110
29
412
311
614
1 2 3 4 5 6 7 8 9 10
513
11 12
816
13 14
715
15 16
Incremento = 2
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
106/389
Solucin:
110
29
412
311
614
1 2 3 4 5 6 7 8 9 10
513
11 12
816
13 14
715
15 16
Incremento = 2
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
107/389
Solucin:
19
210
412
311
614
1 2 3 4 5 6 7 8 9 10
513
11 12
816
13 14
715
15 16
Incremento = 2
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
108/389
Solucin:
19
210
412
311
614
1 2 3 4 5 6 7 8 9 10
513
11 12
816
13 14
715
15 16
Incremento = 2
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
109/389
Solucin:
19
210
412
311
614
1 2 3 4 5 6 7 8 9 10
513
11 12
816
13 14
715
15 16
Incremento = 2
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
110/389
Solucin:
19
210
412
311
614
1 2 3 4 5 6 7 8 9 10
513
11 12
816
13 14
715
15 16
Incremento = 2
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
111/389
Solucin:
19
210
312
411
614
1 2 3 4 5 6 7 8 9 10
513
11 12
816
13 14
715
15 16
Incremento = 2
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
112/389
Solucin:
19
210
312
411
614
1 2 3 4 5 6 7 8 9 10
513
11 12
816
13 14
715
15 16
Incremento = 2
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
113/389
Solucin:
19
210
311
412
614
1 2 3 4 5 6 7 8 9 10
513
11 12
816
13 14
715
15 16
Incremento = 2
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
114/389
Solucin:
19
210
311
412
614
1 2 3 4 5 6 7 8 9 10
513
11 12
816
13 14
715
15 16
Incremento = 2
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
115/389
Solucin:
19
210
311
412
614
1 2 3 4 5 6 7 8 9 10
513
11 12
816
13 14
715
15 16
Incremento = 2
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
116/389
Solucin:
19
210
311
412
614
1 2 3 4 5 6 7 8 9 10
513
11 12
816
13 14
715
15 16
Incremento = 2
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
117/389
Solucin:
19
210
311
412
514
1 2 3 4 5 6 7 8 9 10
613
11 12
816
13 14
715
15 16
Incremento = 2
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
118/389
Solucin:
19
210
311
412
514
1 2 3 4 5 6 7 8 9 10
613
11 12
816
13 14
715
15 16
Incremento = 2
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
119/389
Solucin:
19
210
311
412
513
1 2 3 4 5 6 7 8 9 10
614
11 12
816
13 14
715
15 16
Incremento = 2
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
120/389
Solucin:
19
210
311
412
513
1 2 3 4 5 6 7 8 9 10
614
11 12
816
13 14
715
15 16
Incremento = 2
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
121/389
Solucin:
19
210
311
412
513
1 2 3 4 5 6 7 8 9 10
614
11 12
816
13 14
715
15 16
Incremento = 2
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
122/389
Solucin:
19
210
311
412
513
1 2 3 4 5 6 7 8 9 10
614
11 12
816
13 14
715
15 16
Incremento = 2
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
123/389
Solucin:
19
210
311
412
513
1 2 3 4 5 6 7 8 9 10
614
11 12
716
13 14
815
15 16
Incremento = 2
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
124/389
Solucin:
19
210
311
412
513
1 2 3 4 5 6 7 8 9 10
614
11 12
716
13 14
815
15 16
Incremento = 2
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
125/389
Solucin:
19
210
311
412
513
1 2 3 4 5 6 7 8 9 10
614
11 12
715
13 14
816
15 16
Incremento = 2
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
126/389
Solucin:
1 9 2 10 3 11 4 12 5 13
1 2 3 4 5 6 7 8 9 10
6 14
11 12
7 15
13 14
8 16
15 16
Incremento = 2
Array 2-ordenado
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
127/389
Solucin:
1 9 2 10 3 11 4 12 5 13
1 2 3 4 5 6 7 8 9 10
6 14
11 12
7 15
13 14
8 16
15 16
Incremento = 1
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
128/389
Solucin:
1 9 2 10 3 11 4 12 5 13
1 2 3 4 5 6 7 8 9 10
6 14
11 12
7 15
13 14
8 16
15 16
Incremento = 1
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
129/389
Solucin:
1 9 2 10 3 11 4 12 5 13
1 2 3 4 5 6 7 8 9 10
6 14
11 12
7 15
13 14
8 16
15 16
Incremento = 1
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
130/389
Solucin:
1 2 9 10 3 11 4 12 5 13
1 2 3 4 5 6 7 8 9 10
6 14
11 12
7 15
13 14
8 16
15 16
Incremento = 1
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
131/389
Solucin:
1 2 9 10 3 11 4 12 5 13
1 2 3 4 5 6 7 8 9 10
6 14
11 12
7 15
13 14
8 16
15 16
Incremento = 1
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
132/389
Solucin:
1 2 9 10 3 11 4 12 5 13
1 2 3 4 5 6 7 8 9 10
6 14
11 12
7 15
13 14
8 16
15 16
Incremento = 1
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
133/389
Solucin:
1 2 3 9 10 11 4 12 5 13
1 2 3 4 5 6 7 8 9 10
6 14
11 12
7 15
13 14
8 16
15 16
Incremento = 1
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
134/389
Solucin:
1 2 3 9 10 11 4 12 5 13
1 2 3 4 5 6 7 8 9 10
6 14
11 12
7 15
13 14
8 16
15 16
Incremento = 1
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
135/389
Solucin:
1 2 3 9 10 11 4 12 5 13
1 2 3 4 5 6 7 8 9 10
6 14
11 12
7 15
13 14
8 16
15 16
Incremento = 1
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
136/389
Solucin:
1 2 3 4 9 10 11 12 5 13
1 2 3 4 5 6 7 8 9 10
6 14
11 12
7 15
13 14
8 16
15 16
Incremento = 1
i
Ordenacin de Shell: ejemplo del peor caso
-
7/25/2019 TGR3_Ordenacion_2015
137/389
Solucin:
1 2 3 4 9 10 11 12 5 13
1 2 3 4 5 6 7 8 9 10
6 14
11 12
7 15
13 14
8 16
15 16
Incremento = 1
i
Ordenacin de Shell: ejemplo del peor caso
l
-
7/25/2019 TGR3_Ordenacion_2015
138/389
Solucin:
1 2 3 4 9 10 11 12 5 13
1 2 3 4 5 6 7 8 9 10
6 14
11 12
7 15
13 14
8 16
15 16
Incremento = 1
i
Ordenacin de Shell: ejemplo del peor caso
S l i
-
7/25/2019 TGR3_Ordenacion_2015
139/389
Solucin:
1 2 3 4 5 9 10 11 12 13
1 2 3 4 5 6 7 8 9 10
6 14
11 12
7 15
13 14
8 16
15 16
Incremento = 1
i
Ordenacin de Shell: ejemplo del peor caso
S l i
-
7/25/2019 TGR3_Ordenacion_2015
140/389
Solucin:
1 2 3 4 5 9 10 11 12 13
1 2 3 4 5 6 7 8 9 10
6 14
11 12
7 15
13 14
8 16
15 16
Incremento = 1
i
Ordenacin de Shell: ejemplo del peor caso
S l i
-
7/25/2019 TGR3_Ordenacion_2015
141/389
Solucin:
1 2 3 4 5 9 10 11 12 13
1 2 3 4 5 6 7 8 9 10
6 14
11 12
7 15
13 14
8 16
15 16
Incremento = 1
i
Ordenacin de Shell: ejemplo del peor caso
S l i
-
7/25/2019 TGR3_Ordenacion_2015
142/389
Solucin:
1 2 3 4 5 6 9 10 11 12
1 2 3 4 5 6 7 8 9 10
13 14
11 12
7 15
13 14
8 16
15 16
Incremento = 1
i
Ordenacin de Shell: ejemplo del peor caso
S l i
-
7/25/2019 TGR3_Ordenacion_2015
143/389
Solucin:
1 2 3 4 5 6 9 10 11 12
1 2 3 4 5 6 7 8 9 10
13 14
11 12
7 15
13 14
8 16
15 16
Incremento = 1
i
Ordenacin de Shell: ejemplo del peor caso
S l i
-
7/25/2019 TGR3_Ordenacion_2015
144/389
Solucin:
1 2 3 4 5 6 9 10 11 12
1 2 3 4 5 6 7 8 9 10
13 14
11 12
7 15
13 14
8 16
15 16
Incremento = 1
i
Ordenacin de Shell: ejemplo del peor caso
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
145/389
Solucin:
1 2 3 4 5 6 7 9 10 11
1 2 3 4 5 6 7 8 9 10
12 13
11 12
14 15
13 14
8 16
15 16
Incremento = 1
i
Ordenacin de Shell: ejemplo del peor caso
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
146/389
Solucin:
1 2 3 4 5 6 7 9 10 11
1 2 3 4 5 6 7 8 9 10
12 13
11 12
14 15
13 14
8 16
15 16
Incremento = 1
i
Ordenacin de Shell: ejemplo del peor caso
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
147/389
Solucin:
1 2 3 4 5 6 7 9 10 11
1 2 3 4 5 6 7 8 9 10
12 13
11 12
14 15
13 14
8 16
15 16
Incremento = 1
i
Ordenacin de Shell: ejemplo del peor caso
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
148/389
Solucin:
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
11 12
11 12
13 14
13 14
15 16
15 16
Incremento = 1
i
Ordenacin de Shell: ejemplo del peor caso
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
149/389
Solucin:
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
11 12
11 12
13 14
13 14
15 16
15 16
Incremento = 1
i
Ordenacin de Shell: ejemplo del peor caso
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
150/389
Solucin:
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
11 12
11 12
13 14
13 14
15 16
15 16
Incremento = 1
Array 1-ordenado (ordenado)
Ordenacin de Shell: ejemplo del peor caso
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
151/389
Solucin:
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
11 12
11 12
13 14
13 14
15 16
15 16
Ordenacin por montculos
Ejercicio 1: construir los montculos generados para la ordenacin
-
7/25/2019 TGR3_Ordenacion_2015
152/389
Ejercicio 1: construir los montculos generados para la ordenacindel siguiente vector de datos
9 12 2 10 3 4 1 11 5 68 7
1 2 3 4 5 6 7 8 9 10 11 12
Ordenacin por montculos
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
153/389
Solucin:
12
11 8
4 10
2 1 9 5
6 7
3
Paso 1: Crear montculo
Ordenacin por montculos
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
154/389
Solucin:
12
11 8
4 10
2 1 9 5
6 7
3
Paso 2: Eliminar el mayor: 12 (y hundir el 3)
Ordenacin por montculos
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
155/389
Solucin:
11
10 8
4 9
2 1 3 5
6 7
Paso 3: Eliminar el mayor: 11 (y hundir el 5)
Ordenacin por montculos
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
156/389
Solucin:
10
9 8
4 5
2 1 3
6 7
Paso 4: Eliminar el mayor: 10 (y hundir el 3)
Ordenacin por montculos
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
157/389
Solucin:
9
5 8
4 3
2 1
6 7
Paso 5: Eliminar el mayor: 9 (y hundir el 1)
Ordenacin por montculos
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
158/389
Solucin:
8
5 7
4 3
2
6 1
Paso 6: Eliminar el mayor: 8 (y hundir el 2)
Ordenacin por montculos
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
159/389
Solucin:
7
5 6
4 3 2 1
Paso 7: Eliminar el mayor: 7 (y hundir el 1)
Ordenacin por montculos
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
160/389
6
5 2
4 3 1
Paso 8: Eliminar el mayor: 6 (y hundir el 1)
Ordenacin por montculos
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
161/389
5
4 2
1 3
Paso 9: Eliminar el mayor: 5 (y hundir el 3)
Ordenacin por montculos
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
162/389
4
3 2
1
Paso 10: Eliminar el mayor: 4 (y hundir el 1)
Ordenacin por montculos
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
163/389
3
1 2
Paso 11: Eliminar el mayor: 3 (y hundir el 2)
Ordenacin por montculos
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
164/389
2
1
Paso 12: Eliminar el mayor: 2 (y hundir el 1)
Ordenacin por montculos
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
165/389
1
Paso 13: Eliminar el mayor: 1 fin del proceso
Ordenacin por montculos
Ejercicio 2: construir los montculos generados para la ordenacin
-
7/25/2019 TGR3_Ordenacion_2015
166/389
del siguiente vector de datos
12 1 7 6 5 10 14 9
1 2 3 4 5 6 7 8 9 10
2 11
11 12
8
13 14
4 13 3
Ordenacin por montculos
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
167/389
14
12 13
10 9
4 7 6 2
11 8
5
Paso 1: Crear montculo
3 1
Ordenacin por montculos
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
168/389
14
12 13
10 9
4 7 6 2
11 8
5 3 1
Paso 2: Eliminar el mayor: 14 (y hundir el 1)
Ordenacin por montculos
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
169/389
13
12 11
10 9
4 7 6 2
5 8
1 3
Paso 3: Eliminar el mayor: 13 (y hundir el 3)
Ordenacin por montculos
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
170/389
12
10 11
7 9
4 3 6 2
5 8
1
Paso 4: Eliminar el mayor: 12 (y hundir el 1)
Ordenacin por montculos
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
171/389
11
10 8
7 9
4 3 6 2
5 1
Paso 5: Eliminar el mayor: 11 (y hundir el 2)
Ordenacin por montculos
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
172/389
10
9 8
7 6
4 3 2
5 1
Paso 6: Eliminar el mayor: 10 (y hundir el 2)
Ordenacin por montculos
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
173/389
9
7 8
4 6
2 3
5 1
Paso 7: Eliminar el mayor: 9 (y hundir el 3)
Ordenacin por montculos
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
174/389
8
7 5
4 6
2
3 1
Paso 8: Eliminar el mayor: 8 (y hundir el 2)
Ordenacin por montculos
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
175/389
7
6 5
4 2 3 1
Paso 9: Eliminar el mayor: 7 (y hundir el 1)
Ordenacin por montculos
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
176/389
6
4 5
1 2 3
Paso 10: Eliminar el mayor: 6 (y hundir el 3)
Ordenacin por montculos
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
177/389
5
4 3
1 2
Paso 11: Eliminar el mayor: 5 (y hundir el 2)
Ordenacin por montculos
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
178/389
4
2 3
1
Paso 12: Eliminar el mayor: 4 (y hundir el 1)
Ordenacin por montculos
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
179/389
3
2 1
Paso 13: Eliminar el mayor: 3 (y hundir el 1)
Ordenacin por montculos
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
180/389
2
1
Paso 14: Eliminar el mayor: 2 (y hundir el 1)
Ordenacin por montculos
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
181/389
1
Paso 15: Eliminar el mayor: 1 fin del proceso
Ordenacin por fusin
Ejercicio 1: construir el rbol recursivo que genera el algoritmo porf i t i ( b l 0)
-
7/25/2019 TGR3_Ordenacion_2015
182/389
fusin puramente recursivo (umbral = 0).
7 11 15 2 8 2 3 10 7 1 413 1 5
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
183/389
7 11 15 2 8 2 3 10 7 1 413 1 5
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
184/389
7 11 15 2 8 2 3 10 7 1 413 1 5
7 11 15 2 813 1
Llamadarecursiva
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
185/389
7 11 15 2 8 2 3 10 7 1 413 1 5
7 11 15 2 813 1
7 11 1513
Llamadarecursiva
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
186/389
7 11 15 2 8 2 3 10 7 1 413 1 5
7 11 15 2 813 1
7 11 1513
713
Llamadarecursiva
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
187/389
7 11 15 2 8 2 3 10 7 1 413 1 5
7 11 15 2 813 1
7 11 1513
713
13
Llamadarecursiva
Caso base(umbral = 0)
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
188/389
7 11 15 2 8 2 3 10 7 1 413 1 5
7 11 15 2 813 1
7 11 1513
713
13 7
Llamadarecursiva
Caso base(umbral = 0)
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
189/389
7 11 15 2 8 2 3 10 7 1 413 1 5
7 11 15 2 813 1
7 11 1513
13 7
Llamadarecursiva
Fusin
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
190/389
7 11 15 2 8 2 3 10 7 1 413 1 5
7 11 15 2 813 1
7 11 1513
13 7
137
Llamadarecursiva
Fusin
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
191/389
7 11 15 2 8 2 3 10 7 1 413 1 5
7 11 15 2 813 1
7 11 1513
137 11 15
Llamadarecursiva
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
192/389
7 11 15 2 8 2 3 10 7 1 413 1 5
7 11 15 2 813 1
7 11 1513
137 11 15
11
Llamadarecursiva
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
193/389
7 11 15 2 8 2 3 10 7 1 413 1 5
7 11 15 2 813 1
7 11 1513
137 11 15
11 15
Llamadarecursiva
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
194/389
7 11 15 2 8 2 3 10 7 1 413 1 5
7 11 15 2 813 1
7 11 1513
137
11 15
Llamadarecursiva
Fusin
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
195/389
7 11 15 2 8 2 3 10 7 1 413 1 5
7 11 15 2 813 1
7 11 1513
137
11 15
11 15
Llamadarecursiva
Fusin
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
196/389
7 11 15 2 8 2 3 10 7 1 413 1 5
7 11 15 2 813 1
137 11 15
Llamadarecursiva
Fusin
-
7/25/2019 TGR3_Ordenacion_2015
197/389
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
198/389
7 11 15 2 8 2 3 10 7 1 413 1 5
7 11 15 2 813 1
11 13 157 2 8 1
Llamadarecursiva
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
199/389
7 11 15 2 8 2 3 10 7 1 413 1 5
7 11 15 2 813 1
11 13 157 2 8 1
2 8
Llamadarecursiva
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
200/389
7 11 15 2 8 2 3 10 7 1 413 1 5
7 11 15 2 813 1
11 13 157 2 8 1
2 8
2
Llamadarecursiva
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
201/389
7 11 15 2 8 2 3 10 7 1 413 1 5
7 11 15 2 813 1
11 13 157 2 8 1
2 8
2 8
Llamadarecursiva
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
202/389
7 11 15 2 8 2 3 10 7 1 413 1 5
7 11 15 2 813 1
11 13 157 2 8 1
2 8
Llamadarecursiva
Fusin
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
203/389
7 11 15 2 8 2 3 10 7 1 413 1 5
7 11 15 2 813 1
11 13 157 2 8 1
2 8
2 8
Llamadarecursiva
Fusin
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
204/389
7 11 15 2 8 2 3 10 7 1 413 1 5
7 11 15 2 813 1
11 13 157 2 8 1
2 8 1
Llamadarecursiva
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
205/389
7 11 15 2 8 2 3 10 7 1 413 1 5
7 11 15 2 813 1
11 13 157
2 8 1
Llamadarecursiva
Fusin
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
206/389
7 11 15 2 8 2 3 10 7 1 413 1 5
7 11 15 2 813 1
11 13 157
2 8 1
1 2 8
Llamadarecursiva
Fusin
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
207/389
7 11 15 2 8 2 3 10 7 1 413 1 5
11 13 157 1 2 8
Llamadarecursiva
Fusin
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
208/389
7 11 15 2 8 2 3 10 7 1 413 1 5
11 13 157 1 2 8
2 7 8 11 131 15
Llamadarecursiva
Fusin
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
209/389
7 11 15 2 8 2 3 10 7 1 413 1 5
2 7 8 11 131 15 2 3 10 7 1 45
Llamadarecursiva
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
210/389
7 11 15 2 8 2 3 10 7 1 413 1 5
2 7 8 11 131 15 2 3 10 7 1 45
2 3 10 7
Llamadarecursiva
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
211/389
7 11 15 2 8 2 3 10 7 1 413 1 5
2 7 8 11 131 15 2 3 10 7 1 45
2 3 10 7
2 3
Llamadarecursiva
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
212/389
7 11 15 2 8 2 3 10 7 1 413 1 5
2 7 8 11 131 15 2 3 10 7 1 45
2 3 10 7
2 3
2
Llamadarecursiva
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
213/389
7 11 15 2 8 2 3 10 7 1 413 1 5
2 7 8 11 131 15 2 3 10 7 1 45
2 3 10 7
2 3
2 3
Llamadarecursiva
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
214/389
7 11 15 2 8 2 3 10 7 1 413 1 5
2 7 8 11 131 15 2 3 10 7 1 45
2 3 10 7
2 3
Llamadarecursiva
Fusin
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
215/389
7 11 15 2 8 2 3 10 7 1 413 1 5
2 7 8 11 131 15 2 3 10 7 1 45
2 3 10 7
2 3
2 3
Llamadarecursiva
Fusin
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
216/389
7 11 15 2 8 2 3 10 7 1 413 1 5
2 7 8 11 131 15 2 3 10 7 1 45
2 3 10 7
2 3 10 7
Llamadarecursiva
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
217/389
7 11 15 2 8 2 3 10 7 1 413 1 5
2 7 8 11 131 15 2 3 10 7 1 45
2 3 10 7
2 3 10 7
10
Llamadarecursiva
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
218/389
7 11 15 2 8 2 3 10 7 1 413 1 5
2 7 8 11 131 15 2 3 10 7 1 45
2 3 10 7
2 3 10 7
10 7
Llamadarecursiva
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
219/389
7 11 15 2 8 2 3 10 7 1 413 1 5
2 7 8 11 131 15 2 3 10 7 1 45
2 3 10 7
2 3
10 7
Fusin
Llamadarecursiva
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
220/389
7 11 15 2 8 2 3 10 7 1 413 1 5
2 7 8 11 131 15 2 3 10 7 1 45
2 3 10 7
2 3
10 7
7 10
Fusin
Llamadarecursiva
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
221/389
7 11 15 2 8 2 3 10 7 1 413 1 5
2 7 8 11 131 15 2 3 10 7 1 45
2 3 7 10
Llamadarecursiva
Fusin
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
222/389
7 11 15 2 8 2 3 10 7 1 413 1 5
2 7 8 11 131 15 2 3 10 7 1 45
2 3 7 10
2 3 7 10
Llamadarecursiva
Fusin
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
223/389
7 11 15 2 8 2 3 10 7 1 413 1 5
2 7 8 11 131 15 2 3 10 7 1 45
2 3 7 10 1 45
Llamadarecursiva
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
224/389
7 11 15 2 8 2 3 10 7 1 413 1 5
2 7 8 11 131 15 2 3 10 7 1 45
2 3 7 10 1 45
1 5
Llamadarecursiva
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
225/389
7 11 15 2 8 2 3 10 7 1 413 1 5
2 7 8 11 131 15 2 3 10 7 1 45
2 3 7 10 1 45
1 5
1
Llamadarecursiva
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
226/389
7 11 15 2 8 2 3 10 7 1 413 1 5
2 7 8 11 131 15 2 3 10 7 1 45
2 3 7 10 1 45
1 5
1 5
Llamadarecursiva
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
227/389
7 11 15 2 8 2 3 10 7 1 413 1 5
2 7 8 11 131 15 2 3 10 7 1 45
2 3 7 10 1 45
1 5
Llamadarecursiva
Fusin
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
228/389
7 11 15 2 8 2 3 10 7 1 413 1 5
2 7 8 11 131 15 2 3 10 7 1 45
2 3 7 10 1 45
1 5
1 5
Fusin
Llamadarecursiva
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
229/389
7 11 15 2 8 2 3 10 7 1 413 1 5
2 7 8 11 131 15 2 3 10 7 1 45
2 3 7 10 1 45
1 5 4
Llamadarecursiva
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
230/389
7 11 15 2 8 2 3 10 7 1 413 1 5
2 7 8 11 131 15 2 3 10 7 1 45
2 3 7 10
1 5 4
Llamadarecursiva
Fusin
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
231/389
7 11 15 2 8 2 3 10 7 1 413 1 5
2 7 8 11 131 15 2 3 10 7 1 45
2 3 7 10
1 5 4
1 54
Llamadarecursiva
Fusin
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
232/389
7 11 15 2 8 2 3 10 7 1 413 1 5
2 7 8 11 131 15
2 3 7 10 1 54
Llamadarecursiva
Fusin
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
233/389
7 11 15 2 8 2 3 10 7 1 413 1 5
2 7 8 11 131 15
2 3 7 10 1 54
1 2 3 4 5 107
Llamadarecursiva
Fusin
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
234/389
2 7 8 11 131 15 1 2 3 4 5 107
Fusin
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
235/389
2 7 8 11 131 15 1 2 3 4 5 107
1 2 2 3 4 7 7 8 10 11 151 5 13
Fusin
Ordenacin por fusin
Ejercicio 2: construir el rbol recursivo que genera el algoritmo porfusin puramente recursivo (umbral = 0) para el siguiente vector de
-
7/25/2019 TGR3_Ordenacion_2015
236/389
datos.
10 3 6 7 7 1 4 9 11 515 8
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
237/389
10 3 6 7 7 1 4 9 11 515 8
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
238/389
10 3 6 7 7 1 4 9 11 515 8
10 3 6 7 715
Llamadarecursiva
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
239/389
10 3 6 7 7 1 4 9 11 515 8
10 3 6 7 715
10 315
Llamadarecursiva
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
240/389
10 3 6 7 7 1 4 9 11 515 8
10 3 6 7 715
10 315
1015
Llamadarecursiva
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
241/389
10 3 6 7 7 1 4 9 11 515 8
10 3 6 7 715
10 315
1015
15
Llamadarecursiva
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
242/389
10 3 6 7 7 1 4 9 11 515 8
10 3 6 7 715
10 315
1015
15 10
Llamadarecursiva
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
243/389
10 3 6 7 7 1 4 9 11 515 8
10 3 6 7 715
10 315
15 10
Fusin
Llamadarecursiva
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
244/389
10 3 6 7 7 1 4 9 11 515 8
10 3 6 7 715
10 315
15 10
1510
Llamadarecursiva
Fusin
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
245/389
10 3 6 7 7 1 4 9 11 515 8
10 3 6 7 715
10 315
1510 3
Llamadarecursiva
Ordenacin por fusin
Solucin:
0 3 6 98
-
7/25/2019 TGR3_Ordenacion_2015
246/389
10 3 6 7 7 1 4 9 11 515 8
10 3 6 7 715
1510 3
Llamadarecursiva
Fusin
Ordenacin por fusin
Solucin:
10 3 6 7 7 1 4 9 11 515 8
-
7/25/2019 TGR3_Ordenacion_2015
247/389
10 3 6 7 7 1 4 9 11 515 8
10 3 6 7 715
1510 3
10 153
Llamadarecursiva
Fusin
Ordenacin por fusin
Solucin:
10 3 6 7 7 1 4 9 11 515 8
-
7/25/2019 TGR3_Ordenacion_2015
248/389
10 3 6 7 7 1 4 9 11 515 8
10 3 6 7 715
10 153 6 7 7
Llamadarecursiva
Ordenacin por fusin
Solucin:
10 3 6 7 7 1 4 9 11 515 8
-
7/25/2019 TGR3_Ordenacion_2015
249/389
10 3 6 7 7 1 4 9 11 515 8
10 3 6 7 715
10 153 6 7 7
6 7
Llamadarecursiva
Ordenacin por fusin
Solucin:
10 3 6 7 7 1 4 9 11 515 8
-
7/25/2019 TGR3_Ordenacion_2015
250/389
10 3 6 7 7 1 4 9 11 515 8
10 3 6 7 715
10 153 6 7 7
6 7
6
Llamadarecursiva
Ordenacin por fusin
Solucin:
10 3 6 7 7 1 4 9 11 515 8
-
7/25/2019 TGR3_Ordenacion_2015
251/389
10 3 6 7 7 1 4 9 11 515 8
10 3 6 7 715
6 7 7
6 7
6 7
10 153
Llamadarecursiva
Ordenacin por fusin
Solucin:
10 3 6 7 7 1 4 9 11 515 8
-
7/25/2019 TGR3_Ordenacion_2015
252/389
10 3 6 7 7 1 4 9 11 515 8
10 3 6 7 715
10 153 6 7 7
6 7
Fusin
Llamadarecursiva
-
7/25/2019 TGR3_Ordenacion_2015
253/389
Ordenacin por fusin
Solucin:
10 3 6 7 7 1 4 9 11 515 8
-
7/25/2019 TGR3_Ordenacion_2015
254/389
10 3 6 7 7 1 4 9 11 515 8
10 3 6 7 715
10 153 6 7 7
6 7 7
Llamadarecursiva
Ordenacin por fusin
Solucin:
10 3 6 7 7 1 4 9 11 515 8
-
7/25/2019 TGR3_Ordenacion_2015
255/389
10 3 6 7 7 1 4 9 11 515 8
10 3 6 7 715
10 153
6 7 7
Llamadarecursiva
Fusin
Ordenacin por fusin
Solucin:
10 3 6 7 7 1 4 9 11 515 8
-
7/25/2019 TGR3_Ordenacion_2015
256/389
10 3 6 7 7 1 4 9 11 515 8
10 3 6 7 715
10 153
6 7 7
6 7 7
Llamadarecursiva
Fusin
Ordenacin por fusin
Solucin:
10 3 6 7 7 1 4 9 11 515 8
-
7/25/2019 TGR3_Ordenacion_2015
257/389
10 3 6 7 7 1 4 9 11 515 8
10 153 6 7 7
Llamadarecursiva
Fusin
Ordenacin por fusin
Solucin:
10 3 6 7 7 1 4 9 11 515 8
-
7/25/2019 TGR3_Ordenacion_2015
258/389
10 3 6 7 7 1 4 9 11 515 8
10 153 6 7 7
6 7 7 10 153
Llamadarecursiva
Fusin
Ordenacin por fusin
Solucin:
10 3 6 7 7 1 4 9 11 515 8
-
7/25/2019 TGR3_Ordenacion_2015
259/389
10 3 6 7 7 1 4 9 11 515 8
1 4 9 11 58
Llamadarecursiva
6 7 7 10 153
Ordenacin por fusin
Solucin:
10 3 6 7 7 1 4 9 11 515 8
-
7/25/2019 TGR3_Ordenacion_2015
260/389
10 3 6 7 7 1 4 9 11 515 8
1 4 9 11 58
1 48
Llamadarecursiva
6 7 7 10 153
Ordenacin por fusin
Solucin:
10 3 6 7 7 1 4 9 11 515 8
-
7/25/2019 TGR3_Ordenacion_2015
261/389
10 3 6 7 7 1 4 9 11 515 8
1 4 9 11 58
1 48
18
Llamadarecursiva
6 7 7 10 153
Ordenacin por fusin
Solucin:
10 3 6 7 7 1 4 9 11 515 8
-
7/25/2019 TGR3_Ordenacion_2015
262/389
10 3 6 7 7 1 4 9 11 515 8
1 4 9 11 58
1 48
18
8
Llamadarecursiva
6 7 7 10 153
Ordenacin por fusin
Solucin:
10 3 6 7 7 1 4 9 11 515 8
-
7/25/2019 TGR3_Ordenacion_2015
263/389
10 3 6 7 7 1 4 9 11 515 8
1 4 9 11 58
1 48
18
8 1
Llamadarecursiva
6 7 7 10 153
Ordenacin por fusin
Solucin:
10 3 6 7 7 1 4 9 11 515 8l d
-
7/25/2019 TGR3_Ordenacion_2015
264/389
10 3 6 7 7 1 4 9 11 515 8
1 4 9 11 58
1 48
8 1
Llamadarecursiva
Fusin
6 7 7 10 153
Ordenacin por fusin
Solucin:
10 3 6 7 7 1 4 9 11 515 8Ll d
-
7/25/2019 TGR3_Ordenacion_2015
265/389
10 3 6 7 7 1 4 9 11 515 8
1 4 9 11 58
1 48
8 1
81
Llamadarecursiva
Fusin
6 7 7 10 153
Ordenacin por fusin
Solucin:
10 3 6 7 7 1 4 9 11 515 8Ll d
-
7/25/2019 TGR3_Ordenacion_2015
266/389
10 3 6 7 7 1 4 9 11 515 8
1 4 9 11 58
1 48
81 4
Llamadarecursiva
6 7 7 10 153
Ordenacin por fusin
Solucin:
10 3 6 7 7 1 4 9 11 515 8Ll d
-
7/25/2019 TGR3_Ordenacion_2015
267/389
0 3 6 7 7 4 9 55 8
1 4 9 11 58
81 4
Llamadarecursiva
Fusin
6 7 7 10 153
Ordenacin por fusin
Solucin:
10 3 6 7 7 1 4 9 11 515 8Llamada
-
7/25/2019 TGR3_Ordenacion_2015
268/389
1 4 9 11 58
81 4
4 81
Llamadarecursiva
Fusin
6 7 7 10 153
Ordenacin por fusin
Solucin:
10 3 6 7 7 1 4 9 11 515 8Llamada
-
7/25/2019 TGR3_Ordenacion_2015
269/389
1 4 9 11 58
4 81 9 11 5
Llamadarecursiva
6 7 7 10 153
Ordenacin por fusin
Solucin:
10 3 6 7 7 1 4 9 11 515 8Llamada
-
7/25/2019 TGR3_Ordenacion_2015
270/389
1 4 9 11 58
4 81 9 11 5
9 11
Llamadarecursiva
6 7 7 10 153
Ordenacin por fusin
Solucin:
10 3 6 7 7 1 4 9 11 515 8Llamada
-
7/25/2019 TGR3_Ordenacion_2015
271/389
1 4 9 11 58
4 81 9 11 5
9 11
9
Llamadarecursiva
6 7 7 10 153
Ordenacin por fusin
Solucin:
10 3 6 7 7 1 4 9 11 515 8Llamada
-
7/25/2019 TGR3_Ordenacion_2015
272/389
1 4 9 11 58
4 81 9 11 5
9 11
9 11
Llamadarecursiva
6 7 7 10 153
Ordenacin por fusin
Solucin:
10 3 6 7 7 1 4 9 11 515 8Llamada
-
7/25/2019 TGR3_Ordenacion_2015
273/389
1 4 9 11 58
4 81 9 11 5
9 11
Llamadarecursiva
Fusin
6 7 7 10 153
Ordenacin por fusin
Solucin:
10 3 6 7 7 1 4 9 11 515 8Llamada
-
7/25/2019 TGR3_Ordenacion_2015
274/389
1 4 9 11 58
4 81 9 11 5
9 11
9 11
Llamadarecursiva
Fusin
6 7 7 10 153
Ordenacin por fusin
Solucin:
10 3 6 7 7 1 4 9 11 515 8Llamada
-
7/25/2019 TGR3_Ordenacion_2015
275/389
1 4 9 11 58
4 81 9 11 5
9 11 5
Llamadarecursiva
6 7 7 10 153
Ordenacin por fusin
Solucin:
10 3 6 7 7 1 4 9 11 515 8Llamada
-
7/25/2019 TGR3_Ordenacion_2015
276/389
1 4 9 11 58
4 81
9 11 5
Llamadarecursiva
Fusin
6 7 7 10 153
Ordenacin por fusin
Solucin:
10 3 6 7 7 1 4 9 11 515 8Llamada
-
7/25/2019 TGR3_Ordenacion_2015
277/389
1 4 9 11 58
4 81
9 11 5
5 9 11
Llamadarecursiva
Fusin
6 7 7 10 153
Ordenacin por fusin
Solucin:
10 3 6 7 7 1 4 9 11 515 8Llamada
-
7/25/2019 TGR3_Ordenacion_2015
278/389
4 81 5 9 11
recursiva
Fusin
6 7 7 10 153
Ordenacin por fusin
Solucin:
10 3 6 7 7 1 4 9 11 515 8Llamada
-
7/25/2019 TGR3_Ordenacion_2015
279/389
4 81 5 9 11
4 5 8 9 111
recursiva
Fusin
6 7 7 10 153
Ordenacin por fusin
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
280/389
4 5 8 9 111
Fusin
6 7 7 10 153
Ordenacin por fusin
Solucin:
3 4 5 6 7 8 9 10 11 151 7
-
7/25/2019 TGR3_Ordenacion_2015
281/389
4 5 8 9 111
Fusin
6 7 7 10 153
Ordenacin rpida: ejemplo balanceado
Ejercicio 1: construir el rbol recursivo que genera el algoritmo deordenacin rpida (quicksort), con mediana de 3 en la seleccin delpivote y umbral=3, para el siguiente vector de datos.
-
7/25/2019 TGR3_Ordenacion_2015
282/389
14 6 1 7 9 2 11 13 10 3 128 4 5
Ordenacin rpida: ejemplo balanceado
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
283/389
14 6 1 7 9 2 11 13 10 3 128 4 5
Ordenacin rpida: ejemplo balanceado
Solucin:
Mediana de 3
-
7/25/2019 TGR3_Ordenacion_2015
284/389
14 6 1 7 9 2 11 13 10 3 128 4 5
Ordenacin rpida: ejemplo balanceado
Solucin:
Mediana de 3
-
7/25/2019 TGR3_Ordenacion_2015
285/389
14 6 1 7 9 2 11 13 10 3 124 8 5
Ordenacin rpida: ejemplo balanceado
Solucin:
Mediana de 3
-
7/25/2019 TGR3_Ordenacion_2015
286/389
14 6 1 7 9 2 11 13 10 3 124 8 5
Pivote
Ordenacin rpida: ejemplo balanceado
Solucin:
Intercambio con el pivote
-
7/25/2019 TGR3_Ordenacion_2015
287/389
14 6 1 7 9 2 11 13 10 3 124 5 8
Ordenacin rpida: ejemplo balanceado
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
288/389
14 6 1 7 9 2 11 13 10 3 124 5 8
Recorrido doblecomparando con el pivote
mk
Ordenacin rpida: ejemplo balanceado
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
289/389
14 6 1 7 9 2 11 13 10 3 124 5 8
mk
Cuando vector[k] >= pivote sedetiene el recorrido
Ordenacin rpida: ejemplo balanceado
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
290/389
14 6 1 7 9 2 11 13 10 3 124 5 8
mk
Cuando vector[m]
-
7/25/2019 TGR3_Ordenacion_2015
291/389
14 6 1 7 9 2 11 13 10 3 124 5 8
mk
Ordenacin rpida: ejemplo balanceado
Solucin:
Intercambio de elementos
-
7/25/2019 TGR3_Ordenacion_2015
292/389
3 6 1 7 9 2 11 13 10 14 124 5 8
mk
Ordenacin rpida: ejemplo balanceado
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
293/389
3 6 1 7 9 2 11 13 10 14 124 5 8
mk
Ordenacin rpida: ejemplo balanceado
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
294/389
3 6 1 7 9 2 11 13 10 14 124 5 8
mk
Ordenacin rpida: ejemplo balanceado
Solucin:
-
7/25/2019 TGR3_Ordenacion_2015
295/389
3 6 1 7 9 2 11 13 10 14 124 5 8
mk
Ordenacin rpida: ejemplo balanceado
Solucin:
3 6 1 7 9 2 11 13 10 14 124 5 8
-
7/25/2019 TGR3_Ordenacion_2015
296/389
3 6 1 7 9 2 11 13 10 14 124 5 8
mk
vector[k] >= pivote
Ordenacin rpida: ejemplo balanceado
Solucin:
3 6 1 7 9 2 11 13 10 14 124 5 8
-
7/25/2019 TGR3_Ordenacion_2015
297/389
3 6 1 7 9 2 11 13 10 14 124 5 8
mk
Ordenacin rpida: ejemplo balanceado
Solucin:
3 6 1 7 9 2 11 13 10 14 124 5 8
-
7/25/2019 TGR3_Ordenacion_2015
298/389
3 6 1 7 9 2 11 13 10 14 124 5 8
mk
Ordenacin rpida: ejemplo balanceado
Solucin:
3 6 1 7 9 2 11 13 10 14 124 5 8
-
7/25/2019 TGR3_Ordenacion_2015
299/389
3 6 1 7 9 2 11 13 10 14 124 5 8
mk
Ordenacin rpida: ejemplo balanceado
Solucin:
3 6 1 7 9 2 11 13 10 14 124 5 8
-
7/25/2019 TGR3_Ordenacion_2015
300/389
3 6 1 7 9 2 11 13 10 14 124 5 8
mk
vector[m]
-
7/25/2019 TGR3_Ordenacion_2015
301/389
3 6 1 7 9 2 11 13 10 14 124 5 8
mk
Ordenacin rpida: ejemplo balanceado
Solucin:
3 6 1 7 2 9 11 13 10 14 124 5 8
Intercambio de elementos
-
7/25/2019 TGR3_Ordenacion_2015
302/389
3 6 1 7 2 9 11 13 10 14 124 5 8
mk
Ordenacin rpida: ejemplo balanceado
Solucin:
3 6 1 7 2 9 11 13 10 14 124 5 8
-
7/25/2019 TGR3_Ordenacion_2015
303/389
3 6 1 7 2 9 11 13 10 14 124 5 8
mk
Ordenacin rpida: ejemplo balanceado
Solucin:
3 6 1 7 2 9 11 13 10 14 124 5 8
-
7/25/2019 TGR3_Ordenacion_2015
304/389
3 6 1 7 2 9 11 13 10 14 124 5 8
mk
vector[k] >= pivote
Ordenacin rpida: ejemplo balanceado
Solucin:
3 6 1 7 2 9 11 13 10 14 124 5 8
-
7/25/2019 TGR3_Ordenacion_2015
305/389
3 6 1 7 2 9 11 13 10 14 124 5 8
km
vector[m]
-
7/25/2019 TGR3_Ordenacion_2015
306/389
3 6 1 7 2 9 11 13 10 14 124 5 8
km
Ordenacin rpida: ejemplo balanceado
Solucin:
3 6 1 7 2 5 11 13 10 14 124 9 8
Intercambio de elementos
-
7/25/2019 TGR3_Ordenacion_2015
307/389
3 6 1 7 2 5 11 13 10 14 124 9 8
km
Ordenacin rpida: ejemplo balanceado
Solucin:
3 6 1 7 2 5 11 13 10 14 124 9 8
-
7/25/2019 TGR3_Ordenacion_2015
308/389
3 6 1 7 2 5 11 13 10 14 124 9 8
Si k>mFinaliza el recorrido
km
Ordenacin rpida: ejemplo balanceado
Solucin:
3 6 1 7 2 5 11 13 10 14 124 9 8
Intercambio de elementos
-
7/25/2019 TGR3_Ordenacion_2015
309/389
3 6 1 7 2 5 11 13 10 14 124 9 8
km
Ordenacin rpida: ejemplo balanceado
Solucin:
3 6 1 7 2 9 11 13 10 14 124 5 8
Intercambio de elementos
-
7/25/2019 TGR3_Ordenacion_2015
310/389
3 6 1 7 2 9 11 13 10 14 124 5 8
km
Ordenacin rpida: ejemplo balanceado
Solucin:
3 6 1 7 2 9 11 13 10 14 124 5 8
Se coloca el pivote en la posicinque le corresponde (k)
-
7/25/2019 TGR3_Ordenacion_2015
311/389
3 6 1 7 2 9 11 13 10 14 124 5 8
km
Ordenacin rpida: ejemplo balanceado
Solucin:
3 6 1 7 2 8 11 13 10 14 124 5 9
Se coloca el pivote en la posicinque le corresponde (k)
-
7/25/2019 TGR3_Ordenacion_2015
312/389
km
Ordenacin rpida: ejemplo balanceado
Solucin:
3 6 1 7 2 8 11 13 10 14 124 5 9
-
7/25/2019 TGR3_Ordenacion_2015
313/389
Ordenacin rpida: ejemplo balanceado
Solucin:
3 6 1 7 2 8 11 13 10 14 124 5 9
-
7/25/2019 TGR3_Ordenacion_2015
314/389
Llamadarecursiva
3 6 1 7 24 5
Ordenacin rpida: ejemplo balanceado
Solucin:
3 6 1 7 2 8 11 13 10 14 124 5 9
-
7/25/2019 TGR3_Ordenacion_2015
315/389
Llamadarecursiva
3 6 1 7 24 5
Mediana de 3
Ordenacin rpida: ejemplo balanceado
Solucin:
3 6 1 7 2 8 11 13 10 14 124 5 9
-
7/25/2019 TGR3_Ordenacion_2015
316/389
Llamadarecursiva
3 6 4 7 21 5
Mediana de 3
Ordenacin rpida: ejemplo balanceado
Solucin:
3 6 1 7 2 8 11 13 10 14 124 5 9
-
7/25/2019 TGR3_Ordenacion_2015
317/389
Llamadarecursiva
3 6 4 7 21 5
Mediana de 3
Ordenacin rpida: ejemplo balanceado
Solucin:
3 6 1 7 2 8 11 13 10 14 124 5 9
-
7/25/2019 TGR3_Ordenacion_2015
318/389
Llamadarecursiva
3 6 2 7 41 5
Mediana de 3
Pivote
Ordenacin rpida: ejemplo balanceado
Solucin:
3 6 1 7 2 8 11 13 10 14 124 5 9
-
7/25/2019 TGR3_Ordenacion_2015
319/389
Llamadarecursiva
3 6 2 7 41 5
Pivote
mk
Recorrido doblecomparando con el pivote
Ordenacin rpida: ejemplo balanceado
Solucin:
3 6 1 7 2 8 11 13 10 14 124 5 9
-
7/25/2019 TGR3_Ordenacion_2015
320/389
Llamadarecursiva
3 2 4 7 61 5
Ordenacin rpida: ejemplo balanceado
Solucin:
3 6 1 7 2 8 11 13 10 14 124 5 9
-
7/25/2019 TGR3_Ordenacion_2015
321/389
Llamadarecursiva
3 2 4 7 61 5
3 21
Caso base(umbral = 3)
Ordenacin rpida: ejemplo balanceado
Solucin:
3 6 1 7 2 8 11 13 10 14 124 5 9
-
7/25/2019 TGR3_Ordenacion_2015
322/389
Llamadarecursiva
3 2 4 7 61 5
3 21 6 57
Caso base(umbral = 3)
Ordenacin rpida: ejemplo balanceado
Solucin:
3 6 1 7 2 8 11 13 10 14 124 5 9
-
7/25/2019 TGR3_Ordenacion_2015
323/389
Llamadarecursiva
3 2 4 7 61 5
Ordenacin rpida: ejemplo balanceado
Solucin:
3 6 1 7 2 8 11 13 10 14 124 5 9
-
7/25/2019 TGR3_Ordenacion_2015
324/389
Llamadarecursiva
3 2 4 7 61 5 11 13 10 14 129
Ordenacin rpida: ejemplo balanceado
Solucin:
3 6 1 7 2 8 11 13 10 14 124 5 9
l
-
7/25/2019 TGR3_Ordenacion_2015
325/389
Llamadarecursiva
3 2 4 7 61 5 11 13 10 14 129
Mediana de 3
Ordenacin rpida: ejemplo balanceado
Solucin:
3 6 1 7 2 8 11 13 10 14 124 5 9
Ll d
-
7/25/2019 TGR3_Ordenacion_2015
326/389
Llamadarecursiva
3 2 4 7 61 5 10 13 11 14 129
Mediana de 3
Ordenacin rpida: ejemplo balanceado
Solucin:
3 6 1 7 2 8 11 13 10 14 124 5 9
Ll d
-
7/25/2019 TGR3_Ordenacion_2015
327/389
Llamadarecursiva
3 2 4 7 61 5 10 13 11 14 129
Mediana de 3
Ordenacin rpida: ejemplo balanceado
Solucin:
3 6 1 7 2 8 11 13 10 14 124 5 9
Ll d
-
7/25/2019 TGR3_Ordenacion_2015
328/389
Llamadarecursiva
3 2 4 7 61 5 10 13 9 14 1211
Mediana de 3
Pivote
Ordenacin rpida: ejemplo balanceado
Solucin:
3 6 1 7 2 8 11 13 10 14 124 5 9
Ll d
-
7/25/2019 TGR3_Ordenacion_2015
329/389
Llamadarecursiva
3 2 4 7 61 5 10 13 9 14 1211
Pivote
mk
Recorrido doblecomparando con el pivote
Ordenacin rpida: ejemplo balanceado
Solucin:
3 6 1 7 2 8 11 13 10 14 124 5 9
Llamada
-
7/25/2019 TGR3_Ordenacion_2015
330/389
Llamadarecursiva
3 2 4 7 61 5 10 9 11 14 1213
Ordenacin rpida: ejemplo balanceado
Solucin:
3 6 1 7 2 8 11 13 10 14 124 5 9
Llamada
-
7/25/2019 TGR3_Ordenacion_2015
331/389
Llamadarecursiva
3 2 4 7 61 5 10 9 11 14 1213
910
Caso base(umbral = 3)
Ordenacin rpida: ejemplo balanceado
Solucin:
3 6 1 7 2 8 11 13 10 14 124 5 9
Llamada
-
7/25/2019 TGR3_Ordenacion_2015
332/389
Llamadarecursiva
3 2 4 7 61 5 10 9 11 14 1213
13 1214
Caso base(umbral = 3)
910
Ordenacin rpida: ejemplo balanceado
Solucin:
3 6 1 7 2 8 11 13 10 14 124 5 9
Llamada
-
7/25/2019 TGR3_Ordenacion_2015
333/389
Llamadarecursiva
3 2 4 7 61 5 10 9 11 14 1213
Ordenacin rpida: ejemplo balanceado
Solucin:
3 2 4 7 6 8 10 9 11 14 121 5 13
Llamada
-
7/25/2019 TGR3_Ordenacion_2015
334/389
Llamadarecursiva
3 2 4 7 61 5 10 9 11 14 1213
Ordenacin rpida: ejemplo balanceado
Solucin:
3 2 4 7 6 8 10 9 11 14 121 5 13
-
7/25/2019 TGR3_Ordenacion_2015
335/389
Ordenacin por Insercin
Ordenacin rpida: ejemplo balanceado
Solucin:
2 3 4 5 6 8 9 10 11 12 141 7 13
-
7/25/2019 TGR3_Ordenacion_2015
336/389
Ordenacin por Insercin
Ordenacin rpida: ejemplo desbalanceado
Ejercicio 2: construir el rbol recursivo que genera el algoritmo deordenacin rpida (quicksort), con mediana de 3 en la seleccin delpivote y umbral=3, para el siguiente vector de datos.
7 4 10 6 13 3 12 11 8 14 25 1 9
-
7/25/2019 TGR3_Ordenacion_2015
337/389
7 4 10 6 13 3 12 11 8 14 25 1 9
Ordenacin rpida: ejemplo desbalanceado
Solucin:
7 4 10 6 13 3 12 11 8 14 25 1 9
-
7/25/2019 TGR3_Ordenacion_2015
338/389
Ordenacin rpida: ejemplo desbalanceado
Solucin:
7 4 10 6 13 3 12 11 8 14 25 1 9
Mediana de 3
-
7/25/2019 TGR3_Ordenacion_2015
339/389
Ordenacin rpida: ejemplo desbalanceado
Solucin:
7 4 10 6 13 3 12 11 8 14 51 2 9
Mediana de 3
-
7/25/2019 TGR3_Ordenacion_2015
340/389
Ordenacin rpida: ejemplo desbalanceado
Solucin:
7 4 10 6 13 3 12 11 8 14 51 2 9
Mediana de 3
Pivote
-
7/25/2019 TGR3_Ordenacion_2015
341/389
Ordenacin rpida: ejemplo desbalanceado
Solucin:
7 4 10 6 13 3 12 11 8 14 51 2 9
Pivote
Intercambio con el pivote
-
7/25/2019 TGR3_Ordenacion_2015
342/389
Ordenacin rpida: ejemplo desbalanceado
Solucin:
7 4 10 6 13 3 12 11 8 14 51 9 2
Pivote
Intercambio con el pivote
-
7/25/2019 TGR3_Ordenacion_2015
343/389
Ordenacin rpida: ejemplo desbalanceado
Solucin:
7 4 10 6 13 3 12 11 8 14 51 9 2
Recorrido doble mk
-
7/25/2019 TGR3_Ordenacion_2015
344/389
comparando con el pivotemk
Ordenacin rpida: ejemplo desbalanceado
Solucin:
2 4 10 6 13 3 12 11 8 14 51 9 7
-
7/25/2019 TGR3_Ordenacion_2015
345/389
Ordenacin rpida: ejemplo desbalanceado
Solucin:
2 4 10 6 13 3 12 11 8 14 51 9 7Llamadarecursiva
-
7/25/2019 TGR3_Ordenacion_2015
346/389
1
Caso base(umbral = 3)
Ordenacin rpida: ejemplo desbalanceado
Solucin:
2 4 10 6 13 3 12 11 8 14 51 9 7Llamadarecursiva
-
7/25/2019 TGR3_Ordenacion_2015
347/389
1 4 10 6 13 3 12 11 8 14 59 7
Ordenacin rpida: ejemplo desbalanceado
Solucin:
2 4 10 6 13 3 12 11 8 14 51 9 7Llamadarecursiva
-
7/25/2019 TGR3_Ordenacion_2015
348/389
1 4 10 6 13 3 12 11 8 14 59 7
Mediana de 3
Ordenacin rpida: ejemplo desbalanceado
Solucin:
2 4 10 6 13 3 12 11 8 14 51 9 7Llamadarecursiva
-
7/25/2019 TGR3_Ordenacion_2015
349/389
1 3 10 6 13 4 12 11 8 14 59 7
Mediana de 3
Ordenacin rpida: ejemplo desbalanceado
Solucin:
2 4 10 6 13 3 12 11 8 14 51 9 7Llamadarecursiva
Pivote
-
7/25/2019 TGR3_Ordenacion_2015
350/389
1 3 10 6 13 4 12 11 8 14 59 7
Mediana de 3
Ordenacin rpida: ejemplo desbalanceado
Solucin:
2 4 10 6 13 3 12 11 8 14 51 9 7Llamadarecursiva
Pivote
-
7/25/2019 TGR3_Ordenacion_2015
351/389
1 3 10 6 13 7 12 11 8 14 59 4
Mediana de 3
Ordenacin rpida: ejemplo desbalanceado
Solucin:
2 4 10 6 13 3 12 11 8 14 51 9 7Llamadarecursiva
Pivote
-
7/25/2019 TGR3_Ordenacion_2015
352/389
1 3 10 6 13 7 12 11 8 14 59 4
mk
Recorrido doblecomparando con el pivote
Ordenacin rpida: ejemplo desbalanceado
Solucin:
2 4 10 6 13 3 12 11 8 14 51 9 7Llamadarecursiva
-
7/25/2019 TGR3_Ordenacion_2015
353/389
1 3 4 6 13 7 12 11 8 14 59 10
Ordenacin rpida: ejemplo desbalanceado
Solucin:
2 4 10 6 13 3 12 11 8 14 51 9 7Llamadarecursiva
-
7/25/2019 TGR3_Ordenacion_2015
354/389
1 3 4 6 13 7 12 11 8 14 59 10
3
Caso base(umbral = 3)
-
7/25/2019 TGR3_Ordenacion_2015
355/389
Ordenacin rpida: ejemplo desbalanceado
Solucin:
2 4 10 6 13 3 12 11 8 14 51 9 7Llamadarecursiva
1 3 4 6 13 7 12 11 8 14 59 10
-
7/25/2019 TGR3_Ordenacion_2015
356/389
1 3 4 6 13 7 12 11 8 14 59 10
3 6 13 7 12 11 8 14 59 10
Mediana de 3
Ordenacin rpida: ejemplo desbalanceado
Solucin:
2 4 10 6 13 3 12 11 8 14 51 9 7Llamadarecursiva
1 3 4 6 13 7 12 11 8 14 59 10
-
7/25/2019 TGR3_Ordenacion_2015
357/389
1 3 4 6 13 7 12 11 8 14 59 10
3 5 13 7 6 11 8 14 129 10