32
MÉTODOS DE ORDENACIÓN MELINA CASTAÑEDA PÍREZ. DANIEL MARTÍNEZ SUASTEGUI. SILVERIO QUIÑONEZ GARCÍA. GUSTAVO AXEL SAUCEDO ROMÁN.

Ordenacion archivos

Embed Size (px)

Citation preview

Page 1: Ordenacion archivos

MÉTODOS DE ORDENACIÓNMELINA CASTAÑEDA PÍREZ.

DANIEL MARTÍNEZ SUASTEGUI.

SILVERIO QUIÑONEZ GARCÍA.

GUSTAVO AXEL SAUCEDO ROMÁN.

Page 2: Ordenacion archivos

¿QUÉ ES ORDENACIÓN?LA ORDENACIÓN O CLASIFICACIÓN DE DATOS (SORT EN INGLÉS) ES UNA OPERACIÓN CONSISTENTE EN DISPONER UN CONJUNTO ESTRUCTURA DE DATOS EN ALGÚN DETERMINADO ORDEN CON RESPECTO A UNO DE LOS CAMPOS DE ELEMENTOS DEL CONJUNTO. POR EJEMPLO, CADA ELEMENTO DEL CONJUNTO DE DATOS DE UNA GUÍA TELEFÓNICA TIENE UN CAMPO NOMBRE, UN CAMPO DIRECCIÓN Y UN CAMPO NÚMERO DE TELÉFONO; LA GUÍA TELEFÓNICA ESTÁ DISPUESTA EN ORDEN ALFABÉTICO DE NOMBRES. LOS ELEMENTOS NUMÉRICOS SE PUEDEN ORDENAR EN ORDEN CRECIENTE O DECRECIENTE DE ACUERDO AL VALOR NUMÉRICO DEL ELEMENTO

Page 3: Ordenacion archivos

EJEMPLO DE ORDENACIÓN

• Por ejemplo, para una guía telefónica, la lista está clasificada en orden ascendente por el campo clave k, donde k[i] es el nombre del abona- do (apellidos, nombre).

• ,

Page 4: Ordenacion archivos

ORDENACIÓN POR BURBUJA

• Este método es clásico y muy sencillo, aunque por desgracia poco eficiente. La ordenación por burbuja (<<buble sort») se basa en comparar elementos adyacentes de la lista (vec- tor) e intercambiar sus valores si están desordenados. De este modo se dice que los valo- res más pequeños burbujean hacia la parte superior de la lista (hacia el primer elemen- to), mientras que los valores más grandes se hunden hacia el fondo de la lista. Consideremos, como ya se ha expuesto, clasificaciones en orden creciente

Page 5: Ordenacion archivos
Page 6: Ordenacion archivos
Page 7: Ordenacion archivos

ORDENACIÓN POR SELECCIÓN

• El algoritmo de ordenación por selección de una lista (vector) de n elementos tiene los siguientes pasos:

• l. Encontrar el elemento mayor de la lista.

• 2. Intercambiar el elemento mayor con el elemento de subíndice n (o bien si es el elemento menor con el subíndice 1).

• 3. A continuación se busca el elemento mayor en la sublista de subíndices 1.. n - 1, Y se intercambia con el elemento de subíndice n - 1; por consiguiente, se sitúa el segundo elemento mayor en la posición n - l.

• 4. A continuación se busca el elemento mayor en la sublista 1.. n - 2, y así sucesivamente.

Page 8: Ordenacion archivos

DESCRIPCIÓN DEL MÉTODO

• Su funcionamiento es el siguiente:

• Buscar el mínimo elemento de la lista

• Intercambiarlo con el primero

• Buscar el siguiente mínimo en el resto de la lista

• Intercambiarlo con el segundo

• Y en general:

• Buscar el mínimo elemento entre una posición i y el final de la lista

• Intercambiar el mínimo con el elemento de la posición i

• De esta manera se puede escribir el siguiente pseudocódigo para ordenar una lista de n elementos indexados desde el 1:

Page 9: Ordenacion archivos

ANÁLISIS SELECCIÓN

• Análisis de la ordenación por selección

• Número de comparaciones por cada una de las pasadas.

• Pasada Número de comparaciones

• El número total de comparaciones es

• 1 + 2 + 3 + ... + n - 2 + n - 1 =

• n'(n-l)_ 1 ) 2 - 2(n--n)

• La eficiencia, como se observa, es similar al método de la burbuja

Page 10: Ordenacion archivos

ORDENACIÓN POR INSERCIÓN.

Page 11: Ordenacion archivos

ALGORITMO DE INSERCIÓN.

Desde k 2 hasta n hacer:

• Guardar el valor de ese elemento A[k] en una variable aux.

• Hacer espacio para aux desplazando todos los valores mayores que dicho valor A[k] una posición.

• Insertar el valor de aux en el lugar del último valor desplazado.

Fin desde.

Page 12: Ordenacion archivos

ALGORITMO DE DESPLAZAMIENTO.

Mientras el primer elemento no se desplaza y valor del elemento > aux

Hacer:

• Desplazar elemento una posición.

• Comprobar valor del siguiente elemento.

• Definir nuevaPos como posición original del último elemento desplazado.

Fin mientras.

Page 13: Ordenacion archivos

ALGORITMO DE SHELL.

Se suele denominar también ordenación por disminución de incremento (gap).

La idea general del método (algoritmo) es la siguiente:

504 88 513 62 908 171 898 277 654 427 150 510 612 675 750 704

Page 14: Ordenacion archivos

ALGORITMO DE SHELL.

l. Se divide la lista original (16 elementos, en este ejemplo) en ocho grupos de dos (considerando un incremento o intervalo de 16/2 = 8).

Page 15: Ordenacion archivos

2. Se clasifica cada grupo por separado (se comparan las parejas de elementos y si no están ordenados se intercambian entre sí de posiciones).

Page 16: Ordenacion archivos

3. Se divide ahora la lista en cuatro grupos de cuatro (intervalo o salto de 8/2 = 4) y nuevamente se clasifica cada grupo por separado.

4. Un tercer paso clasifica dos grupos de ocho registros y luego un cuarto paso completa el trabajo clasificando los 16 registros.

Page 17: Ordenacion archivos

2. Se clasifica cada grupo por separado (se comparan las parejas de elementos y si no están ordenados se intercambian entre sí de posiciones).

Page 18: Ordenacion archivos

ORDENACIÓN RÁPIDA.

La idea básica de la ordenación rápida de un array (lista) es:

• Elegir un elemento del array denominado pivote.

• Dividir o partir el array original en dos subarrays o mitades (sublistas), de modo

que en una de ellas estén todos los elementos menores que el pivote y en la otra sublista todos los elementos mayores que el pivote.

• Las sublistas deben ser ordenadas, independientemente, del mismo modo, lo que conduce a un algoritmo recursivo.

Page 19: Ordenacion archivos

ALGORITMO DE ORDENACIÓN RÁPIDA.

1. Inicializar 1 a Primero (primer índice del array)

2. Inicializar J a Ultimo (último índice del array)

3. Seleccionar el elemento pivote (término Central)

Central ~ A [(Primero + Ultimo) div 2]

4. Repetir

4.1. Mientras A[I] < Central hacer

1 = 1 +1

Fin Mientras

4.2. Mientras A [J] > Central hacer

J = J - 1

Fin Mientras

Page 20: Ordenacion archivos

ALGORITMO DE ORDENACIÓN RÁPIDA.4.3. Si 1 <= J entonces

Intercambiar (A [I] ,A [J]

Hasta que 1 > J

5. Si J > Primero, llamar al procedimiento Partir, para dividir la

sublista izquierda [Primero … J]

6. Si 1 < Ultimo, llamar al procedimiento Partir, para dividir la

sublista derecha [1 … Ultimo]

Page 21: Ordenacion archivos

ORDENACIÓN POR MEZCLA.

El proceso consiste en dividir la lista en dos mitades y cada una de las mitades en otras mitades. Este proceso se repite hasta que cada sublista contiene, cada una, una entrada

Page 22: Ordenacion archivos

ALGORITMO DE ORDENACIÓN POR MEZCLA.

l. Dividir la lista en dos mitades.

2. Ordenar la sublista izquierda.

3. Ordenar la sublista derecha.

4. Mezclar las dos sublistas juntas.

1. Si Primero < Ultimo, entonces {índices de la lista original}

1.1. Central f- (Primero +Ultimo) div 2 {punto de división para la partición}

1.2. Llamar a OrdMezcla a [ Primero .. Central )

1.3. Llamar a OrdMezcla a [Central+1 .. Ultimo]

1.4. Mezclar a [Primero .. Central] con a [Cen tral+l. .Ultimo]

Page 23: Ordenacion archivos
Page 24: Ordenacion archivos

Este algoritmo de ordenación está basado en la estructura de montículo.

MontículoSe define un montículo de tamaño n como un árbol binario completo de n nodos, tal que el contenido de cada nodo es mayor o igual al contenido de su padre.

Método de Ordenación por Montículos

Page 25: Ordenacion archivos

El nodo ocupara la posición 1 en el arreglo, y en la posición 2 y 3 estarán sus nodos hijo izquierdo y derecho, respectivamente.La representación del árbol del ejemplo en un arreglo es:

Método de Ordenación por Montículos

Es claro que a partir de esta definición de montículo la raíz del árbol (o primer elemento del arreglo) es el elemento más pequeño; en definitiva, V[l] siempre tendrá el elemento mas pequeño.Según esto podemos descomponer el método de ordenación heapsort en los siguientespasos:1. Construir un montículo inicial con todos los elementos del vector: V[lJ, V[2J,

... V[nJ2. Intercambiar los valores de . V[lJ y V[nJ (siempre se queda el máximo en el

extremo).3. Reconstruir el montículo con los elementos V[lJ, V[2J, ... V[n - 1].4. Intercambiar los valores de V[lJ y V[n - 1J.5. Reconstruir el montículo con los elementos V[l], V[2J, '" V[n - 2].

Page 26: Ordenacion archivos

Según el algoritmo debemos considerar dos problemas: construir el montículo inicial y cómo restablecer los montículos intermedios. Como ahora veremos, la solución a ambos problemas va a ser mediante una misma rutina. Consideremos que ya está construido el montículo inicial y se ha realizado el intercambio. La figura nos muestra esta , situación

Método de Ordenación por Montículos

Page 27: Ordenacion archivos

Método de Ordenación por Montículos

Page 28: Ordenacion archivos

Para restablecer el montículo hay dos posibilidades:•V[l] es menor o igual que los valores de sus hijos, entonces la propiedad del montículo no se ha roto.• En otro caso, el elemento mínimo que necesitamos poner en V[ 1] es o su hijo izquierdo o su hijo derecho (V[2], V[3], respectivamente). Por lo que se determina el menor de sus hijos y éste se intercambia con V[l). El proceso continúa repitiendo las mismas comparaciones entre el nodo intercambiado y sus nodos hijos; así hasta llegar a un nodo en el que no se viole la propiedad de montículo, o estemos en un nodo hoja. La figura nos muestra el proceso de restablecer la condición de montículo en el árbol resultante del intercambio; este proceso se expresa diciendo que el nodo situado en la cúspide del árbol se deja «hundir» por el camino de claves mínimas

Método de Ordenación por Montículos

Page 29: Ordenacion archivos

Método de Ordenación BinsortEste método, también llamado clasificación por urnas, plantea conseguir tiempos de ejecución menores de O(n lag n) para ordenar n elementos siempre que se conozca algo acerca del tipo de las claves por las que se están ordenando.Este método utiliza urnas, cada urna contiene todos los registros con una misma clave. El proceso consiste en examinar cada registro R a clasificar y situarle en la urna 1, coincidiendo i con el valor del campo clave de R. En la mayoría de los casos en que se utilice el algoritmo será necesario guardar más de un registro en una misma urna por tener claves repetidas. Entonces estas urnas hay que concatenarlas en el orden de menor índice de urna a mayor, así quedará el arreglo en orden creciente respecto al campo clave. En la figura se tiene un arreglo de 1 a m urnas.

Page 30: Ordenacion archivos

Método de Ordenación Binsort

Page 31: Ordenacion archivos

Método de Ordenación BinsortEste método se puede considerar como una generalización de la clasificación por urnas Aprovecha la estrategia de la forma más antigua de clasificación manual, consistente en hacer diversos montones de fichas, cada uno caracterizado por tener sus componentes un mismo dígito (letra si es alfabética) en la misma posición; estos montones se recogen en orden ascendente y se reparte de nuevo en montones según el siguiente dígito de la clave. Para centrarnos en lo que estamos diciendo, supóngase que tenemos que ordenar estas fichas identificadas por tres dígitos:345, 721,425,572,836,467,672,194,365,236,891, 746,431,834,247,529,216,389

Page 32: Ordenacion archivos

Método de Ordenación BinsortTomando los montones en orden, la secuencia de fichas queda: 721 891 431 572 672 194 834 345 425 365 836 236 746 216 467 247 529 389 De esta secuencia podemos decir que está ordenada respecto al dígito de menor peso. Pues bien, ahora de nuevo distribuimos la secuencia de fichas en montones respecto al segundo dígito:

Tomando de nuevo los montones en orden, la secuencia de fichas queda así:216 721 425 529 431 834 836 236 345 746 247 365 467 572 672 389 891 194