Ordenacion interna y externa

Parte II: Estructuras de Datos y
Algoritmos
UNIVERSIDAD DE CANTABRIA

1. Introducción al análisis y diseño de algoritmos. 2. Tipos abstractos de datos. 3. Métodos de ordenación.

GRUPO DE COMPUTADORES Y TIEMPO REAL
4

© Javier Gutiérrez, Michael González
24/nov/08

1

FACULTAD DE CIENCIAS

Notas:
UNIVERSIDAD DE CANTABRIA

3. Métodos de ordenación. • El modelo de ordenacióninterna. • Esquemas simples de ordenación. • Ordenación Rápida. • Ordenación por Cajas. • Ordenación por Base.

GRUPO DE COMPUTADORES Y TIEMPO REAL FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González
24/nov/08

2

3.1. El modelo de ordenación interna.

UNIVERSIDAD DE CANTABRIA

Los procesos de ordenación pueden ser: • internos: para ordenar datos en la memoria del computador •externos: para ordenar datos que residen en memoria secundaria (ficheros) Los objetos a ser ordenados son de cualquier tipo, aunque deben tener definida la operación de comparación estándar (r; end loop; k:=l; end Particion;
GRUPO DE COMPUTADORES Y TIEMPO REAL FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González
24/nov/08

10

Implementación de “Quicksort” (cont.)
procedureQuicksort(i,j : in Indice; A : in out Tipo_elementos) is Pos_Pivote,k : Indice; begin Pos_Pivote:=Encuentra_Pivote(i,j,A); if Pos_Pivote /= 0 then Particion(i,j,A(Pos_Pivote),A,k); Quicksort(i,k-1,A); Quicksort(k,j,A); end if; end Quicksort; begin -- Ordenacion_Rapida Quicksort(1,N,A); end Ordenacion_Rapida;

UNIVERSIDAD DE CANTABRIA

GRUPO DE COMPUTADORES Y TIEMPO REAL FACULTAD DE CIENCIAS

© JavierGutiérrez, Michael González
24/nov/08

11

Notas:
UNIVERSIDAD DE CANTABRIA

Los tiempos de ejecución de este algoritmo son de O(n⋅log n) en el caso medio y de O(n2) en el peor caso. Efectivamente, los tiempos de ejecución de peor caso para encuentra_pivote y partición son de tipo O(j-i+1). En el peor caso el número de niveles de recursión es n (caso en el que el pivote divide la lista endos grupos uno de ellos de longitud 1) y, por tanto, el tiempo de peor caso es O(n2). En cambio en el caso medio, el número de niveles de recursión es proporcional a log n, por lo que el tiempo de ejecución medio es O(n⋅log n). Existen otros algoritmos que presentan tiempos de ejecución medios y de peor caso del orden de O(n⋅log n). Sin embargo el tiempo de ejecución medio del algoritmo 'quicksort'es inferior, por un factor constante, al de estos métodos. Existen técnicas para mejorar el tiempo de ejecución de este algoritmo, basadas en realizar una mejor elección del pivote. Por ejemplo, se pueden tomar tres elementos del array al azar y tomar como pivote el de valor intermedio.

GRUPO DE COMPUTADORES Y TIEMPO REAL FACULTAD DE CIENCIAS

© Javier Gutiérrez, Michael González
24/nov/0812

3.4. Ordenación por cajas

UNIVERSIDAD DE CANTABRIA

La ordenación por cajas o “bin sorting” sirve para ordenar conjuntos de elementos en base a una función llave discreta: • llave(elemento) = valor discreto • los elementos se ordenan según su llave Para cada posible valor de la llave se crea una “caja” donde depositar elementos:
Llave 1 Llave 2 ... Llave n
GRUPO DE COMPUTADORES YTIEMPO REAL FACULTAD DE CIENCIAS

a11 a21

a12

a13

a14

an1

an2
13

© Javier Gutiérrez, Michael González
24/nov/08

Notas:
UNIVERSIDAD DE CANTABRIA

Para algunos tipos particulares de datos a ordenar es posible utilizar algoritmos de ordenación con tiempos de ejecución de tipo O(n). Tal es el caso del método de ordenación por 'cajas', que se aplica a elementos para los queexiste definida una función llave que sirve para ordenar los elementos, y cuyos valores sólo pueden presentar un conjunto discreto de valores, como por ejemplo números enteros comprendidos en un rango limitado. Si suponemos que el tipo_llave = 1..n, y queremos ordenar un conjunto de n registros cuyos valores llave no están repetidos, puede utilizarse un array B(1..n) de 'cajas', con el siguiente...