Sellshort

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

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

1

Introducción
Supongamos un subconjunto de nelementos X = {e1,…,en} de un conjunto referencial Y, X ⊆Y. Dentro de Y se define una relación de orden total ≤ (con las propiedades reflexiva, simétrica y transitiva). El objetivo de la ordenación esencontrar una secuencia de los elementos de X 〈eσ(1),…,eσ(n)〉 tal que se verifique: eσ(1) ≤ … ≤ eσ(n)

2

Introducción
Observaciones Los datos pueden ser simples o complejos. El orden se establece deacuerdo al campo clave. clave. Los conjuntos de datos pueden tener duplicados. Si se mantiene el orden relativo de los datos con clave repetida en el conjunto de datos original, el algoritmo se diceque es estable. estable.
3

Introducción
Tipos de algoritmos de ordenación Algoritmos de ordenación interna: En memoria principal (acceso aleatorio) Algoritmos de ordenación externa: En memoriasecundaria (restricciones de acceso).

4

Aplicaciones
Aplicaciones evidentes: evidentes:
Mostrar los ficheros de un directorio. directorio. Mostrar un listado ordenado del contenido de una basede datos (p.ej. listado alfabético). p.ej. alfabético). Ordenar los resultados de una búsqueda en Internet (p.ej. (p.ej. Google PageRank). PageRank).

Problemas que resultan más sencillos de resolvercon los datos ordenados: ordenados:
Realizar una búsqueda (p.ej. búsqueda binaria). p.ej. binaria). Encontrar la mediana. mediana. Encontrar el par más cercano. cercano. Identificar “outliers” /anomalías. anomalías. Detectar duplicados. duplicados.

5

Aplicaciones
Otras aplicaciones (puede que no tan evidentes) : evidentes)
Compresión de datos. datos. Informática gráfica. gráfica....