PDF de programación - Algoritmos de ordenación - Análisis y Diseño de Algoritmos

Algoritmos de ordenación
Algoritmos de ordenación
Análisis y Diseño de Algoritmos
Análisis y Diseño de Algoritmos

Algoritmos de ordenación
Algoritmos de ordenación

 Algoritmos básicos:

Algoritmos básicos: ΘΘ(n(n22))
 Ordenación por inserción
Ordenación por inserción
Ordenación por selección
 Ordenación por selección
 Ordenación por intercambio directo (burbuja)
Ordenación por intercambio directo (burbuja)
 Algoritmos más eficientes
 Algoritmos más eficientes
Algoritmos más eficientes
Algoritmos más eficientes
 Mergesort
Mergesort
 Quicksort
Quicksort
 Heapsort
Heapsort
 Shellsort
Shellsort
 Algoritmos para casos especiales
Algoritmos para casos especiales
Binsort (ordenación por urnas)
(ordenación por urnas)
 Binsort
 ……

11

Introducción
Introducción

 Supongamos un subconjunto de n elementos
Supongamos un subconjunto de n elementos
,…,enn} de un conjunto referencial Y, X
X = {e
X = {e11,…,e

} de un conjunto referencial Y, X ⊆⊆Y. Y.

 Dentro de Y se define una relación de orden total ≤
 Dentro de Y se define una relación de orden total ≤
Dentro de Y se define una relación de orden total ≤
Dentro de Y se define una relación de orden total ≤
(con las propiedades reflexiva, simétrica y transitiva).
(con las propiedades reflexiva, simétrica y transitiva).

 El objetivo de la ordenación es encontrar una
El objetivo de la ordenación es encontrar una
,…,eσσ(n)(n)〉〉
secuencia de los elementos de X 〈〈eeσσ(1)(1),…,e
secuencia de los elementos de X
tal que se verifique: e
tal que se verifique: eσσ(1)

(1) ≤ ≤ … … ≤≤ eeσσ(n)(n)

22

Introducción
Introducción

Observaciones
Observaciones

 Los datos pueden ser simples o complejos.
Los datos pueden ser simples o complejos.

 El orden se establece de acuerdo al campo
 El orden se establece de acuerdo al campo

El orden se establece de acuerdo al campo clave
El orden se establece de acuerdo al campo clave
clave..
clave..

 Los conjuntos de datos pueden tener duplicados.
Los conjuntos de datos pueden tener duplicados.

 Si se mantiene el orden relativo de los datos con clave
Si se mantiene el orden relativo de los datos con clave
repetida en el conjunto de datos original, el algoritmo se
repetida en el conjunto de datos original, el algoritmo se
dice que es estable
dice que es
estable..

33

Introducción
Introducción

Tipos de algoritmos de ordenación
Tipos de algoritmos de ordenación

 Algoritmos de ordenación interna:
Algoritmos de ordenación interna:
En memoria principal (acceso aleatorio)
En memoria principal (acceso aleatorio)

 Algoritmos de ordenación externa:
Algoritmos de ordenación externa:
En memoria secundaria (restricciones de acceso).
En memoria secundaria (restricciones de acceso).

Aplicaciones
Aplicaciones

los ficheros

de un directorio
directorio..

evidentes::
Aplicaciones
Aplicaciones evidentes
ficheros de un
Mostrar los
 Mostrar
 Mostrar
Mostrar un un listado
listado ordenado
listado alfabético
datos
datos ((p.ejp.ej. . listado
Ordenar los
 Ordenar
resultados de de unauna búsqueda
Google
Google
Google PageRank
Google PageRank

ordenado del del contenido
alfabético).).

los resultados
PageRank).).
PageRank).).

contenido de de unauna base de
base de

búsqueda en Internet (

en Internet (p.ejp.ej. .

sencillos de resolver con
de resolver con

resultan másmás sencillos

Problemas
Problemas queque resultan
los
los datos
 Realizar
 Encontrar
 Encontrar
 Identificar
 Detectar

datos ordenados
ordenados::
Realizar unauna búsqueda
búsqueda ((p.ejp.ej. . búsqueda
mediana. .
Encontrar la la mediana
Encontrar el par
Identificar “outliers” /
Detectar duplicados
duplicados..

cercano..
el par másmás cercano
“outliers” / anomalías
anomalías..

búsqueda binaria

binaria).).

44

55

puede queque no tan

no tan evidentes

evidentes) :) :

Aplicaciones
Aplicaciones

aplicaciones ((puede

OtrasOtras aplicaciones
Compresión de de datos
datos..
 Compresión
Informática gráfica
gráfica..
 Informática
Planificación de de tareas
tareas..
 Planificación
Balanceado de de carga
 Balanceado
carga en un
Biología computacional
Biología
Biología computacional
 Biología
computacional..
computacional..
Simulación ((p.ejp.ej. . sistemas
 Simulación
Árbol generador
 Árbol
generador minimal
 Gestión
Gestión de la
 Recomendaciones
Recomendaciones de de libros
 ……

de la cadena

en un ordenador

ordenador paralelo
paralelo..

partículas).).

sistemas de de partículas
minimal [MST: Minimum Spanning Tree]
[MST: Minimum Spanning Tree]
suministro [SCM: Supply Chain Management]
[SCM: Supply Chain Management]

cadena de de suministro

libros en Amazon.com
en Amazon.com

66

Ordenación por selección
Ordenación por selección

En cada iteración, se selecciona el menor elemento del
En cada iteración, se selecciona el menor elemento del
subvector
subvector no ordenado y se intercambia con el primer
no ordenado y se intercambia con el primer
elemento de este subvector
elemento de este
subvector::

77

Ordenación por selección
Ordenación por selección

selectionSort (double v[])
(double v[])

void
void selectionSort
{{

double
double tmptmp;;
intint ii, j,
intint N = N = v.length

, j, pos_min
v.length;;

pos_min;;

for (ii=0; =0; ii<N<N--1; 1; ii++) {
for (
++) {

// Menor elemento del vector v[i..N
// Menor elemento del vector v[i..N--1]1]
// Menor elemento del vector v[i..N
// Menor elemento del vector v[i..N--1]1]
pos_min
pos_min = = ii;;

for (j=i+1; j<N; j++)
for (j=i+1; j<N; j++)

if (v[j]<v[
if (v[j]<v[pos_min

pos_min])])

pos_min
pos_min = j;= j;

// Coloca el mínimo en v[i]
// Coloca el mínimo en v[i]

];
tmptmp = v[= v[ii];
v[v[ii] = v[
pos_min];];
v[v[pos_min

pos_min] = ] = tmptmp;;

] = v[pos_min

}}

}}

Ordenación por selección
Ordenación por selección

selectionSort (double v[])
(double v[])

void
void selectionSort
{{

double
double tmptmp;;
intint ii, j,
intint N = N = v.length

, j, pos_min
v.length;;

pos_min;;

for (ii=0; =0; ii<N<N--1; 1; ii++) {
for (
++) {

// Menor elemento del vector v[i..N
// Menor elemento del vector v[i..N--1]1]
// Menor elemento del vector v[i..N
// Menor elemento del vector v[i..N--1]1]
pos_min
pos_min = = ii;;

for (j=i+1; j<N; j++)
for (j=i+1; j<N; j++)

if (v[j]<v[
if (v[j]<v[pos_min

pos_min])])

pos_min
pos_min = j;= j;

// Coloca el mínimo en v[i]
// Coloca el mínimo en v[i]

];
tmptmp = v[= v[ii];
v[v[ii] = v[
pos_min];];
v[v[pos_min

pos_min] = ] = tmptmp;;

] = v[pos_min

}}

}}

88

99

Ordenación por inserción
Ordenación por inserción

En cada iteración, se inserta un elemento del
En cada iteración, se inserta un elemento del
subvector
subvector no ordenado en la posición correcta dentro
no ordenado en la posición correcta dentro
del del subvector

subvector ordenado.
ordenado.

Ordenación por inserción
Ordenación por inserción

En cada iteración, se inserta un elemento del
En cada iteración, se inserta un elemento del
subvector
subvector no ordenado en la posición correcta dentro
no ordenado en la posición correcta dentro
del del subvector

subvector ordenado.
ordenado.

1010

1111

Ordenación por inserción
Ordenación por inserción

insertionSort (double v[])
(double v[])

void
void insertionSort
{{

double
double tmptmp;;
intint ii, j;, j;
intint N = N = v.length

v.length;;

for (ii=1; =1; ii<N; <N; ii++) {
for (
++) {

tmptmp = v[= v[ii];];

for (j=
for (j=ii; (j>0) && (

; (j>0) && (tmptmp<v[j<v[j--1]); j

1]); j----))

v[j] = v[j
v[j] = v[j--1];1];

v[j] =
v[j] = tmptmp;;

}}

}}

Método de la burbuja
Método de la burbuja

Ordenación por intercambio directo
Ordenación por intercambio directo
IDEA: Los elementos más ligeros ascienden
IDEA: Los elementos más ligeros ascienden

1212

1313

Método de la burbuja
Método de la burbuja

bubbleSort (double v[])
(double v[])

void
void bubbleSort
{{

double
double tmptmp;;
intint i,ji,j;;
intint N = N = v.length

v.length;;

forfor (i = 0; i < N

(i = 0; i < N –– 1; i++)
1; i++)
forfor (j = N

1; j > i; j----))

(j = N –– 1; j > i; j
ifif (v[j] < v[j
(v[j] < v[j--1]) {
ifif (v[j] < v[j
(v[j] < v[j--1]) {
1]) {
1]) {
tmptmp = v= v[j];[j];
v[j] = v[j
v[j] = v[j--1];1];
v[jv[j--1] =

1] = tmptmp;;

}}

}}

1414

Método de la burbuja
Método de la burbuja

Mejora: Usar un centinela y terminar cuando en una
Mejora: Usar un centinela y terminar cuando en una
iteración del bucle interno no se produzcan intercambios.
iteración del bucle interno no se produzcan intercambios.

bubbleSort((double

double[] v)
[] v)

voidvoid bubbleSort
{{

swapped == true;
true;

boolean
boolean swapped
intint i, j = 0;
i, j = 0;
double
double tmptmp;;

while
while ((swapped

swapped) {) {

v.length -- j; i++)
j; i++)

swapped
swapped == false;
false;
j++j++;;
forfor (i = 0; i <

(i = 0; i < v.length
(v[i] > v[i + 1]) {
ifif (v[i] > v[i + 1]) {
tmptmp = v[i];
= v[i];
v[i] = v[i + 1];
v[i] = v[i + 1];
v[i + 1] = tmptmp;;
v[i + 1] =
swapped
swapped == true;
true;

}}

}}

}}

1515

Análisis de eficiencia
Análisis de eficiencia

Ordenación por selección
Ordenación por selección

NN22/2 comparaciones y N intercambios.
/2 comparaciones y N intercambios.

Ordenación por inserción
Ordenación por inserción

NN22/4 comparaciones y N
/4 comparaciones y N22/8 intercambios en media
/4 comparaciones y N22/8 intercambios en media
NN22/4 comparaciones y N
/8 intercambios en media
/8 intercambios en media
El doble en el peor caso.
 El doble en el peor caso.
 Casi lineal para conjuntos casi ordenados.
Casi lineal para conjuntos casi ordenados.

/2 comparaciones y N22/2 intercambios en media
/2 intercambios en media

Ordenación por burbuja
Ordenación por burbuja
NN22/2 comparaciones y N
(y en el peor caso).
(y en el peor caso).
 Lineal en su versión mejorada si el vector está ordenado.
Lineal en su versión mejorada si el vector está ordenado.

Mergesort
Mergesort

Algoritmo de ordenación “divide y vencerás”:
Algoritmo