Métodos de Ordenación

50 %
50 %
Information about Métodos de Ordenación
Education

Published on July 24, 2008

Author: alirambo

Source: authorstream.com

Métodos de Ordenación : Métodos de Ordenación Los métodos aquí presentados son: Intercambio ó Burbuja Selección Shell QuickSort Intercambio o Burbuja : Intercambio o Burbuja El método del intercambio consiste en comparar elementos contiguos e intercambiarlos hasta que todos los elementos del ARREGLO se ubiquen en el orden correcto. Slide 3: INICIO Enteros: I, J, Aux, V[N] I  1 J  1 Aux  0 Mientras I <= (N - 1) Hacer Mientras J <= (N – 1) Hacer Si V[J] > V[J + 1] Entonces Aux  V[J] V[J]  V[J + 1] V[J + 1]  Aux Fin Si J  J +1 Fin Mientras I  I + 1 J  1 Fin Mientras FIN Ya están ordenados, pero para comprobarlo habría que acabar esta segunda comprobación y hacer una tercera. Si el ARREGLO tiene N elementos, para estar seguro de que el ARREGLO está ordenado, hay que hacer N-1 pasadas, por lo que habría que hacer (N-1)*(N-i-1) comparaciones, para cada i desde 1 hasta N-1. El número de comparaciones es, por tanto, N(N-1)/2. Burbuja Alternativa 2 : Burbuja Alternativa 2 INICIO Enteros: I, J, Aux, V[N] I  1 J  1 Aux  0 Mientras I <= (N - 1) Hacer Mientras J <= (N – I) Hacer Si V[J] > V[J + 1] Entonces Aux  V[J] V[J]  V[J + 1] V[J + 1]  Aux Fin Si J  J +1 Fin Mientras I  I + 1 J  1 Fin Mientras FIN Este realiza menos iteraciones, debido a que no compara los últimos elementos una vez que estos se encuentran en su lugar. Pero, esté método aun se puede mejorar, por ello a continuación se expone la Alternativa 3. Burbuja Alternativa 3 : Burbuja Alternativa 3 INICIO Enteros: I, J, Aux, B, V[N] I  1 J  1 Aux  0 B  1 Mientras B = 1 Hacer B  0 Mientras J <= (N – 1) Hacer Si V[J] > V[J + 1] Entonces Aux  V[J] V[J]  V[J + 1] V[J + 1]  Aux B  1 Fin Si J  J +1 Fin Mientras I  I + 1 J  1 Fin Mientras FIN Selección : Selección Este método consiste en buscar el elemento más pequeño del ARREGLO y ponerlo en primera posición, luego entre los restantes se busca el elemento más pequeño y se coloca en segundo lugar, y así sucesivamente hasta colocar el último elemento. También se pude buscar el mayor elemento dentro de un ARREGLO, y ubicarlo al final y así sucesivamente, luego busca el segundo mayor elemento y lo ubica donde corresponda, y así por cada elemento del ARREGLO. Slide 7: INICIO Enteros: I, J, X, Aux, B, V[N] I  1 J  1 X  1 Aux  0 B  1 Mientras (I < N) Y (B = 1) Hacer B  0 Aux  V[I] X  I J  I Mientras J <= N Hacer J  J + 1 Si V[J] < Aux Entonces Aux  V[J] X  J B  1 Fin Si Fin Mientras V[X] V[I] V[I]  Aux I  I + 1 Fin Mientras FIN Guarda el menor (ó mayor) Valor del menor (ó mayor) Índice de la pos. del menor (o mayor) elemento Intercambio de elementos: en la posiciòn x coloca el elemento de V[I] Por ejemplo, si tenemos el ARREGLO [40,21,4,9,10,35], los pasos a seguir son: [4,21,40,9,10,35] <-- Se ubica el 4, el menor, en la primer posición :se cambia el 4 por el 40.[4,9,40,21,10,35] <-- Se coloca el 9, en la segunda posición: se cambia el 9 por el 21.[4,9,10,21,40,35] <-- Se coloca el 10, en la tercera posición: se cambia el 10 por el 40.[4,9,10,21,40,35] <-- Se coloca el 21, en la cuarta posición: ya está colocado.[4,9,10,21,35,40] <-- Se coloca el 35, en la tercera posición: se cambia el 35 por el 40. Si el ARREGLO tiene N elementos, el número de comprobaciones que hay que hacer es de N*(N-1)/2, , lo que nos deja un tiempo de ejecución, al igual de Intercambio. Shell : Shell Es una mejora del método de inserción directa, utilizado cuando el ARREGLO tiene una gran cantidad de elementos. En este método no se compara a cada elemento con el de su izquierda, como en inserción, sino con el que está a un cierto número de lugares (llamado salto) a su izquierda. Este salto es constante y su valor inicial es N/2 (siendo N el número de elementos, y siendo división entera). Se van dando pasadas hasta que en una pasada no se intercambie ningún elemento de sitio entonces el salto se reduce a la mitad, y se vuelven a dar pasadas hasta que no se intercambie ningún elemento, y así sucesivamente hasta que el salto vale 1. Slide 9: INICIO Enteros: J, S, Aux, V[N], B S  N J  1 Aux  0 B  1 Mientras S <> 1 Hacer B  1 S  (S Div 2) Mientras B = 1 Hacer B  0 J  1 Mientras (J + S) <> (N + 1) Hacer Si V[J] > V[J + S] Entonces Aux  V[J] V[J]  V[J + S] V[J + S]  Aux B  1 Fin Si J  J +1 Fin Mientras Fin Mientras Fin Mientras FIN Por ejemplo, lo pasos para ordenar el ARREGLO {40,21,4,9,10,35} mediante el método de Shell serían: Salto=3:Primera pasada:{9,21,4,40,10,35} <-- se intercambian el 40 y el 9.{9,10,4,40,21,35} <-- se intercambian el 21 y el 10.Salto=1:Primera pasada:{9,4,10,40,21,35} <-- se intercambian el 10 y el 4.{9,4,10,21,40,35} <-- se intercambian el 40 y el 21.{9,4,10,21,35,40} <-- se intercambian el 35 y el 40.Segunda pasada:{4,9,10,21,35,40} <-- se intercambian el 4 y el 9. Con sólo 6 intercambios se ha ordenado el ARREGLO, cuando por inserción se necesitaban muchos más. salto índice auxiliar bandera QuickSort : QuickSort El Método de Ordenación Rápida o QuickSort, se basa en el principio de Divide y Vencerás, , que consiste en ir subdividiendo el ARREGLO en ARREGLOSmás pequeños, y ordenar éstos. Para hacer esta división, se toma un valor del ARREGLO como pivote, y se mueven todos los elementos menores que este pivote a su izquierda, y los mayores a su derecha. A continuación se aplica el mismo método a cada una de las dos partes en las que queda dividido el ARREGLO. Normalmente se toma como pivote el primer elemento de ARREGLO, y se realizan dos búsquedas: una de izquierda a derecha, buscando un elemento mayor que el pivote, y otra de derecha a izquierda, buscando un elemento menor que el pivote. Cuando se han encontrado los dos, se intercambian, y se sigue realizando la búsqueda hasta que las dos búsquedas se encuentran. Slide 11: Por ejemplo, para dividir el ARREGLO [21,40,4,9,10,35], los pasos serían: [21,40,4,9,10,35] <-- se toma como pivote el 21. La búsqueda de izquierda a derecha encuentra el valor 40, mayor que pivote, y la búsqueda de derecha a izquierda encuentra el valor 10, menor que el pivote. Se intercambian: [21,10,4,9,40,35] <-- Si seguimos la búsqueda, la primera encuentra el valor 40, y la segunda el valor 9, pero ya se han cruzado, así que paramos. Para terminar la división, se coloca el pivote en su lugar (en el número encontrado por la segunda búsqueda, el 9, quedando: [9,10,4,21,40,35] <-- Ahora tenemos dividido el ARREGLO en dos ARREGLOS más pequeños: el [9,10,4] y el [40,35], y se repetiría el mismo proceso. INICIO Enteros: Izq, Der, Aux, V[N], P Izq  1 Der  N P  Aleatorio(N) Aux  0 Mientras Izq <= Der Hacer Mientras V[P] >= V[Izq] Hacer Izq  Izq + 1 Fin Mientras Mientras V[P] <= V[Der] Hacer Der  Der - 1 Fin Mientras Si Izq <= Der Aux  V[Izq] V[Izq]  V[Der] V[Der]  Aux Izq  Izq + 1 Der  Der - 1 Fin SI Fin Mientras Aux  V[Izq] V[Izq]  V[P] V[P]  Aux FIN Métodos de Búsqueda : Métodos de Búsqueda Secuencial o Lineal, Binaria, Hash. Secuencial o Lineal : Secuencial o Lineal La lógica del Método Secuencial o Lineal es muy sencilla, pues, se trata de ir comparando de uno en uno cada uno de los elementos de un ARREGLO, hasta encontrar el elemento buscado o simplemente no existan más elementos que comparar. Slide 14: INICIO Enteros: I, Dato, V[N] I  1 Dato  0 Leer Dato Mientras I <= N Hacer Si V[I] = Dato Entonces Imprimir “Dato Encontrado” I N Fin SI I  I + 1 Fin Mientras FIN El algoritmo anterior realiza la operación de búsqueda a la perfección, pero, no permite saber en que posición o no devuelve la posición en la que dicho elemento se encuentra, el algoritmo a continuación sí devuelve la posición en que se encuentra el elemento. INICIO Enteros: I, Dato, V[N] I  1 Dato  0 Leer Dato Mientras I < N Y V[I] <> Dato Hacer I  I + 1 Fin Mientras Si V[I] = Dato Entonces Imprimir “Dato Encontrado”, I Fin SI FIN Slide 15: INICIO Enteros: I, Dato, V[N], B I  1 Dato  0 B  0 Leer Dato Mientras I <= N Y B <> 1Hacer Si V[I] = Dato Entonces Imprimir “Dato Encontrado” B 1 Fin SI I  I + 1 Fin Mientras FIN Binario : Binario Este método se encuentra basado en el principio de Divide y Vencerás, para realizar una búsqueda con este método se necesita tener un ARREGLO ordenado, pues, la búsqueda consiste en dividir un ARREGLO, obteniendo así un Centro, y comparar este Centro con el valor buscado, si dicho Centro es mayor al valor buscado se procede a una nueva división y búsqueda del elemento por el lado Izquierdo, por donde se supone los elementos sean menores. Si el Centro es menor al elemento buscado, se procede del lado Derecho, donde se supone los elementos sean mayores, si el Centro es igual al elemento buscado, la búsqueda finaliza. Una vez comparados los posibles elementos y no siendo encontrado el buscado se finaliza la operación de búsqueda. Slide 17: Se declaran e inicializan las variables a utilizar por el algoritmo donde, Izq se refiere al límite del lado Izquierdo y Der al límite del lado Derecho, estas dos variables se utilizan junto al Centro puesto que cuando se determina un nuevo Centro también se deben determinar nuevos límites para los lados Izquierdo y Derecho del ARREGLO. Además se declara el Centro y la variable a utilizar para ingresar el dato a buscar. Se determina el primer Centro utilizando la Función DIV (División entera) puesto que las posiciones en un ARREGLO son valores enteros. INICIO Enteros: Izq, Der, , Cen Dato, V[N] Izq  1 Der 1 Cen  0 Dato  0 Cen  (Izq + Der) Div 2 Leer Dato Mientras Izq <= Der Y V[Cen] <> Dato Hacer Si V[Cen] > Dato Entonces Der  Cen -1 Si No Izq  Cen + 1 Fin SI Cen   Int(Izq + Der) / 2 Fin Mientras Si Dato = V[Cen] Entonces Imprimir “Dato Encontrado” Fin Si FIN Hash : Hash El método de Hashing o Conversión de Claves, consiste en transformar a un elemento o Clave en una dirección de un ARREGLO, mediante una función especial o Función de Transformación de Claves o de Conversión de Claves. El anterior método se denomina Truncamiento, en el cual se toma parte de una clave, para asignar las direcciones, por tal motivo, otra alternativa a dicho método sería, por ejemplo tomar el 4 y el último dígito de la clave. Plegamiento, consiste en tomar partes de la clave y realizar operaciones matemáticas con ellas para, de este modo, obtener una dirección por ejemplo tomar el 5, 4 y 2 digito, multiplicar el 5 digito por el 4 y luego sumar el segundo. Aritmética Modular, etc. Aritmética Modular, este método, consiste simplemente en tomar una Clave y dividirla por el Rango de un ARREGLO, tomando el modulo o resto como dirección. Existen métodos más complejos que los anteriores presentados, los cuales evitan en mayor grado las posibles colisiones, pero, a modo de ejemplo estos bastan.

Add a comment

Related presentations

Related pages

Unidad V Métodos de ordenamiento - Estructura de Datos

Todos los métodos de ordenación en Arrays implementan una versión del algoritmo de ordenación rápida (quicksort); ...
Read more

Métodos de ordenación - YouTube

Este video trata sobre los métodos de ordenación más sencillos que podemos encontrar en algoritmos de programación. En el video se tratarán ...
Read more

Copy of Métodos de Ordenación by Jorge Saavedra on Prezi

Métodos Ordenacion Quick-sort Ordenación por intercambio Métodos de Ordenación Ordenación por selección Conceptos clave (cc) photo by Metro Centric ...
Read more

Algoritmo de ordenamiento - Wikipedia, la enciclopedia libre

Enlaces externos. Explicación de los distintos métodos de ordenamiento en Java. (pdf) Discusión sobre varios algoritmos de ordenación y sus ...
Read more

Métodos de Ordenación - scribd.com

6ALGORITMOS DE ORDENACIÓN Y BÚSQUEDA OBJETIVOS Después del estudio de este capítulo usted podrá: • Conocer los al...
Read more

Bienvenidos Excel 2013: METODOS DE ORDENACION

METODOS DE ORDENACION Existen tres métodos de ordenación; SIMPLE, COMPUESTO PERSONALIZADO Pasos para ejecutar el método simple: 1. Insertar La celda ...
Read more

ALGORITMOS DE ORDENACIÓN Y BÚSQUEDA - Novella

Los métodos (algoritmos) de ordenación son numerosos, por ello se debe prestar especial aten-ción en su elección.
Read more

Sistemas de ordenación | Clase de gestion de archivos

Métodos de ordenación. Alfabético: basandose en una palabra que identifique los docuemntos. Cronológico: se realiza la ordenación por la fecha de los ...
Read more

METODOS DE ORDENACIÓN by María José Espinoza on Prezi

Los métodos de ordenamiento de datos son muy útiles, ya que la forma de arreglar los registros de una tabla en algún orden secuencial de acuerdo a un ...
Read more

Ordenación de Montes - Scribd

Gestión planificada de la selvicultura. Ordenación de montes. Los métodos de ordenación son modelos prácticos de gestión que organizan adecuadamente ...
Read more