estructura de datos - unidad 5 metodos de ordenamiento

TECNOLÓGICO NACIONAL DE MÉXICOIngeniería en Sistemas Computacionales

Estructura de DatosUnidad V: Métodos de Ordenamiento

Estructura de Datos

Competencia de la Unidad• Aplicar el método de ordenamiento pertinente en la solución de un

problema real.

Temario

INTRODUCCIÓN

•Muchas actividades humanas requieren que a diferentes colecciones de elementos utilizados se pongan en un orden específico. Las oficinas de correo y las empresas de mensajería ordenan el correo y los paquetes por códigos postales con el objeto de conseguir una entrega eficiente: Las facturas telefónicas se ordenan por la fecha de las llamadas; Las guías telefónicas se ordenan por orden alfabético de apellidos; Los estudiantes de una clase en la universidad se ordenan por sus

apellidos o por los números de expediente. • Por esta circunstancia una de las tareas que realizan más frecuentemente

las computadoras en el procesamiento de datos es la ordenación.

Algoritmos Internos de Ordenamiento

ORDENACIÓN• La ordenación o clasificación de datos (sort en inglés) es una operación

consistente en disponer un conjunto de datos en algún determinado orden con respecto a uno de los campos de los 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;

• En terminología de ordenación, el elemento por el cual está ordenado un conjunto de datos (o se está buscando) se denomina clave.

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.

• Los métodos (algoritmos) de ordenación son numerosos, por ello se debe prestar especial atención en su elección. • ¿Cómo se sabe cuál es el mejor algoritmo? La eficiencia es el factor que mide

la calidad y rendimiento de un algoritmo. • En el caso de la operación de ordenación, dos criterios se suelen seguir a la

hora de decidir qué algoritmo; de entre los que resuelven la ordenación es el más eficiente:

1) Tiempo menor de ejecución en computadora; 2) Menor número de instrucciones.

Los métodos de ordenación interna se dividen en dos grandes grupos:

Directos•Burbuja•Selección•Inserción

Indirectos (avanzados)

•Shellsort•Quicksort•Mergesort•Radixsort.

Nota: En el caso de listas pequeñas, los métodos directos se muestran eficientes. Sin embargo, en conjuntos grandes estos métodos se muestran ineficaces y es preciso recurrir a los métodos avanzados.

Los métodos que se analizaran para ordenación interna son los siguientes:

Burbuja Quicksort

Shellsort Radixsort

MÉTODO DE ORDENAMIENTO BURBUJA

El método de ordenación por burbuja es el más conocido y popular entre estudiantes y aprendices de programación, por su facilidad de comprender y programar; por el contrario, es el menos eficiente y por ello, normalmente, se aprende su técnica pero no suele utilizarse.

La técnica utilizada se denomina ordenación por burbuja u ordenación por hundimiento debido a que los valores más pequeños “burbujean” gradualmente (suben) hacia la cima o parte superior del array de modo similar a como suben las burbujas en el agua, mientras que los valores mayores se hunden en la parte inferior del array.

ORDENACIÓN POR BURBUJA

ALGORITMO DE LA BURBUJA

Para un array a con n elementos, la ordenación por burbuja requiere hasta n – 1 pasadas.

Por cada pasada se comparan elementos adyacentes y se intercambian sus valores cuando el

primer elemento es mayor que el segundo elemento.

Al final de cada pasada, el elemento mayor ha “burbujeado” hasta la cima de la sublista actual.

Por ejemplo, después que la pasada 1 está completa, la cola de la lista a[n – 1] está ordenada y

el frente de la lista permanece desordenado.

Las etapas del algoritmo son:

• En la pasada 1 se comparan elementos adyacentes.(a[0],a[1]), (a[1],a[2]), (a[2],a[3]), ... (a[n-2],a[n-1])

• Se realizan n – 1 comparaciones, por cada pareja (a[i],a[i+1]), se intercambian los valores si a[i+1] < a[i].

• En la pasada 2 se realizan las mismas comparaciones e intercambios, terminando con el elemento de segundo mayor valor en a[n-2]

• El proceso termina con la pasada n – 1, en la que el elemento más pequeño se almacena en a[0].

El algoritmo terminará cuando se termine la última pasada (n – 1), o bien cuando el valor del interruptor sea falso, es decir, que no se haya hecho ningún intercambio.

Vídeo de Ordenación Burbuja“Bubble Dance”

Método de Ordenación Burbuja

Realice el siguiente ejercicio aplicando el método de ordenación Burbuja

Conjunto de 8 elementos:

A [8]= {10, 3, 15, 6, 2, 8, 19, 18}

Debe describir pasada por pasada como se intercambian los elementos del arreglo hasta lograr tener un arreglo perfectamente ordenado de menor a mayor

CODIFICACIÓN DEL MÉTODO BURBUJA

EN C++

Módulo de ordenamiento

Variables Globales

MÉTODO DE ORDENAMIENTO QUICKSORT

MÉTODO DE ORDENAMIENTO QUICKSORT• El algoritmo conocido como quicksort (ordenación rápida) es simple, se basa

en la división de la lista en particiones a ordenar, en definitiva aplica la técnica "divide y vencerás". El método es, posiblemente, el más pequeño de código, más rápido y eficiente de los algoritmos conocidos de ordenación.• El algoritmo divide los n elementos de la lista a ordenar en dos partes o

particiones separadas por un elemento: una partición izquierda, un elemento central denominado pivote, y una partición derecha.• La partición se hace de tal forma que todos los elementos de la primera

sublista (partición izquierda) son menores que todos los elementos de la segunda sublista (partición derecha). • Las dos sublistas se ordenan entonces independientemente.

EJEMPLO DE QUICKSORT CON UN ARREGLO DE 5 ELEMENTOS

Vídeo de Ordenación RápidaQuicksort

Método de Ordenación Quicksort

Realice el siguiente ejercicio aplicando el método de ordenación Quicksort

Conjunto de 8 elementos:

A [8]= {10, 3, 15, 6, 2, 8, 19}

Debe describir pasada por pasada como se intercambian los elementos del arreglo hasta lograr tener un arreglo perfectamente ordenado de menor a mayor

CODIFICACIÓN DEL MÉTODO QUICKSORT

EN C++

Módulo de ordenamiento

Método main()

MÉTODO DE ORDENAMIENTO SHELLSORT

MÉTODO DE ORDENAMIENTO SHELLSORT• La ordenación Shell debe el nombre a su inventor, D. L. Shell. Se suele

denominar también ordenación por inserción con incrementos decrecientes. Se considera que es una mejora del método de inserción directa.• En el algoritmo de inserción, cada elemento se compara con los elementos

contiguos de su izquierda, uno tras otro. Si el elemento a insertar es el más pequeño hay que realizar muchas comparaciones antes de colocarlo en su lugar definitivo.• El algoritmo de Shell modifica los saltos contiguos por saltos de mayor tamaño

y con ello consigue que la ordenación sea más rápida. Generalmente, se toma como salto inicial n / 2 (siendo n el número de elementos), luego en cada iteración se reduce el salto a la mitad, hasta que el salto es de tamaño 1.

Ejemplo: Arreglo de 8 elementos

8 2 5 34 67 1

7 1 3 54 68 2

8 2 5 34 67 1Arreglo original

Salto inicial: 8 / 2 = 4

Arreglo resultante

3 1 5 82 67 4

Arreglo resultante

7 53 8

7 53 8

7 53 8

753 8

24 61

2 4 61

Primera parte Segunda parte

Salto subsecuente: 8 / 8 = 1

3 1 5 82 67 4

Arreglo resultante

1 2 3 74 85 6

31 5 82 67 4

31 5 82 67 4

31 5 82 67 4

31 5 82 674

31 5 82 674

31 5 82 674

31 5 82 6 74

Vídeo de OrdenaciónShell

Método de Ordenación Shellsort

Realice el siguiente ejercicio aplicando el método de ordenación Shellsort

Conjunto de 8 elementos:

A [8]= {10, 3, 15, 6, 2, 8, 19}

Debe describir pasada por pasada como se intercambian los elementos del arreglo hasta lograr tener un arreglo perfectamente ordenado de menor a mayor.

CODIFICACIÓN DEL MÉTODO SHELLSORT EN C++

MÉTODO DE ORDENAMIENTO RADIXSORT

MÉTODO DE ORDENAMIENTO RADIXSORTEste método de ordenación es un caso particular del algoritmo de clasificación por urnas. La manera de ordenar, manualmente, un conjunto de fichas nos da una idea intuitiva de este método de ordenación: Se forman montones de fichas, cada uno caracterizado por tener sus

componentes un mismo dígito en la misma posición. Inicialmente se forman los montones por las unidades (dígito de menor peso);

estos montones se recogen y agrupan en orden ascendente, desde el montón del dígito 0 al montón del dígito 9.

Entonces, las fichas están ordenadas respecto a las unidades, a continuación, se vuelve a distribuir las fichas en montones, según el dígito de las decenas.

El proceso de distribuir las fichas por montones y posterior acumulación en orden se repite tantas veces como número de dígitos tiene la ficha de mayor valor.

Suponer que las fichas están identificadas por un campo entero de tres dígitos, los pasos del algoritmo RadixSort para los siguientes valores:

Atendiendo al dígito de menor peso (unidades) los montones:

Una vez agrupados los montones en orden ascendente la lista es la siguiente

Esta lista ya está ordenada respecto al dígito de menor peso, respecto a las unidades. Pues bien, ahora se vuelven a distribuir en montones respecto al segundo dígito (decenas):

Una vez agrupados los montones en orden ascendente la lista es la siguiente

Se agrupan los montones en orden ascendente y la lista ya está ordenada

La lista fichas ya está ordenada respecto a los dos últimos dígitos, es decir, respecto a las decenas. Por último, se vuelven a distribuir en montones respecto al tercer dígito:

Vídeo de Ordenación por Montones

Radixsort

Método de Ordenación Radixsort

Realice el siguiente ejercicio aplicando el método de ordenación Radixsort

Conjunto de 15 elementos:

A [15]= {17, 23, 58, 34, 49, 12, 91, 62, 76, 5, 83, 15, 51, 96, 29}

Debe describir pasada por pasada como se intercambian los elementos del arreglo hasta lograr tener un arreglo perfectamente ordenado de menor a mayor

CODIFICACIÓN DEL MÉTODO RADIXSORT EN C++

Algoritmos Externos de Ordenamiento

Métodos de Ordenación Externa

• La ordenación externa o de archivos, recibe este nombre ya que los elementos se encuentran almacenados en un archivo de texto o de otro tipo, el cual se almacena en un dispositivo secundario o externo como lo es un disco duro o memoria USB.• Existen varios métodos de ordenación al respecto, los que se abordarán en

esta ocasión son:

Intercalación o Merge Mezcla Directa Mezcla Natural

MÉTODO DE ORDENAMIENTO INTERCALACIÓN

Método de Ordenamiento por Intercalación o Merge Pasos:• En este método de ordenamiento existen dos archivos con llaves previamente

ordenadas con cualquier otro método de ordenamiento, los cuales se mezclan para formar un solo archivo.• La longitud de los archivos puede ser diferente.• El proceso consiste en leer un registro de cada archivo y compararlos, el menor

es almacenando en el archivo de resultado y el otro se compara con el siguiente elemento del archivo si existe. • El proceso se repite hasta que alguno de los archivos quede vacío y los

elementos del otro archivo se almacenan directamente en el archivo resultado.

• Ejemplo del método de Intercalación

503 573 581 625 670 762

87 512 677

j

i

i < j = no; se mueve 87 y se mueve j

87

503 573 581 625 670 762

512 677

j

i

i < j = si; se mueve 503 y se mueve i

503

573 581 625 670 762

512 677

j

i

i < j = no; se mueve 512 y se mueve j

512

573 581 625 670 762

677

j

i

i < j = si; se mueve 573 y se mueve i

573

581 625 670 762

677

j

i

i < j = si; se mueve 581 y se mueve i

581

625 670 762

677

j

i

i < j = si; se mueve 625 y se mueve i

625

670 762

677

j

i

i < j = si; se mueve 670 y se mueve i

762

677

j

i

i < j = no; se mueve 677

677

762

i

El puntero i ya no tiene con quien compararse por lo que se asume él y los números subsecuentes están ordenados y se colocan al final.

762670RESULTADO

Vídeo de Ordenación por Intercalación o

Merge

CODIFICACIÓN DEL MÉTODO INTERCALACIÓN EN C++

MÉTODO DE ORDENAMIENTO MEZCLA DIRECTA

Método de Ordenamiento por Mezcla Directa

• Este método de ordenamiento realiza sucesivamente una partición y una fusión que produce secuencias ordenadas de longitud cada vez mayor.

• En la primera pasada la partición es de 1 y la fusión produce secuencias de longitud 2.

• Las particiones y las fusiones doblan su tamaño en cada pasada del procesamiento hasta lograr una partición del tamaño del archivo.

Ejemplo Mezcla Directa

09 75 14 68 29 17 31 25

09 14 29 31

75 68 17 25

Arreglo original con 8 elementos

En la primera división se compara por pares un elemento de cada arreglo

Comparamos en pares, un elemento por cada arreglo

Fusión resultante

09 < 75 = SI; se mueve 09 y después 75;

09

14 < 68 = SI; se mueve 14 y después 68;

75 14 68

29 < 17 = NO; se mueve 17 y después 29;

2917

31 < 25 = NO; se mueve 25 y después 31;

3125

Ahora tenemos un nuevo arreglo fusionado que

sirve como base para la siguiente división.

En el actual arreglo los elementos han quedado

agrupados en pares ordenados

Primera división

Arreglo de pares ordenados

09 75 14 68 2917 3125

Ejemplo Mezcla Directa

09 75 14 68

2917 3125

Segunda División

En la segunda división aumenta al doble el rango de comparación entre un arreglo y otro

Comparamos en pares, un elemento por cada arreglo de acuerdo al rango

Fusión resultante

09 < 17 = SI; se mueve 09;

Ahora tenemos un nuevo arreglo fusionado

que sirve como base para la siguiente

división. En el actual arreglo los

elementos han quedado agrupados en cuartetos

ordenados

09

75 < 17 = NO; se mueve 17;

17

75 < 29 = NO; se mueve 29; como es el último par del bloque se mueve el 75;

29 75

14 < 25 = SI; se mueve 14;

14

68 < 25 = NO; se mueve 25;

68 < 31 = NO; se mueve 31; como es el último elemento del bloque se mueve 68;

25 31 68

09 17 29 75 14 25 31 68

Arreglo de pares ordenados

09 17 29 75

14 25 31 68

Tercera División

En la tercera división aumenta al doble el rango de comparación entre un arreglo y otro respecto a la segunda división

Ejemplo Mezcla DirectaComparamos en pares, un elemento por cada arreglo de acuerdo al rango

Fusión resultante

09 < 14 = SI; se mueve 09;

El arreglo ha quedado ordenado

tras concluir la última división

09

17 < 14 = NO; se mueve 14;

14

29 < 25 = NO; se mueve 25;

17

17 < 25 = SI; se mueve 17;

25

29 < 31 = SI; se mueve 29;

29

75 < 31 = NO; se mueve 31;

31

75 < 68 = NO; se mueve 68; al ser el último elemento del bloque se mueve 75;

7568

Vídeo de Ordenación por Mezcla Directa

Variables globales

CODIFICACIÓN DEL MÉTODO MEZCLA DIRECTA EN C++

División del arreglo en 2 sublistas

Nota: Este programa está diseñado para funcionar con una lista de números mínima de 2 elementos y que aumenta al doble cada vez (2, 4, 8, 16 elementos, etc.).

Módulo main

Módulo para Mezcla directa

MÉTODO DE ORDENAMIENTO MEZCLA NATURAL

MÉTODO DE MEZCLA NATURAL

• Este método, conocido también como mezcla equilibrada, es una optimización del método de mezcla directa.• La diferencia es que las particiones se realizan en secuencias ordenadas de

tamaño variable en lugar de secuencias de tamaño fijo. • La fusión de las secuencias ordenadas se realiza en dos archivos. El proceso

termina cuando el segundo archivo queda vacío en el proceso de fusión-partición.

Arreglos Auxiliares

EJEMPLO DEL ALGORITMO DE MEZCLA NATURAL

09 75 14 68 29 17 31 25 04 05 13 18 72 46 61

09 75 29 25 46

72

61

14 68 17 31 04 05 13 18

09 75 29 25 4672 6114 68 17 31 04 05 13 18

A

AX1

AX2

Primera fusión

Partición 1 Partición 2 Partición 3 Partición 4

Este arreglo fusionado sirve como base para la siguiente pasada

Arreglos Auxiliares

EJEMPLO DEL ALGORITMO DE MEZCLA NATURAL

09 75 29 25 4672 6114 68 17 31 04 05 13 18A

AX1

AX2

Segunda fusión

Partición 1 Partición 2

Este arreglo fusionado sirve como base para la siguiente pasada

09 7514 68

2917 31

2504 05 13 18 72

46 61

09 14 17 29 31 7568 2504 05 13 18 46 61 72

Arreglos Auxiliares

EJEMPLO DEL ALGORITMO DE MEZCLA NATURAL

A

AX1

AX2

Tercera fusión

Partición 1

El arreglo esta ordenado por lo que termina el proceso

09 14 17 29 31 7568 2504 05 13 18 46 61 72

09 14 17 29 31 7568

2504 05 13 18 46 61 72

04 05 09 13 17 18 25 29 31 46 61 68 72 7514

Vídeo de Ordenación por Mezcla Natural

CODIFICACIÓN DEL MÉTODO MEZCLA NATURAL EN C++

Variables Globales Módulo Main

Nota: El algoritmo está diseñado para funcionar con números positivos, no debe tener números repetidos. El algoritmo funciona mejor con una lista de números mínima de 2 elementos y que aumenta al doble cada vez (2, 4, 8, 16, etc.).

Itsguasave.edu.mxES

TRU

CTU

RA D

E D

ATO

S

Módulo que realiza la mezcla natural

Módulo que calcula las particiones

Módulo que inicializa los arreglos auxiliares

Módulo que despliega el contenido del arreglo

Módulo que divide el arreglo original

en dos arreglos auxiliares

Bibliografía

• Joyanes, Zahonero. Estructura de Datos en C++. McGraw Hill. Madrid, España. 2007. ISBN: 978-84-481-5645-9.