ordenamiento - universidad nacional del sur
TRANSCRIPT
![Page 1: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/1.jpg)
OrdenamientoOrdenar una estructura de datos consiste en reacomodar sus elementos de manera tal que queden ordenados de acuerdo a un atributo clave.
Los algoritmos de ordenamiento resultan un tema de interés por varios motivos:
•Son importantes en diversas aplicaciones, en particular en el área de Bases de Datos, en donde los requerimientos de eficiencia hacen del ordenamiento un tema crítico.
•Existen muchísimos métodos para resolver el mismo problema y por lo tanto es un tema interesante para introducir nociones de tiempo de ejecución y eficiencia.
•Permiten ilustrar temas importantes de Resolución de Problemas.
![Page 2: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/2.jpg)
El método Merge Sort consiste en partir una estructura en mitades, ordenar cada mitad y luego intercalar ordenadamente ambas mitades.
Cada mitad se ordena aplicando el mismo método.
Dividir en “mitades” Ordenar la primera mitad Ordenar la segunda mitad Intercalar las mitades ordenadas
Merge Sort
![Page 3: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/3.jpg)
4 2 9 5 11 9 17 8
1-4
1-95-9
1-2
3-4
Merge Sort1 2 3 4 5 6 7 8 9
![Page 4: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/4.jpg)
si la estructura tiene más de 2 elementos Dividir en “mitades” Ordenar la primera mitad Ordenar la segunda mitad Intercalar las mitades ordenadas
sino si la cantidad de componentes es 2
Comparar e intercambiar
Merge Sort
Observemos que este algoritmo NO depende: - Del lenguaje de programación- Del tipo de componentes
![Page 5: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/5.jpg)
4 2 9 5 11 9 17 87 > 4
1-4
1-95-9
1-2
3-4
Merge Sort
![Page 6: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/6.jpg)
7 2 9 5 11 9 14 8
1-4
1-95-9
1-2
3-4
Merge Sort1 2 3 4 5 6 7 8 9
![Page 7: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/7.jpg)
7 2 9 5 11 9 14 82 < 9
1-4
1-95-9
1-2
3-4
Merge Sort
![Page 8: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/8.jpg)
7 2 9 5 11 9 14 8
1-4
1-95-9
1-2
3-4
Merge Sort1 2 3 4 5 6 7 8 9
![Page 9: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/9.jpg)
7 2 9 5 11 9 14 8
Intercalar
1-4
1-95-9
1-2
3-4
Merge Sort1 2 3 4 5 6 7 8 9
![Page 10: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/10.jpg)
4 7 9 5 11 9 12 8
1-4
1-95-9
Merge Sort1 2 3 4 5 6 7 8 9
![Page 11: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/11.jpg)
4 7 9 5 11 9 12 85 < 11
1-4
1-95-9
5-6
7-9
Merge Sort
![Page 12: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/12.jpg)
4 7 9 5 11 9 12 8
1-4
1-95-9
5-6
7-9
Merge Sort1 2 3 4 5 6 7 8 9
![Page 13: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/13.jpg)
4 7 9 5 11 9 12 8
1-4
1-95-9
5-6
7-9
7-7
8-9
Merge Sort1 2 3 4 5 6 7 8 9
![Page 14: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/14.jpg)
4 7 9 5 11 9 12 81 < 8
1-4
1-95-9
5-6
7-9
7-7
8-9
Merge Sort
![Page 15: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/15.jpg)
4 7 9 5 11 9 12 8
Intercalar1-4
1-95-9
5-6
7-9
7-7
8-9
Merge Sort1 2 3 4 5 6 7 8 9
![Page 16: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/16.jpg)
4 7 9 5 11 1 82 9
Intercalar1-4
1-95-9
5-6
7-9
Merge Sort1 2 3 4 5 6 7 8 9
![Page 17: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/17.jpg)
4 7 9 5 11 1 82 9
Intercalar1-4
1-95-9
Merge Sort1 2 3 4 5 6 7 8 9
![Page 18: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/18.jpg)
4 7 9 1 5 8 92 11
Intercalar1-4
1-95-9
Merge Sort1 2 3 4 5 6 7 8 9
![Page 19: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/19.jpg)
4 7 9 1 5 8 92 11
Intercalar1-4
1-95-9
Merge Sort
1-9
1 2 3 4 5 6 7 8 9
![Page 20: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/20.jpg)
Algoritmo MergeSort
si la cantidad de componentes es menor o igual a 2 si la cantidad de componentes es igual a 2 Comparar Intercambiarsino Dividir en mitades MergeSort primera mitad MergeSort segunda mitad Intercalar las mitades ordenadas
Merge Sort
![Page 21: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/21.jpg)
Algoritmo MergeSort DE ini,fin
si ini+1 = fin si Tini es mayor que Tfin
intercambiarTini , Tfin sino
si ini < fin Mitad = (ini+fin) / 2 (redondeo)
MergeSort ini,Mitad-1 MergeSort Mitad,fin Intercalar ini,Mitad-1,Mitad,fin
Merge Sort
![Page 22: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/22.jpg)
4 2 9 5 11 9 17 8
1-4
1-95-9
Merge Sort
MergeSort (1,4)
MergeSort (5,9)
MergeSort (1,9)
1 2 3 4 5 6 7 8 9
![Page 23: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/23.jpg)
4 7 9 1 5 8 92 11
1-4
1-95-9
MergeSort (1,4)
MergeSort (5,9)
Intercalar (1,4,5,9)
Merge Sort
2 4 5 7 8 9 91 11
MergeSort (1,9)
1 2 3 4 5 6 7 8 9
![Page 24: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/24.jpg)
El método intercalar se implementa utilizando la misma estrategia que hemos propuesto antes para intercalar dos estructuras ordenadas, solo que ahora se intercalan las dos mitades de una estructura.
Recordemos que al intercalar dos estructuras se genera una tercera en la cual los elementos se agregan al final.
En la implementación en Java este método es privado, solo es accesible dentro de la clase.
Merge Sort
![Page 25: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/25.jpg)
Algoritmo IntercalarDE i1,n1,i2,n2
crear aux con n2-i1+1 elementosIni=i1 //para recordar donde empiezo
mientras i1 <= n1 y i2 <= n2 si Ti1 es menor que Ti2 agregar Ti1 al final de aux i1++ sino agregar Ti2 al final de aux i2++
…
Merge Sort
![Page 26: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/26.jpg)
Algoritmo Intercalar (continuación)…
Merge Sort
mientras i1 <= n1 agregar Ti1 al final de aux i1++ mientras i2 <= n2 agregar Ti2 al final de aux i2++ //copiar en el arreglo originali1=ini-1para i entre 1 y n2-i1 Ti1+i = auxi
![Page 27: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/27.jpg)
4 7 9 5 11 1 88 3
Merge Sort
ini fin1 9
MergeSort(1,9)
1 2 3 4 5 6 7 8 9
Algoritmo MergeSort DE ini,fin
si ini+1 = fin si Tini es mayor que Tfin
intercambiarTini , Tfin sino si ini < fin Mitad = (ini+fin) / 2 MergeSort ini,Mitad-1 MergeSort Mitad,fin Intercalar ini,Mitad-1,Mitad,fin
1-9
![Page 28: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/28.jpg)
4 7 9 5 11 1 88 3
Merge Sort
Algoritmo MergeSort DE ini,fin
si ini+1 = fin si Tini es mayor que Tfin
intercambiarTini , Tfin sino si ini < fin Mitad = (ini+fin) / 2 MergeSort ini,Mitad-1 MergeSort Mitad,fin Intercalar ini,Mitad-1,Mitad,fin
ini fin1 9
mitad
5
1 2 3 4 5 6 7 8 9
1-9
MergeSort(1,9)
![Page 29: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/29.jpg)
4 7 9 5 11 1 88 3
Merge Sort
Algoritmo MergeSort DE ini,fin
si ini+1 = fin si Tini es mayor que Tfin
intercambiarTini , Tfin sino si ini < fin Mitad = (ini+fin) / 2 MergeSort ini,Mitad-1 MergeSort Mitad,fin Intercalar ini,Mitad-1,Mitad,fin
ini fin1 91 4
mitad
5
1 2 3 4 5 6 7 8 9
MergeSort(1,9) 1-4
1-9
![Page 30: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/30.jpg)
4 7 9 5 11 1 88 3
Merge Sort
Algoritmo MergeSort DE ini,fin
si ini+1 = fin si Tini es mayor que Tfin
intercambiarTini , Tfin sino si ini < fin Mitad = (ini+fin) / 2 MergeSort ini,Mitad-1 MergeSort Mitad,fin Intercalar ini,Mitad-1,Mitad,fin
ini fin1 91 4
mitad
53
1 2 3 4 5 6 7 8 9
MergeSort(1,4) 1-4
1-9
![Page 31: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/31.jpg)
4 7 9 5 11 1 88 3
Merge Sort
Algoritmo MergeSort DE ini,fin
si ini+1 = fin si Tini es mayor que Tfin
intercambiarTini , Tfin sino si ini < fin Mitad = (ini+fin) / 2 MergeSort ini,Mitad-1 MergeSort Mitad,fin Intercalar ini,Mitad-1,Mitad,fin
ini fin1 91 41 2
mitad
53
1 2 3 4 5 6 7 8 9
MergeSort(1,4) 1-4
1-9
1-2
![Page 32: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/32.jpg)
4 7 9 5 11 1 88 3
Merge Sort
Algoritmo MergeSort DE ini,fin
si ini+1 = fin si Tini es mayor que Tfin
intercambiarTini , Tfin sino si ini < fin Mitad = (ini+fin) / 2 MergeSort ini,Mitad-1 MergeSort Mitad,fin Intercalar ini,Mitad-1,Mitad,fin
ini fin1 91 41 2
84
mitad
53
1 2 3 4 5 6 7 8 9
MergeSort(1,2) 1-4
1-9
1-2
![Page 33: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/33.jpg)
4 7 9 5 11 1 88 3
Merge Sort
Algoritmo MergeSort DE ini,fin
si ini+1 = fin si Tini es mayor que Tfin
intercambiarTini , Tfin sino si ini < fin Mitad = (ini+fin) / 2 MergeSort ini,Mitad-1 MergeSort Mitad,fin Intercalar ini,Mitad-1,Mitad,fin
ini fin1 91 4
84
mitad
53
1 2 3 4 5 6 7 8 9
MergeSort(1,4) 1-4
1-9
1-2
![Page 34: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/34.jpg)
4 7 9 5 11 1 88 3
Merge Sort
Algoritmo MergeSort DE ini,fin
si ini+1 = fin si Tini es mayor que Tfin
intercambiarTini , Tfin sino si ini < fin Mitad = (ini+fin) / 2 MergeSort ini,Mitad-1 MergeSort Mitad,fin Intercalar ini,Mitad-1,Mitad,fin
ini fin1 91 4
84
3 4
mitad
53
1 2 3 4 5 6 7 8 9
MergeSort(3,4) 1-4
1-9
1-2
3-4
![Page 35: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/35.jpg)
4 7 9 5 11 1 88 3
Merge Sort
Algoritmo MergeSort DE ini,fin
si ini+1 = fin si Tini es mayor que Tfin
intercambiarTini , Tfin sino si ini < fin Mitad = (ini+fin) / 2 MergeSort ini,Mitad-1 MergeSort Mitad,fin Intercalar ini,Mitad-1,Mitad,fin
ini fin1 91 4
84
3 4
mitad
53
1 2 3 4 5 6 7 8 9
MergeSort(3,4) 1-4
1-9
1-2
3-4
![Page 36: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/36.jpg)
4 7 9 5 11 1 88 3
Merge Sort
Algoritmo MergeSort DE ini,fin
si ini+1 = fin si Tini es mayor que Tfin
intercambiarTini , Tfin sino si ini < fin Mitad = (ini+fin) / 2 MergeSort ini,Mitad-1 MergeSort Mitad,fin Intercalar ini,Mitad-1,Mitad,fin
ini fin1 91 4
84
mitad
53
1 2 3 4 5 6 7 8 9
MergeSort(1,4) 1-4
1-9
1-2
3-4
![Page 37: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/37.jpg)
4 7 9 5 11 1 88 3
Merge Sort
Algoritmo MergeSort DE ini,fin
si ini+1 = fin si Tini es mayor que Tfin
intercambiarTini , Tfin sino si ini < fin Mitad = (ini+fin) / 2 MergeSort ini,Mitad-1 MergeSort Mitad,fin Intercalar ini,Mitad-1,Mitad,fin
ini fin1 91 4
84
i1 n11 2
i2 n23 4
mitad
53
1 2 3 4 5 6 7 8 9
MergeSort(1,4) 1-4
1-9
1-2
3-4
![Page 38: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/38.jpg)
4 8 9 5 11 1 38 8
Merge Sort
Algoritmo MergeSort DE ini,fin
si ini+1 = fin si Tini es mayor que Tfin
intercambiarTini , Tfin sino si ini < fin Mitad = (ini+fin) / 2 MergeSort ini,Mitad-1 MergeSort Mitad,fin Intercalar ini,Mitad-1,Mitad,fin
ini fin1 9
74
mitad
5
1 2 3 4 5 6 7 8 9
MergeSort(1,9) 1-4
1-95-9
1-2
3-4
![Page 39: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/39.jpg)
4 8 9 5 11 1 38 8
Merge Sort
Algoritmo MergeSort DE ini,fin
si ini+1 = fin si Tini es mayor que Tfin
intercambiarTini , Tfin sino si ini < fin Mitad = (ini+fin) / 2 MergeSort ini,Mitad-1 MergeSort Mitad,fin Intercalar ini,Mitad-1,Mitad,fin
ini fin1 95 9
74
mitad
57
1 2 3 4 5 6 7 8 9
MergeSort(1,9) 1-4
1-95-9
1-2
3-4
![Page 40: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/40.jpg)
Introducción a la Programación Orientada a Objetos
El método de Quick Sort consiste en acomodar un elemento llamado Pivot en su posición definitiva y luego ordenar la estructura que queda a su izquierda y la que queda a su derecha.Todos los elementos en posiciones menores al Pivot son menores que él.Todos los elementos en posiciones mayores al Pivot son mayores que él.Las dos estructuras se ordenan aplicando el mismo método.
Ordenamiento: Quick Sort
![Page 41: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/41.jpg)
Introducción a la Programación Orientada a Objetos
Ordenamiento: Quick Sort
![Page 42: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/42.jpg)
Introducción a la Programación Orientada a Objetos
Acomodar un elemento llamado Pivot Ordenar a la izquierda del Pivot Ordenar a la derecha del Pivot
Ordenamiento: Quick Sort
![Page 43: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/43.jpg)
Introducción a la Programación Orientada a Objetos
Algoritmo QuickSort
si hay más de un elemento Acomodar Pivot QuickSort a la izquierda del Pivot QuickSort la derecha del Pivot
Ordenamiento: Quick Sort
![Page 44: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/44.jpg)
Introducción a la Programación Orientada a Objetos
Algoritmo QuickSort DE ini,Fin si ini < fin pospivot ← AcomodarPivot ini,fin QuickSort ini,pospivot-1 QuickSort pospivot+1,fin
Ordenamiento: Quick Sort
Es un algoritmo genérico, no depende del tipo de los elementos.
![Page 45: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/45.jpg)
Introducción a la Programación Orientada a Objetos
Algoritmo AcomodarPivotDE ini,finDS pos pos ←avanzar ini,fin
Ordenamiento: Quick Sort
![Page 46: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/46.jpg)
Introducción a la Programación Orientada a Objetos
Algoritmo avanzarDE izq, derDS posPivsi izq >= der posPiv ← izqsino si T izq >= T izq+1 intercambiar izq izq+1 posPiv ← avanzar izq+1,der sino posPiv ← retroceder izq,der
Ordenamiento: Quick Sort
![Page 47: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/47.jpg)
Introducción a la Programación Orientada a Objetos
Algoritmo retrocederDE izq, derDS posPivsi izq >= der posPiv ← izqsino si T izq <= T der posPiv ← retroceder izq,der-1 sino intercambiar izq+1,der posPiv ← avanzar izq,der-1
Ordenamiento: Quick Sort
Es un algoritmo genérico, no depende del tipo de los elementos.
![Page 48: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/48.jpg)
TDA Matriz Racionales
![Page 49: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/49.jpg)
TDA Matriz Racionales
Implementar un TDA MatrizRac que brinde operaciones para calcular el producto de un escalar por una matriz, la suma de dos matrices, establecer la matriz identidad, decidir si una matriz es cuadrada, decidir si una matriz es la matriz identidad, decidir si es una matriz simétrica.
La matriz se representa mediante un arreglo de dos dimensiones de números racionales
La clase que encapsula al arreglo brinda operaciones para establecer y obtener un elemento y para comparar, copiar y clonar matrices.
![Page 50: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/50.jpg)
TDA Racional Racional
<<Constructor>>Racional (n: entero, d: entero)<<Comandos>>establecerNum(n: entero)establecerDen(d: entero)copy(r: Racional)<<Consultas>>obtenerNum(): enteroobtenerDen(): enterotoString(): Stringequals(rac: Racional): booleanclone(): Racionalsuma(rac: Racional): Racionalresta(rac: Racional): Racionalproducto(rac: Racional): Racionalcociente(rac: Racional): Racional
<<atributos de instancia>>num: enteroden: enteroRequiere d > 0
![Page 51: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/51.jpg)
TDA Matriz Racionales - DiseñoMatriz
Racional [] [] mr
<<constructores>>Matriz (fMax,cMax : entero)
<<comandos>>establecerElem (f,c : entero, elem : Racional)copy(m : Matriz) invertirFilas(f1,f2:entero)xEscalar(r:Racional)transpuesta():Matriz<<Consultas>>...
Asume que la posiciónes válida
Asume que se verificóque f1 y f2 son válidas
![Page 52: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/52.jpg)
TDA Matriz Racionales - DiseñoMatriz
Racional [] [] mr<<consultas>>existePos(f,c : entero) : booleanobtenerNFil () : enteroobtenerNCol () : enteroobtenerElem (f,c : entero) : Racionalclone() :Matrizequals(m:Matriz): booleanesCuadrada () : booleanesIdentidad():booleanesTriangularSuperior():booleanesSimetrica():booleanesRala():boolean...
Asume que la posiciónes válida
Más de la mitadde los elementos
son 0
![Page 53: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/53.jpg)
TDA Matriz Racionales - DiseñoMatriz
Racional [] [] mr
<<consultas>>...cantElem (elem : Racional) : enteroestaElem(elem : Racional) : booleanmayorElemento () : RacionalfilaMayorElemento () : enterovectorMayores () :Vectorsuma (m:Matriz) : Matrizproducto(m:Matriz):Matriz
Asume que se controlaron filas
y col
Genera un vectorcon el mayor
elementode cada fila
![Page 54: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/54.jpg)
TDA Matriz Racionales – Multiplicación de Matrices
• Dadas dos matrices A (mxn) y B (nxp), tales que el numero de columnas de la matriz A es igual al numero de filas de la matriz B.
• El resultado de AB es una nueva matriz C (mxp) .
![Page 55: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/55.jpg)
TDA Matriz Racionales - Implementación
public Matriz producto(Matriz b){
Matriz c = new Matriz(this.obtenerNfil(), b.obtenerNcol())
for(int i = 0; i< c.obtenerNfil() ; i++){
for(int j = 0; j < c.obtenerNcol() ; j++){
//multiplicar fila i por columna j
}
}
return c;
}
![Page 56: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/56.jpg)
TDA Matriz Racionales - Implementación
//multiplicar fila i por columna j
________ acumulador = ______0.0_______;
for (int n = 0; n < this.obtenerNcol() ; n++){
________ prod = this.obtenerElem(i, n)____X____(b.obtenerElem(n,j);
acumulador = acumulador__+__(prod) ;
}
c.establecerElem(i,j, acumulador);
![Page 57: Ordenamiento - Universidad Nacional del Sur](https://reader036.vdocumento.com/reader036/viewer/2022071623/62d2c50af681d34abf583537/html5/thumbnails/57.jpg)
TDA Matriz Racionales - Implementación
//multiplicar fila i por columna j
Racional componente = new Racional(0,1);
for (int n = 0; n < this.obtenerNcol() ; n++){
Racional prod = this.obtenerElem(i, n).producto(b.obtenerElem(n,j);
componente = componente.suma(prod) ;
}
c.establecerElem(i,j, Componente);