Programación II

Ing. Mauricio Paletta, Msc

Coordinación General de Pregrado

UNIVERSIDAD NACIONAL EXPERIMENTAL DE GUAYANA

INGENIERÍA EN INFORMÁTICA

Programación II

Ordenación

Presentación

Programación II

Introducción

Ordenación proceso de ordenamiento de

datos siguiendo un criterio específico (menor

a mayor o ascendente, mayor a menor o

descendente, otros).

Muy común en el desarrollo de algoritmos y

programas.

Se le ha dedicado tiempo y esfuerzo para su

estudio.

Programación II

Introducción

Programación II

Algoritmos

1) Por selección.

2) De burbuja.

3) Por inserción.

4) Por incrementos (Shell-sort).

5) Por mezcla (Merge-sort).

6) Por montículos (Heapsort).

7) Rápida (Quicksort)

Programación II

Ordenación por Selección

• En cada iteración se busca el elemento

más pequeño (grande o según el criterio de

ordenación) y se ubica en la posición

correspondiente.

• Se hace un intercambio de posiciones entre

el elemento encontrado y aquél que ocupa

el puesto que el primero debe ocupar.

• Se repite tantas veces como sea necesario.

Programación II

Ordenación por Selección

Programación II

Ordenación por Selección

Programación II

Ordenación por Selección

Programación II

Ordenación por Selección

• Ejemplo:

Programación II

Ordenación por Selección

• Dos ciclos de orden lineal: 1) para buscar el

próximo elemento según el criterio y 2) para

cubrir todos los espacios del conjunto.

• Orden del algoritmo O(n2).

Programación II

Ordenación de Burbuja

• En cada iteración se busca el elemento

más pequeño (grande o según el criterio de

ordenación) y se ubica en la posición

correspondiente.

Programación II

Ordenación de Burbuja

Programación II

Ordenación de Burbuja

Programación II

Ordenación de Burbuja

Programación II

Ordenación de Burbuja

• Ejemplo:

Programación II

Ordenación de Burbuja

• Dos ciclos de orden lineal: 1) para cubrir

todos los espacios del conjunto y 2) para

burbujear el próximo elemento según el

criterio.

• Orden del algoritmo O(n2).

Programación II

Ordenación por Inserción

• En cada iteración se busca el elemento

más pequeño (grande o según el criterio de

ordenación) y se ubica en la posición

correspondiente, aprovechando el

ordenamiento parcial del subconjunto ya

procesado.

Programación II

Ordenación por Inserción

Programación II

Ordenación por Inserción

Programación II

Ordenación por Inserción

• Ejemplo:

Programación II

Ordenación por Inserción

Programación II

Ordenación por Inserción

• Ejemplo:

Programación II

Ordenación por Inserción

• El orden del algoritmo es O(n2). Si el

conjunto ya está ordenado (mejor caso) el

orden del algoritmo es O(n).

Programación II

Ordenación por Incrementos (Shell-sort)

• Donald Shell; “A High-Speed Procedure”,

Communications of the ACM, vol. 2, N 7,

1959, pp. 30-32.

• Se puede ver como una ordenación por

inserción con un enfoque de divide y

vencerás.

• En lugar de ordenar todo el conjunto desde

el comienzo, se ordenan primero pequeños

subgrupos utilizando el método de inserción.

Programación II

Ordenación por Incrementos (Shell-sort)

• Luego de ordenar estos pequeños

subgrupos, se repite el proceso esta vez

con grupos más grandes (un aproximado

del doble de elementos de los grupos

iniciales).

• Finalmente se ordena el conjunto total con

el método de inserción.

Programación II

Ordenación por Incrementos (Shell-sort)

Programación II

• Ejemplo:

Ordenación por Incrementos (Shell-sort)

Programación II

Ordenación por Incrementos (Shell-sort)

• El análisis general del algoritmo sigue

siendo un problema abierto.

• El rendimiento depende de cómo se elija la

secuencia decreciente de los intervalos. Por

ejemplo, para potencias sucesivas de 2 (32,

16, 8, 4, 2, 1) es O(n2). Para el caso 2k – 1

(31, 15, 7, 3, 1) – secuencia de Hibbard -se

puede probar que el desempeño es O(n3/2)

Programación II

Ordenación por Mezcla (Merge-sort)

• Mezcla (merge) consiste en unir dos

conjuntos de datos.

• En este caso se tienen dos conjuntos

ordenados y se desea obtener un tercer

conjunto ordenado que contenga las dos

primeras secuencias ordenadas.

Programación II

Ordenación por Mezcla (Merge-sort)

Programación II

Ordenación por Mezcla (Merge-sort)

Programación II

Ordenación por Mezcla (Merge-sort)

• Ejemplo:

Programación II

Ordenación por Mezcla (Merge-sort)

• Dado lo recursivo del algoritmo su análisis

no es sencillo. La parte de la mezcla tiene

orden igual a O(i) donde i es el tamaño

actual del conjunto. La profundidad de la

recursión es log n para n elementos. Luego

la complejidad del algoritmo se puede

estimar en O(n log n).

Programación II

Ordenación por Montículos (Heapsort)

• Un montículo es una estructura tipo árbol

binario que garantiza que en la cima

siempre está el elemento mayor.

• Si se van eliminando los elementos de la

cima y se va rearmando el montículo

adecuadamente se puede ir ordenando el

conjunto de mayor a menor.

Programación II

Ordenación por Montículos (Heapsort)

Programación II

Ordenación por Montículos (Heapsort)

• Ejemplo:

Programación II

Ordenación por Montículos (Heapsort)

• Ejemplo:

Programación II

Ordenación por Montículos (Heapsort)

• Ejemplo:

Programación II

Ordenación por Montículos (Heapsort)

• Construir el montículo tiene una

complejidad de O(n); las n eliminaciones

representan un orden de O(log n) cada una;

luego la complejidad del algoritmo es O(n

log n).

• A diferencia de los otros algoritmos,

siempre se conoce el mayor elemento del

conjunto parcialmente ordenado.

Programación II

Ordenación Rápida (Quicksort)

• Desarrollado por C.A.R. Hoare en 1962.

• La idea básica es acomodar el conjunto en

dos partes de manera tal que todos los

elementos del subconjunto izquierdo sean

menores que los del subconjunto derecho.

• El elemento que establece la división se

llama pivote.

• El proceso se repite recursivamente hasta

lograr el ordenamiento total del conjunto.

Programación II

Ordenación Rápida (Quicksort)

Programación II

Ordenación Rápida (Quicksort)

Programación II

Ordenación Rápida (Quicksort)

• Ejemplo:

Programación II

Ordenación Rápida (Quicksort)

• Ejemplo:

(Partition)

Programación II

Ordenación Rápida (Quicksort)

• La estimación de la complejidad del

algoritmo es O(n log n). El mejor escenario se da cuando la función Findpivot divide

el conjunto en dos partes de igual tamaño.

• Un peor escenario se tiene cuando los

valores del pivote se seleccionan

aleatoriamente (caso inusual). De ser así el

algoritmo es O(n2).