Métodos de Ordenación
Notas de Clase

Prof. Juan Andrés Colmenares, M.Sc.
Instituto de Cálculo Aplicado
Facultad de Ingeniería
Universidad del Zulia


Índice General

Métodos de Ordenación Elementales

Los métodos de ordenación elementales proporcionan:

Típicamente, los métodos de ordenación elementales tienen peor desempeño que los sofisticados, pero existen muchas aplicaciones en las que es mejor utilizar un método de ordenación elemental. Por ejemplo, cuando el algoritmo se utiliza pocas veces y/o se ordenan pocos elementos.

Como regla general se tiene que los métodos elementales necesitan cerca de $ N^2$ pasos para ordenar $ N$ elementos organizados al azar.

En general, no se recomienda su uso para ordenar:

Por su parte, métodos mas avanzados pueden lograr desempeños de orden $ NlogN$, $ N^{\frac{3}{2}}$, $ N$. Mas aún, se puede demostrar que ningún método de ordenación puede utilizar menos de $ NlogN$ comparaciones entre claves cuando éstas están organizadas al azar.

Terminología General

En el contexto de los métodos de ordenación, cada elemento de dato tiene su clave, y los métodos de ordenación trabajan ordenando los elementos de dato según sus claves. Por lo regular, los métodos comparan las claves e intercambian los elementos de dato. En lugar de desplazar físicamente los elementos de datos, con frecuencia, sólo se intercambian índices, punteros o referencias. Esto se denomina ordenación indirecta.

Un método de ordenación que trabaja sobre un conjunto de datos que se encuentra en memoria (e.g., un arreglo, una lista) se dice que es un método de ordenación interna. Por el contrario, si el conjunto de datos almacenados en archivos no pueden ser cargado en memoria (por ejemplo, por razones de tamaño) y el método de ordenación opera sobre los archivos, se dice que es de ordenación externa. Evidentemente, en la ordenación interna se accede a los elementos de dato más fácilmente, mientras que en la ordenación externa se accede a los elementos de dato de forma secuencial o al menos en grades bloques.

Los métodos de ordenación se pueden clasificar de acuerdo a sus requerimientos de memoria. Los métodos in situ son aquellos que requieren ninguna o muy poca memoria extra. En el otro extremo, existen métodos que requieren mucha memoria extra.

Una característica que puede ser importante es la estabilidad del método de ordenación. Un algoritmo de ordenación es estable si elementos de dato con la misma clave conservan su orden relativo luego de su aplicación. Típicamente, los métodos elementales son estables mientras que la mayoría de los algoritmos sofisticados no lo son.

Entre los métodos de ordenación elementales están Selección e Inserción, los cuales son descritos a continuación.

Método de Ordenación por Selección

Supongamos que tenemos un arreglo con los datos, entonces el procedimiento es como sigue:

  1. se sitúa en el primer elemento (i=0).
  2. se busca el elemento más pequeño de arreglo (desde i hasta el final).
  3. se intercambia el elemento más pequeño con el que está en la posición i.
  4. se incrementa i (i++).

Nótese que se gasta la mayor parte del tiempo en intentar en encontrar el elemento mínimo.

A continuación se presenta una implementación en Java del método de ordenación por selección:

/**
 * Clase que implementa métodos de ordenación elementales.
 */
public class Sorting 
{
  static public void selectionSort(Comparable array[]) 
  {
    // No se incluye validación de parámetro de entrada.
    int min;
    for (int i = 0; i < array.length; i++)
    {
      min = i;
      for (int j = i + 1; j < array.length; j++) 
      {
        if (array[j].compareTo(array[min]) < 0) 
        {
          min = j;
        }				
      }
			
      Sort.swap(array, min, i);
     }
  }

  private static void swap(Comparable[] array, int i, int j) 
  {
    Comparable tmp = array[i];
    array[i] = array[j];
    array[j] = tmp;
  }
}

El método de ordenación por selección:

  1. está basado en el enfoque de fuerza bruta
  2. funciona bien con archivos pequeños
  3. cada elemento se mueve sólo una vez

Método de Ordenación por Inserción

Considere que los elementos están uno tras otro, el método consiste en insertar cada elemento en el lugar apropiado entre los elementos que ya han sido considerado (manteniéndolos ordenados). Es similar a la forma en que se ordena un juego de cartas.

Por ejemplo:

E J E M P L O A O R D E N A R
E J
E J E
E E J M
E E J M P
E E J M P L
E E J L M P ...

A continuación se muestra una implementación en Java del método de ordenación por inserción.

static public void insertionSort(Comparable array[]) 
  {
    // No se incluye validación de parámetro de entrada.
    int min;
    for (int i = 1; i < array.length; i++)
    {
      Comparable tmp = array[i];
      int j;
      for (j = i; j > 0 && tmp.compareTo(array[j-1]) < 0; j--) 
      {
        array[j] = array[j-1];
      }

      array[j] = tmp;
    }
}

Características de Rendimiento de los Métodos de Ordenación Elementales

Método de Ordenación de Shell (Shell Sort)

Fue uno de los primeros métodos en romper la barrera del tiempo cuadrático. Ya sabemos que cualquier algoritmo de ordenación que intercambie elemento adyacentes tendrá un tiempo promedio de ejecución de orden cuadrático.

¿Qué podemos para tratar de mejorar eso? Simplemente hacer comparaciones e intercambios entre elementos no adyacentes (es decir, más apartados). En consecuencia, Shell Sort compara elementos que están distantes, y esta distancia disminuye en la medida que el algoritmo progresa hasta la última fase en la cual se comparan elementos adyacentes.

Shell Sort utiliza secuencias de incrementos del tipo: $ h_{t}, h_{t-1},\dots, h_{2}, h_{1}$ donde $ h_{1}=1$ y $ h_{k} < h_{k+1}$. Después de una fase y habiendo usando un incremento $ h_{k}$, para cada elemento i se cumple que $ a[i]< a[i+h_{k}]$, es decir que todos los elementos espaciados $ h_{k}$ están ordenados. En este caso se dice que tenemos una archivo $ h_{k}$-ordenado. En cada fase se realizan ordenaciones por inserción en arreglos independientes.

A continuación se presenta un ejemplo de la ejecución de Shell Sort con la secuencia {5, 3, 1}:

Original 81 94 11 96 12 35 17 95 28 58 41 75 15
5-ordenado 35 17 11 28 12 41 75 15 96 58 81 96 95
3-ordenado 28 12 11 35 15 41 58 17 94 75 81 96 95
1-ordenado 11 12 15 17 28 35 41 58 75 81 94 95 96

Propiedad1: un archivo $ h_{k}$-ordenado que es luego $ h_{k-1}$-ordenado, mantiene su condición de $ h_{k}$-ordenado.

Nótese que el desempeño del algoritmo depende de la secuencia seleccionada y que unas secuencias son mejores que otras. Algunas de las secuencias más utilizadas son las siguientes:

Se ha comprobado que la cota $ \Theta(N^{\frac{3}{2}})$ aplica a muchas secuencias.

A continuación se presenta una implementación en Java del método de ordenación de Shell que utiliza la secuencia de Sedgewick.

static public void shellSort(Comparable array[]) 
{
    // No se incluye validación de parámetro de entrada.

    Comparable tmp;
    int h = 0;
		
    // generate the sequence
    for (h = 0; h < array.length; h=3*h+1); 

    for (; h>0; h/=3)
    {
        for (int i = h; i < array.length; i++) 
        {
            tmp =array[i]; 
            int j = i;
            while (j>=h  && tmp.compareTo(array[j-h]) < 0)
            {
                array[j] = array[j-h];
                j-=h; 
            }
            array[j] = tmp;
        }
    }
}

Ordenación por Fusión (MergeSort)

Es un algoritmo recursivo (de tipo divide y vencerás) cuyo tiempo de ejecución es de $ O(NlnN)$ en el peor caso, y el número de comparaciones usadas es cercana al óptimo.

La operación fundamental sobre la cual se basa este algoritmo es: funsionar 2 arreglos (listas) ordenados(as) en un(a) arreglo (lista) mayor también ordenado(a). Esta operación se puede realizar en un sólo paso por la entrada, si la salida es puesta en su tercer arreglo. Supóngase que tenemos como entrada dos arreglos de elementos ya ordenados (A[N] y B[M]) y como salida el arreglo C[N+M]; adicionalmente tenemos las variables enteras (contadores) a, b y c inicializadas en 0 que servirán para manejar los índices de los arreglos. Dado esto la operación se realiza de la siguiente manera:

  1. El menor de A[a] y B[b] es colocado en C[c] y se incrementan los contadores apropiados.
  2. Cuando se llega al final de alguno de los arreglos de entrada el resto del otro arreglo es copiada a C.

La Figura 1 ejemplifica la operación básica de fusionar dos arreglos ordenados.

Figura 1: Ilustración de la operación fundamental del algoritmo MergeSort.
\includegraphics[scale=0.6]{images/merge-operation}

Mezclar dos arreglos (listas) ordenados(as) en otro(a) ordenado(a) es un proceso lineal: cuando más se realizan $ N-1$ comparaciones, donde $ N$ es el numero total de elementos.

Descripción

Los pasos son lo siguientes:

  1. Si N=1 sólo existe un elemento a ordenar y ya se tiene la solución.
  2. En caso contrario, aplique recursivamente la operación mergeSort(...) sobre la primera y segunda mitad del arreglo
  3. Finalmente, esto resulta en dos mitades ordenadas que pueden funsionarse utilizando la operación fundamental descrita anteriormente.

Detalle de implementación: cuando el arreglo a ordenar es pequeño (e.g., 20 elementos o menos) dentro de una llamada recursiva, en lugar de continuar recursivamente se utiliza el método de ordenación por inserción.


Desempeño

Para realizar el análisis del algoritmo empleamos la siguiente secuencia: $ T(1)=1 $ y $ T(N)=2 \cdot T(\frac{N}{2}) + N$, donde $ N$ es el número de elementos a ordenar. En la parte derecha de la igualdad de la segunda ecuación, el primer término de corresponde a las dos llamadas recursivas del algoritmo, mientras el segundo corresponde a la mezcla que es lineal.

Sin perder generalidad, supongamos que $ N=2^{n}$, entonces:


$\displaystyle T(2^{n})$ $\displaystyle =$ $\displaystyle 2 \cdot T(2^{n}) + 2^{n}$  
$\displaystyle \dfrac{T(2^{n})}{2^{n}}$ $\displaystyle =$ $\displaystyle \dfrac{T(2^{n-1})}{2^{n-1}} + 1$  
  $\displaystyle =$ $\displaystyle \dfrac{T(2^{n-2})}{2^{n-2}} + 1 + 1$  
  $\displaystyle \cdots$    
$\displaystyle \dfrac{T(2^{n})}{2^{n}}$ $\displaystyle =$ $\displaystyle n$  
$\displaystyle T(2^{n})$ $\displaystyle =$ $\displaystyle 2^{n} \cdot n$  
$\displaystyle T(N)$ $\displaystyle =$ $\displaystyle Nlog(N)$  

Características

El algoritmo de ordenación por fusión:

  1. necesita alrededor de $ NLog(N)$ comparaciones para ordenar un archivo de $ N$ elementos.
  2. utiliza un espacio extra proporcional a $ N$ (no es in situ).
  3. es estable.
  4. es insensible al orden inicial de la entrada.

QuickSort

Es probablemente el más utilizado de los algoritmos de ordenación. Fue inventado por C.A.R. Hoare2 en 1960 y desde entonces se han propuesto mejoras.

Es muy popular porque es relativamente fácil de implementar, ofrece buenos resultados generales, en muchos casos consume menos recursos otros método de ordenación, y está bien estudiado (ha sido expuesto a un minucioso análisis matemático que ha sido corroborado con amplia experiencia práctica).

Entre sus ventajas están:

Y sus desventajas:

Descripción

Es un algoritmo recursivo (de tipo divide y vencerás). Es decir, divide el arreglo en dos partes y las ordena independientemente. A continuación se presenta el algoritmo QuickSort en pseudocódigo.

void quicksort(int a[], int izq, int der)
{
   int i;
   if (der>izq)
   {
       i= divide(a, izq, der);
       quicksort(a, izq, i-1);
       quicksort(a, i+1, der):
   }
}

Nótese que la llamada quicksort(a, 0, N-1) ordena el arreglo de N elementos en su totalidad.

Procedimiento de Partición

El procedimiento de partición (divide) es una parte escencial del algoritmo. Este procedimiento debe reordenar el arreglo de forma tal que:

  1. El elemento $ a[i]$ queda en su lugar definitivo dentro del arreglo (pivote).
  2. Ninguno de los elementos de $ a[izq], \cdots, a[i-1]$ son mayores que $ a[i]$.
  3. Ninguno de los elementos de $ a[i+1], \cdots, a[der]$ son menores que $ a[i]$.

La Figura 2 ilustra la operación de partición del algoritmo QuickSort.

Figura 2: Ilustración de la operación de partición del algoritmo QuickSort.
\includegraphics[scale=0.7]{images/quicksort-particion}

Nótese que para realizar la partición es necesario seleccionar un elemento de pivote. Seguramente lo primero que nos viene a la mente es seleccionar el primer o último elemento del arreglo ya que podemos considerar que los elementos vienen ordenados al azar. Lamentablemente esto resulta en una partición pobre si el arreglo está ordenado o en orden inverso, ya que todos los elementos se van a una de las dos participaciones, y esto ocurre consistentemente en cada llamada recursiva. La consecuencia práctica de esto es: si el arreglo ya está ordenado, entonces QuickSort toma un tiempo $ N^{2}$ para no hacer nada. Como conclusión, tomar el primer o último elemento del arreglo como pivote es una idea que debe ser descartada de una vez.

También se nos puede ocurrir seleccionar aleatoriamente un elemento del arreglo. Ciertamente está alternativa ofrece mayor grado de seguridad pero es costosa y no mejora el tiempo promedio de ejecución del algoritmo.

Realmente el pivote se selecciona de la siguiente manera: se toman los elementos $ a[izq]$, $ a[der]$ y $ a[(der+izq)/2]$, se ordenan y se toma el del medio (Figura 3). A este método se le conoce como la Mediana de Tres. Esto elimina el peor caso ya que las particiones son de igual tamaño y se ha determinado que reduce el tiempo de ejecución en un 5%.

Figura 3: Ilustración de selección de pivote por la mediana de 3.
Image quicksort-median3

A continuación se presenta una implementación en Java de la selección del pivote por la mediana de 3.

private static Comparable median3(Comparable a[], int left, int right)
{
    int center = (left+right)/2;

    if (a[center].compareTo(a[left]) < 0)
    {
        swap (a, left, center);
    }

    if(a[right].compareTo(a[left])<0)
    {
        swap(a, left, right);
    }

    if(a[right].compareTo (a[center])<0)
    {
        swap(a, center, right);
    }
       
    swap(a, center, right-1);
    return a[right-1];
}

Finalmente, la estrategia de partición (Figura 4) es como sigue:

  1. Se determina el pivote (por la mediana de 3) y se intercambia con el penúltimo elemento.
  2. Se inicializan las variables $ i=0$ y $ j=N-2$. Nótese que $ j$ apunta al pivote (penúltimo elemento).
  3. Mientras $ i$ esté a la izquierda de $ j$ (es decir que $ i<j$), $ i$ se mueve a la derecha ($ i++$) saltando todos los elementos menores que el pivote. Si se consigue uno mayor o igual se detiene.
  4. De forma similar, $ j$ se mueve hacia la izquierda ($ j-$) de saltando todos los elementos mayores pivote. Si se consigue uno menor o igual se detiene.
  5. Cuando $ i$ y $ j$ están parados y se cumple que $ i<j$, entonces los elementos apuntados por $ i$ y $ j$ son intercambiados. El efecto de esto es poner el elemento grande a la derecha del pivote y el elemento chico a su izquierda.
  6. Se repite el proceso hasta que $ i$ y $ j$ se crucen.
  7. Cuando $ i$ y $ j$ están parados y se cruzan, no se realiza ningún intercambio.
  8. Finalmente, se intercambia el pivote (penúltimo elemento) con el apuntado por $ i$.

Figura 4: Ilustración de la estrategia de particición del algoritmo QuickSort.
Image quicksort

Nótese que los apuntadores se detienen cuando se consiguen elementos iguales al pivote. Esto se hace porque contribuye a que las particiones sean más parejas de forma tal que el desempeño del algoritmo tienda a ser $ NLog(N)$.

Detalle de implementación: cuando el arreglo a ordenar es pequeño (e.g., 20 elementos o menos) dentro de una llamada recursiva, en lugar de continuar recursivamente se utiliza el método de ordenación por inserción. Esto mejora en aproximadamente un 15% el tiempo de ejecución del algoritmo.

Desempeño

En promedio uno esperaría que cada partición divida el arreglo por la mitad, lo cual conduce a la siguiente función de recurrencia: $ T(1)=1 $ y $ T(N)=2 \cdot T(\frac{N}{2}) + N$, donde $ N$ es el número de elementos a ordenar. Haciendo un análisis similar al de la Sección 3.2, obtenemos que en promedio el tiempo de ejecución del algoritmo QuickSort es $ Nlog(N)$.

Colas de Prioridad (Motículos)

En muchas aplicaciones, se requiere extraer y procesar el mayor elemento de un conjunto, agregar otros elementos al conjunto, y posteriormente, extraer y procesar el mayor elemento del conjunto en ese momento. Para resolver este problema se emplea una estructura de datos denominada Cola de Prioridad.

Algunos ejemplos de uso son:

  1. Planificación de tareas en sistemas operativos (las tareas se planifican según su prioridad)
  2. Simulación basada en eventos (las claves se establecen de acuerdo a la cronología de los sucesos que deben procesarse)
  3. Cálculo numérico (las claves corresponden a magnitudes de errores de cálculo)

Cola de Prioridad como Tipo de Dato Abstracto

Una cola de prioridad es una estructura de datos que incluye un registro con claves numéricas y que soporta las siguientes operaciones básicas:

  1. Insertar un elemento
  2. Extraer el elemento de mayor prioridad
  3. Construir una cola de prioridad a partir de N elementos (provenientes de un arreglo o lista).

Adicionalmente, puede se capaz de cambiar la prioridad de un elemento, eliminar un elemento determinado (no necesariamente el de mayor prioridad) y unir dos colas de prioridad, entre otras operaciones.

Alternativas de Implementación

Como alternativas iniciales están:

Con una estructura de datos denominada montículo se puede lograr implementaciones eficientes de las operaciones más importantes de una cola de prioridad. Entre sus ventajas es no requiere enlaces y las operaciones se realizan en un tiempo $ O(log(N))$, en el pero caso.

Montículo Binario (Binary Heap)

Un montículo es un árbol binario completo (completamente lleno excepto el último nivel) que satisface las siguientes condiciones (Condiciones de Montículo Binario):

Un árbol binario completo es sumamente regular3. Además, presenta la ventaja de que puede ser implementado mendiante un arreglo sin necesidad de enlaces. Esto es: para cualquier elemento $ i$, el hijo izquierdo está en la posición $ 2i$, el hijo derecho en la posición $ 2i+1$ y el padre en la posición $ \lfloor i/2 \rfloor$. (Figura 5)

Figura 5: Ilustración de Montículo Binario.
\includegraphics[scale=0.7]{images/heap}

Esto favorece la implementación de operaciones simples y rápidas, aunque requiere la estimación de la capacidad máxima del arreglo, y su redimensionamiento dinámico (e.g., uso de la clase ArrayList).

Algoritmos sobre Montículos

Los algoritmos básicos que operan sobre montículos tienen las siguientes características:

Por ejemplo, la operación de insertar un nuevo elemento involucra:

  1. agregar el elemento al final del arreglo, lo cual potencialmente viola la condición de montículo.
  2. hacer que el elemento recién agregado suba el montículo de forma tal que ocupe la posición que le corresponde y en consecuencia, restaurar la condición de montículo.

Por otra parte,la operación de extraer el elemento de mayor prioridad consiste en:

  1. asignar el primer elemento del arreglo a una variable temporal (item = a[1]).
  2. asignar el último elemento del arreglo a la primera posición y decrementar el tamaño del arreglo (a[1]=a[N-]), lo cual potencialmente viola la condición de montículo.
  3. hacer que el elemento recién colocado en la primera posición del arreglo baje el montículo de forma tal que ocupe la posición que le corresponde y en consecuencia, restaurar la condición de montículo.
  4. retornar el elemento asignado a la variable temporal item.

Ordenación por Montículo

Es un métodos elegante y eficaz basado en las operaciones básicas de montículos. No utiliza memoria extra y garantiza ordenar N elementos en aproximadamente $ Nlog(N)$. Su bucle interno es más largo que el de QuickSort. y es en promedio 2 veces más lento.

La idea central del algoritmo es construir un montículo que contenga todo los elementos a ordenar y después suprimirlos hasta dejar vacío el montículo. A continuación se presenta un pseudocódigo que describe esta idea:

public void heapSort(Comparable[] a)
{
    // No se incluye validación de parámetro de entrada.
    int i;
    Heap heap = new Heap(a.length);

    for(i=0; i<a.length; i++) {
        heap.put(a[i]);
    }
    
    for(i=a.legnth-1; i>=0; i--){
      a[i]=heap.pop();
    }
}

Código anterior es sólo para propósitos ilustrativos de la idea central. La implementación real se caracteriza por:

En realidad es mejor construir el montículos retrocediendo a través de el arreglo, e ir creando pequeño submontículos hacia arriba.

Este método considera a cada elemento del arreglo como la raiz de un pequeño submontículo y se aprovecha del hecho de que la operación bajarMonticulo puede aplicarse a esos submontículos. A continuación se presenta el método de ordenación por montículo en pseudocódigo:

public static void heapSort(Comparable a[])
{
    int k;
    
    // Creación del montículo sobre el arreglo original
    for(k=a.length/2; k>=1; k--){
        bajarMonticulo(a, a.length, k); 
    }

    int n = a.length;
    while(n>1){
      swap(a, 1, n);
      bajarMontículo(a, --n, 1);
    }
}

Propiedad 1

La construcción ascendente del montículo es lineal. Por ejemplo, para un montículo de 127 elementos se llama a la operación bajarMonticulo para:
Montículos Elementos Posibles Promociones ($ PProm$)
64 1 0x64
32 3 1x32
16 7 2x16
8 15 3x8
4 31 4x4
2 63 5x2
1 127 6x1

$\displaystyle Total=120<127$

Nótese que la mayoría de los montículos que se procesan son pequeños.

Propiedad 2

La ordenación por montículo utiliza menos de $ 2NLog(N)$ comparaciones para ordenar $ N$ elementos (tiempo de ejecución $ NLog(N)$ inclusive en el peor caso).

Sobre este documento...

Métodos de Ordenación
Notas de Clase

This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.70)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html ordenacion.tex -split 0 -nonavigation

The translation was initiated by Juan Colmenares on 2004-03-25


Notas al pie

...Propiedad1
Si no se cumpliera esta propiedad, el algoritmo fuera de poca utilidad pues una fase posterior dañaría lo que ha hecho una fase previa.
... Hoare2
C.A.R Hoare. Quicksort. Computer Journal. Vol. 5, 1 (1962).
... regular3
Sea $ h$ la altura de un árbol binario lleno, entonces $ 2^{h} \leqslant N \leqslant 2^{h+1}-1$, donde $ N$ es el número de nodos. En consecuencia, $ h=\lfloor log(N)\rfloor$


Juan Colmenares 2004-03-25