Logo Studenta

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:

Otros materiales