Actividad de Aprendizaje 07 Metodos de Ordenamiento Recursivos - Fernando Cesar Sandoval Padilla

Vista previa del material en texto

UNIVERSIDAD DE GUADALAJARA 
Centro Universitario de Ciencias Exactas e Ingenierías 
 
Estructura de datos I 
Actividad de Aprendizaje 07. Métodos de Ordenamiento Recursivos 
 
 
 
 
 
 
Alumno: Sandoval Padilla Fernando Cesar 
Docente: Gutiérrez Hernández Alfredo 
Código: 215685409 
Sección: D12 
 
 
 
 
 
 
 
 
 05 de Octubre de 2019 
Resumen personal: 
Para la elaboración de esta actividad fue necesaria la implementación de los 
diversos métodos de ordenamiento vistos en clase, por lo que se tomó en cuenta 
los apuntes de la clase para realizar esta actividad, cabe destacar que la ejecución 
del programa se demoró demasiado debido al tamaño del arreglo y la potencia del 
ordenador en que se ejecutó el programa, además de que para poder siempre 
ordenar el mismo número de elementos aleatorios del arreglo, fue necesario realizar 
una copia de todo el arreglo de cien mil elementos para que a la hora de intentar 
ordenar los elementos con otro método no se le facilite al ya estar ordenados. 
Código fuente: 
main.cpp 
1 #include <iostream> 
2 #include <time.h> 
3 #include <stdlib.h> 
4 #include "RandomNumbers.h" 
5 #include "Methods.h" 
6 using namespace std; 
7 
8 int main() 
9 { 
10 float first, last, result; 
11 Methods myMethods; 
12 Methods myMethods2; 
13 RandomNumbers myRandom; 
14 
15 long int data; 
16 
17 srand(time(NULL)); 
18 
19 for( int i(0) ; i < 100000 ; i++ ){ 
20 data = (rand() % 1000) * (rand() % 1000); 
21 myRandom.setRandom(data); 
22 myMethods.setNumber(myRandom); 
23 } 
24 
25 myMethods2 = myMethods; 
26 
27 cout << "Metodo[Burbuja] -Tiempo: "; 
28 first = clock(); 
29 myMethods.bubbleSort(); 
30 last = clock(); 
31 result = (last-first) / 1000 ; 
32 cout << result << " Segundos" << endl << endl; 
33 
34 myMethods = myMethods2; 
35 
36 cout << "Metodo[Shell] -Tiempo: "; 
37 first = clock(); 
38 myMethods.shellSort(); 
39 last = clock(); 
40 result = (last-first) / 1000 ; 
41 cout << result << " Segundos" << endl << endl; 
42 
43 myMethods = myMethods2; 
44 
45 cout << "Metodo[Insercion] -Tiempo: "; 
46 first = clock(); 
47 myMethods.insertSort(); 
48 last = clock(); 
49 result = (last-first) / 1000 ; 
50 cout << result << " Segundos" << endl << endl; 
51 
52 myMethods = myMethods2; 
53 
54 cout << "Metodo[Seleccion] -Tiempo: "; 
55 first = clock(); 
56 myMethods.selectionSort(); 
57 last = clock(); 
58 result = (last-first) / 1000 ; 
59 cout << result << " Segundos" << endl << endl; 
60 
61 myMethods = myMethods2; 
62 
63 cout << "Metodo[Mezcla] -Tiempo: "; 
64 first = clock(); 
65 myMethods.mergeSort(); 
66 last = clock(); 
67 result = (last-first) / 1000 ; 
68 cout << result << " Segundos" << endl << endl; 
69 
70 myMethods = myMethods2; 
71 
72 cout << "Metodo[QuickSort] -Tiempo: "; 
73 first = clock(); 
74 myMethods.quickSort(); 
75 last = clock(); 
76 result = (last-first) / 1000 ; 
77 cout << result << " Segundos" << endl << endl; 
78 
79 return 0; 
80 } 
Methods.h 
1 #ifndef METHODS_H 
2 #define METHODS_H 
3 #include "RandomNumbers.h" 
4 
5 class Methods { 
6 private: 
7 RandomNumbers AllMethods[100000]; 
8 RandomNumbers temp[100000]; 
9 void copyAll(const Methods&); 
10 int last; 
11 void mergeSort(const int&,const int&); 
12 void quickSort(const int&,const int&); 
13 public: 
14 Methods(); 
15 bool isFull(); 
16 void setNumber(const RandomNumbers&); 
17 long int getNumber(const int&); 
18 void swapAllMethods(RandomNumbers&,RandomNumbers&); 
19 
20 int getLastPos(); 
21 void bubbleSort(); 
22 void shellSort(); 
23 void insertSort(); 
24 void selectionSort(); 
25 void mergeSort(); 
26 void quickSort(); 
27 Methods& operator = (const Methods&); 
28 }; 
29 #endif // METHODS_H 
Methods.cpp 
1 #include "Methods.h" 
2 #include <iostream> 
3 
4 void Methods::copyAll(const Methods& N){ 
5 int i=0; 
6 
7 while ( i <= N.last ){ 
8 this->AllMethods[i] = N.AllMethods[i]; 
9 i++; 
10 } 
11 this->last = N.last; 
12 } 
13 
14 Methods::Methods() : last(-1) {} 
15 
16 bool Methods::isFull() { 
17 return last == -1; 
18 } 
19 
20 void Methods::setNumber(const RandomNumbers& n) { 
21 AllMethods[++last] = n; 
22 } 
23 
24 long int Methods::getNumber(const int& pos) { 
25 return AllMethods[pos].getRandom(); 
26 } 
27 
28 void Methods::swapAllMethods(RandomNumbers& a,RandomNumbers& b) { 
29 RandomNumbers aux; 
30 aux = a; 
31 a = b; 
32 b = aux; 
33 } 
34 int Methods::getLastPos() { 
35 return last; 
36 } 
37 ///Metodo Burbuja 
38 void Methods::bubbleSort() { 
39 int i(last), j; 
40 bool flag; 
41 
42 do { 
43 flag = false; 
44 j = 0; 
45 while(j < i) { 
46 if(AllMethods[j].getRandom() > AllMethods[j+1].getRandom()) { 
47 swapAllMethods(AllMethods[j],AllMethods[j+1]); 
48 flag = true; 
49 } 
50 j++; 
51 } 
52 i--; 
53 } 
54 while(flag); 
55 } 
56 ///Metodo Shell 
57 void Methods::shellSort() { 
58 float fact(3.0/4.0); 
59 int dif( (last + 1 ) * fact), lim, i; 
60 
61 while(dif>0) { 
62 lim = last - dif; 
63 
64 i=0; 
65 while( i <= lim ) { 
66 if( AllMethods[i].getRandom() > AllMethods[i+dif].getRandom()) { 
67 swapAllMethods(AllMethods[i],AllMethods[i+dif]); 
68 } 
69 
70 i++; 
71 } 
72 
73 dif*=fact; 
74 } 
75 } 
76 ///Metodo insercion 
77 void Methods::insertSort() { 
78 int i(1), j; 
79 RandomNumbers aux; 
80 
81 while(i <= last) { 
82 aux=AllMethods[i]; 
83 j=i; 
84 while( j > 0 and aux.getRandom() < AllMethods[j-1].getRandom() ) { 
85 AllMethods[j] = AllMethods[j-1]; 
86 j--; 
87 } 
88 if(i!=j) 
89 AllMethods[j]= aux; 
90 i++; 
91 } 
92 } 
93 ///Metodo seleccion 
94 void Methods::selectionSort() { 
95 int i(0), j, m; 
96 while( i < last ) { 
97 m = i; 
98 j=i+1; 
99 while(j<last) { 
100 if(AllMethods[j].getRandom() < AllMethods[m].getRandom() ) 
101 m = j; 
102 j++; 
103 } 
104 if(m!=i) 
105 swapAllMethods(AllMethods[i],AllMethods[m]); 
106 i++; 
107 } 
108 } 
109 ///Metodo Mezcla 
110 void Methods::mergeSort() { 
111 mergeSort(0,getLastPos()); 
112 } 
113 
114 void Methods::mergeSort(const int& leftEdge, const int& rightEdge) { 
115 
116 if( leftEdge >= rightEdge ) { 
117 return; 
118 } 
119 
120 int m((leftEdge + rightEdge)/2); 
121 
122 mergeSort(leftEdge,m); 
123 mergeSort( m + 1, rightEdge); 
124 
125 for( int z(leftEdge) ; z <= rightEdge ; z++ ) { 
126 temp[z] = AllMethods[z]; 
127 } 
128 
129 int i(leftEdge), j( m + 1 ), x(leftEdge); 
130 
131 while( i <= m and j <= rightEdge) { 
132 while( i <= m and temp[i].getRandom() <= temp[j].getRandom() ) { 
133 AllMethods[x++] = temp[i++]; 
134 } 
135 if( i <= m) { 
136 while( j <= rightEdge and temp[j].getRandom() <= temp[i].getRandom() ) { 
137 AllMethods[x++] = temp[j++]; 
138 } 
139 } 
140 } 
141 while ( i <= m ) { 
142 AllMethods[x++] = temp[i++]; 
143 } 
144 while( j <= rightEdge ) { 
145 AllMethods[x++] = temp[j++]; 
146 } 
147 } 
148 ///Metodo QuickSort 
149 void Methods::quickSort() { 
150 quickSort(0,getLastPos()); 
151 } 
152 
153 void Methods::quickSort(const int& leftEdge, const int& rightEdge) { 
154 if( leftEdge >= rightEdge ) { 
155 return; 
156 } 
157 
158 int i(leftEdge), j(rightEdge); 
159 
160 while( i < j ) { 
161 while( i < j and AllMethods[i].getRandom() <= AllMethods[rightEdge].getRandom() ) { 
162 i++; 
163 } 
164 while( i < j and AllMethods[j].getRandom() >= AllMethods[rightEdge].getRandom() ) { 
165 j--; 
166 } 
167 if( i != j ) { 
168 swapAllMethods(AllMethods[i],AllMethods[j]); 
169 } 
170 } 
171 if( i != rightEdge ) { 
172 swapAllMethods(AllMethods[i],AllMethods[rightEdge]); 
173 } 
174 
175 quickSort(leftEdge, i - 1); 
176 quickSort(i + 1, rightEdge); 
177 } 
178 Methods& Methods::operator=(const Methods& n){ 
179 copyAll(n); 
180 return *this; 
181 } 
RandomNumbers.h 
1 #ifndef RANDOMNUMBERS_H 
2 #define RANDOMNUMBERS_H 
3 
4 
5 class RandomNumbers { 
6 private:7 long random; 
8 public: 
9 void setRandom(const long int&); 
10 long int getRandom(); 
11 }; 
12 
13 
14 #endif // RANDOMNUMBERS_H 
RandomNumbers.cpp 
1 #include "RandomNumbers.h" 
2 
3 void RandomNumbers::setRandom(const long int& r){ 
4 random = r; 
5 } 
6 
7 long int RandomNumbers::getRandom(){ 
8 return random; 
9 } 
Capturas de pantalla: