Upload
others
View
41
Download
0
Embed Size (px)
Citation preview
Unidad 5: Arreglos y Vectores Métodos de ordenamiento
Ordenamiento burbuja
Ordenamiento por inserción
Arreglos multidimensionales
Métodos de ordenamiento
Debido a que las estructuras de datos son utilizadas para almacenar información, para poderrecuperar esa información de manera eficiente es deseable que aquella esté ordenada. Existenvarios métodos para ordenar las diferentes estructuras de datos básicas.
En general los métodos de ordenamiento no son utilizados con frecuencia, en algunos casossólo una vez. Hay métodos muy simples de implementar que son útiles en los casos en dónde elnúmero de elementos a ordenar no es muy grande (ej, menos de 500 elementos). Por otro ladohay métodos sofisticados, más difíciles de implementar pero que son más eficientes encuestión de tiempo de ejecución.
Los métodos sencillos por lo general requieren de aproximadamente n x n pasos para ordenar nelementos.
Los métodos simples son: Ordenamiento por inserción Ordenamiento burbuja Ordenamiento por selección Ordenamiento Shell
Ordenamiento Burbuja
La Ordenación de burbuja (Bubble Sort en inglés) es unsencillo algoritmo de ordenamiento. Funciona revisando cadaelemento de la lista que va a ser ordenada con el siguiente,intercambiándolos de posición si están en el orden equivocado. Esnecesario revisar varias veces toda la lista hasta que no se necesitenmás intercambios, lo cual significa que la lista está ordenada.Este algoritmo obtiene su nombre de la forma con la que suben por lalista los elementos durante los intercambios, como si fueran pequeñas"burbujas". También es conocido como el método del intercambiodirecto. Dado que solo usa comparaciones para operar elementos, selo considera un algoritmo de comparación, siendo el más sencillo deimplementar.
Ordenamiento Burbuja
Código fuente:
Ordenamiento burbuja
Ordenamiento por Inserción
El ordenamiento por inserción (insertion sort en inglés) es una manera muy natural deordenar para un ser humano, y puede usarse fácilmente para ordenar un mazo de cartasnumeradas en forma arbitraria. Requiere O(n²) operaciones para ordenar una lista de nelementos.
Inicialmente se tiene un solo elemento, que obviamente es un conjunto ordenado.Después, cuando hay k elementos ordenados de menor a mayor, se toma elelemento k+1 y se compara con todos los elementos ya ordenados, deteniéndose cuandose encuentra un elemento menor (todos los elementos mayores han sido desplazados unaposición a la derecha) o cuando ya no se encuentran elementos (todos los elementosfueron desplazados y este es el más pequeño). En este punto se inserta elelemento k+1 debiendo desplazarse los demás elementos.
Ordenamiento por Inserción
Paso a Paso
Ordenamiento por Inserción
Código fuente:
Ordenamiento por inserción
Unidad 5: Arreglos y Vectores Métodos de ordenamiento
Ordenamiento burbuja
Ordenamiento por inserción
Arreglos multidimensionales
Las matrices son arreglos con dos dimensiones, es decir se puededecir que tienen filas y columnas, su manejo es igual que los vectoresanteriormente tratados, los valores de las variables sellaman elementos, de la misma forma que en los arreglos y susíndices están compuestos por dos caracteres que indican su posición.Para poder acceder a un elemento se debe poner su posicióncompuesta de los dos índices.
Arreglos Multidimensionales- Matrices:Declaración y creación de matrices(DEFINICIÓN)
Por ejemplo para la matriz A y la posición en la fila 1 y columna 2 sedebe poner A[1][2], denotándose que el primer índice indica laposición de la fila y el segundo la posición de la columna.
Arreglos Multidimensionales- Matrices:Declaración y creación de matrices(DEFINICIÓN)
Ejemplo• Arreglos multidimensionales