12. Métodos de ordenación

Última modificación por Mario Gorga López el 2021/05/11 08:10

Contenidos

Objetivos
Introducción
Clasificación de los algoritmos directos de ordenación
Comparación de algoritmos
Conclusiones
Resumen

Objetivos

Los objetivos de este módulo son los siguientes:

Tener una idea consistente de los diferentes grupos de algoritmos de ordenación en vectores/tablas.
Valorar la complejidad de los diferentes grupos de algoritmos.

Introducción

En el módulo anterior hemos visto que las búsquedas dentro de datos estructurados ordenados son bastante más eficientes que si los datos no están ordenados. En conjuntos de datos que tienen que ser sometidos frecuentemente a búsquedas, el ahorro de computación si se dispone de datos ordenados puede significar un importante aumento en el rendimiento del sistema.

En estos casos será importante generar directamente los datos ordenados, es decir, cuando insertamos un nuevo dato dentro de la estructura de datos, ya lo situamos en la posición que le corresponde según el orden establecido. El dato estructurado nace y se mantiene siempre ordenado y las búsquedas siempre pueden ser eficientes.

Hay varias situaciones en las que esto no es posible:

Los datos son complejos (tuplas) y el ordenamiento de las mismas es diferente según los diferentes campos que a menudo son base de búsquedas.
Disponemos ya de la colección de datos pero no está ordenada.

En estos casos será necesario disponer de mecanismos de ordenación de los datos que permitan reorganizarlos de una manera eficaz.

A lo largo de este módulo incidiremos, sobre todo, en los algoritmos de ordenación de vectores dado que son las estructuras de datos más frecuentes susceptibles de mantener un orden y porque se puede valorar de una manera relativamente simple la complejidad de cada uno de los algoritmos. Todos los métodos se pueden extender a otros tipos de datos, como tablas de tipos simples (aplicación directa) o listas.

En los ejemplos que haremos, los métodos supondrán siempre que queremos aplicar un orden ascendente, las modificaciones de los algoritmos para tratar el orden descendente son triviales.

Además, supondremos siempre que estamos ordenando un vector de tuplas por el valor de su campo entero key. Considera la siguiente definición de tupla:

[Ejemplo 12_01]

Algoritmo
C

type
    tReg = record
        key: integer;
        { ... }
    end record
end type

typedef struct {
int key;
/* ... */
} tReg;

En algunos algoritmos también será necesario intercambiar tuplas, cosa que se hará con la ayuda de una acción swap.

[Ejemplo 12_02]

Algoritmo
C

action swap(inout a: tReg, inout b: tReg)
    var
        auxiliar: tReg;
    end var

    auxiliar := a;
    a := b;
    b := auxiliar;

end action

#include <mem.h>

void swap(tReg *a, tReg *b) {
    tReg auxiliar:
    memcpy(&auxiliar, a, sizeof(tReg));
    memcpy(a, b, sizeof(tReg));
    memcpy(b, &auxiliar, sizeof(tReg));
}

Clasificación de los algoritmos directos de ordenación

Hay varios algoritmos genéricos de ordenamiento en función de la estrategia básica con la que mueven los elementos dentro del vector hasta la localización definitiva que les corresponde según el orden deseado.

Todos los algoritmos que mostraremos son los nombrados directos porque hacen la ordenación dentro del mismo vector original, a diferencia de los indirectos que emplean un vector auxiliar para reordenar los datos y, por tanto, son menos eficientes en cuanto al uso de la memoria.

Ordenación por selección

Los mecanismos de selección suponen que en todo momento el vector que se quiere ordenar está dividido en dos segmentos, una parte ordenada y otra desordenada. El algoritmo es iterativo y en cada iteración seleccionamos un elemento de la parte desordenada y lo pasamos a la ordenada. El estado inicial del algoritmo es que la parte desordenada contiene todos los elementos y la ordenada ninguno, mientras el estado final es que la parte desordenada no contiene ningún elemento y la parte ordenada ya los tiene todos.

En un momento determinado de la aplicación del algoritmo, el estado del vector podría ser:

Figura: la señal roja indica la frontera entre la parte ya ordenada y la que falta ordenar

En lenguaje natural, el algoritmo sería:

Seleccionar de la parte desordenada la tupla con el valor de key más pequeño.
Intercambiar esta tupla con la primera tupla de la parte desordenada.
Repetir los pasos 1 y 2 hasta que sólo quede una tupla en la parte desordenada (que será la de valor de key más grande).

Si se parte del vector de valores de key [44, 55, 12, 42, 94, 18, 06, 67] la evolución desde la situación inicial (iteración 0) hasta la final sería:

Figura: Cuando sólo queda un elemento en la parte por ordenar, ya está ordenado todo el vector

Veamos el algoritmo codificado:

[Ejemplo 12_03]

Algoritmo
C

const
N: integer = 8;
end const

type
tVec: vector[N] of tReg;
end type

action selectionSort(inout v: tVec, in n: integer)

    var
        i, j, min: integer;
    end var

    for i:=1 to n-1 do
        min := i;
        for j:=i+1 to n do
            if v[j].key < v[min].key then
                min := j;
            end if
        end for

        if min ≠ i then
            swap(v[i], v[min]);
        end if
    end for

end action

#define N 8

typedef tReg tVec[N];

void selectionSort(tVec v; int n) {

   int i, j, min;

   for (i=0; i < n-1; i++) {
        min = i;
       for ( j = i+1 ; j < n ; j++) {
           if (v[j].key < v[min].key) {
               min := j;
            }
        }
       if (min != i) {
            swap(&v[i], &v[min]);
        }
    }
}

Para analizar la complejidad trataremos por separado las comparaciones entre las claves y los movimientos de los registros

Se realizan n - 1 pasadas.
En cada pasada el número de comparaciones entre las claves decrece: n-1, n-2, ..., 2, 1. En total se hacen n*(n-1)/2.
El número de intercambios no es constante, depende de la situación inicial de la tabla. En el mejor de los casos sería 0 (el vector ya estaba ordenado). En el peor de los casos n-1 (cada iteración debemos hacer un intercambio).

La cantidad de movimientos (intercambios) es lineal respecto el tamaño del vector. Por el contrario, la cantidad de comparaciones es de orden cuadrático. La complejidad será, pues O(n²).

Ordenación por inserción

El método de ordenación por inserción supone, como el anterior que tenemos el conjunto de registros dividido en dos subsecuencias, una parte izquierda ya ordenada y el otro con los registros que quedan para ordenar:
[k0, k1, ..., ki-1] [ki, ki + 1, ..., kn-1]

El proceso de ordenación por inserción se fundamenta en insertar en la subsecuencia de la izquierda, el primer registro de la subsecuencia de la derecha. Inicialmente se considera que el primer elemento forma la primera subsecuencia ordenada.

Figura: Suponemos el primer elemento ordenado, y la ordenación finaliza cuando hemos incorporado el último elemento a la parte izquierda

Para insertar un registro en la posición que le corresponde temporalmente hay que prever que deben realizarse desplazamientos de una posición hacia la derecha de algunos elementos que formaban parte de la subsecuencia ordenada. Para el caso de tener que insertar el elemento v[i], podría describirse de la siguiente forma:

Comparar v[i].key con v[j].key (0 ≤ j ≤ i-1) empezando por j = i-1.
Si v[i].key < v[j].key, debe moverse v[j].key a la posición j + 1
Se repiten los pasos 1 y 2 hasta que v[i].key > v[j].key o bien llegamos a la primera posición.

El algoritmo codificado sería:

[Ejemplo 12_04]

Algoritmo
C

const
N: integer = 8;
end const

type
tVec: vector[N] of tReg;
end type

action insertionSort(inout v: tVec, in n: integer)

    var
        i, j: integer;
        z: tReg;
    end var

    for i:=1 to n do
        z := v[i];
        j := i - 1;

        while (j >= 1 and z.key < v[j].key) do
            v[j+1] := v[j];
            j := j-1;
       end while

v[j+1] := z;
end for

end action

#define N 8

typedef tReg tVec[N];

void insertionSort (tVec v; int n) {

   int i,j;
    tReg z;

   for (i = 1; i < n; i++) {
        memcpy(&z, &v[i], sizeof(tReg));
        j = i - 1;
       while (j >= 0 && z.key < v[j].key) {
            memcpy(&v[j+1], &v[j], sizeof(tReg));
            j--;
        }
        memcpy(&v[j+1], &z, sizeof(tReg));
    }
}

Este algoritmo hace una sola pasada sobre toda la secuencia. La cantidad de comparaciones varía según el estado inicial del vector. En el mejor de los casos (vector ordenado) hace n - 1 comparaciones. En el peor (vector ordenado en orden inverso) hace (n² + n)/2-1.

También se debe considerar el número de movimiento de tuplass y de claves (se supone el mismo coste para ambos tipos de movimientos). En el mejor de los casos se hace una copia de la llave y dos de registro para cada comparación 3(n-1). La situación más desfavorable conlleva (n² + 5n -6)/2 traslados de información. De todos modos, la complejidad del algoritmo es O(n²).

Ordenación por intercambio

Existen varios algoritmos basados en este método. El más simple es el algoritmo de la burbuja que también supone que el vector está dividido en dos subsecuencias, a la izquierda la de los elementos menores y desordenados y a la derecha la de los elementos mayores ya ordenados, en cada pasada se compara cada elemento de la parte desordenada con el siguiente y, si entre ellos están fuera de orden, los intercambia. De esta manera cada pasada pone el elemento más grande al final de la parte desordenada de la tabla.

Figura: Se ilustra sólo la primera pasada. Se va comparando cada elemento a su posterior y se intercambian si es necesario. Al final de la pasada se ha ido al final el elemento con la clave mayor, y por lo tanto se incrementa una posición la parte ordenada.

La codificación sería:

[Ejemplo 12_05]

Algoritmo
C

const
N: integer = 8;
end const

type
tVec: vector[N] of tReg;
end type

action bubbleSort(inout v: tVec, in n: integer)

    var
        i, j: integer;
    end var

    for i:=1 to n-1 do
         for j:=1 to n-i do
            if (v[j].key > v[j+1].key) then
                swap(v[j],v[j+1]);
            end if
         end for
    end for

end action

#define N 8

typedef tReg tVec[N];

void bubbleSort(tVec v; int n) {

   int i, j;

   for (i = 0; i < n-1; i++) {
       for (j = 0; j < n-i; j++) {
           if (v[j].clau > v[j+1].clau) {
                swap(&v[j], &v[j+1], sizeof(tReg));
            }
        }
    }
}

El análisis de la complejidad es más simple. Se realizan n - 1 pasadas y en cada pasada n - i comparaciones de claves (1 ≤ i ≤ n-1). En total (n-1)n/2 comparaciones.

Cada intercambio comporta tres movimientos. La cantidad de movimientos será 0 en el mejor de los casos y, como máximo será 3(n²-n)/2 si la secuencia está ordenada inversamente. La complejidad es, en todo caso O(n²).

Puede mejorarse el algoritmo si, al detectar que ya está ordenada la secuencia se para de hacer comparaciones. Para eso hay que tener constancia de cuando se da la situación i no es complicado. Si al realizar una pasada no se ha tenido que hacer ningún intercambio, el vector ya tiene su orden definitivo.

Para ello, basta con añadir una condición sorted. Se supondrá al inicio de cada pasada que el vector está ordenado y, en caso de hacerse un intercambio, se pondrá la condición a 0 (false).

[Ejemplo 12_06]

Algoritmo
C

const
N: integer = 8;
end const

type
tVec: vector[N] of tReg;
end type

action improvedBubbleSort (inout v: tVec, in n: integer)

    var
        i, j: integer;
        sorted: boolean;
    end var

sorted := false;
i := 1;

    while i < n and not sorted do
        sorted := true;
        for j:=1 to n-i do
            if v[j].key > v[j+1].key then
                swap(v[j],v[j+1]);
                sorted := false;
            end if
        end for
        i := i + 1;
    end while

end action

#define N 8

typedef tReg tVec[N];

typedef enum {FALSE, TRUE} boolean;

void improvedBubbleSort(tVec v; int n) {

   int i, j;
    boolean sorted;

    sorted = FALSE;

   for(i = 0; i < n-1 && !sorted; i++) {
        sorted = TRUE;
       for (j = 0; j < n - i; j++) {
           if (v[j].clau > v[j+1].clau) {
                swap(&v[j], &v[j+1], sizeof(tReg));
                sorted = FALSE;
            }
        }
    }
}

Algoritmo QuickSort

El método QuickSort (ordenación rápida) es el algoritmo de ordenación más eficiente de los conocidos hasta ahora.

El mecanismo es recursivo: se trata de seleccionar un elemento k del vector y colocarlo en su sitio definitivo de modo que todos los elementos que queden a su izquierda tengan un valor de clave inferior a k .key y los que queden a su derecha tengan un valor superior. De esta manera se ha partido la secuencia inicial aleatoria en dos subsecuencias también aleatorias pero ordenadas entre ellas (cualquier elemento de la secuencia izquierda es inferior a cualquiera de la derecha).

Por ejemplo, si se parte del vector de valores de key [44, 55, 12, 42, 94, 18, 06, 67] y se elige como elemento de comparación el primero del vector, la evolución en la primera iteración sería:

Figura: el primer elemento tiene com valor key el 44. Después de la primera partición del vector, el 44 ha quedado en su lugar, precedido por los que tienen valores de key inferiores y seguido de los que tienen valores de key superiores.

Después de dividir el vector se vuelve a llamar el algoritmo para que parta la parte izquierda y después la parte derecha. Los vectores serán cada vez más pequeños, y cuando lleguen a un tamaño 1 o 2, el resultado será haber ordenado totalmente el vector.

Figura: evolución completa de la ordenación con quickSort. Denominamos pivot la clave que sirve para hacer cada una de las particiones (la indicamos con las flechas) y se marca en fondo blanco el segmento activo del vector (se se está particionando).

Veamos el algoritmo codificado:

[Ejemplo 12_07]

Algoritmo
C

const
N: integer = 8;
end const

type
tVec: vector[N] of tReg;
end type

action quickSort(inout v: tVec, in begin: integer, in end: integer)

    var
        i, j, pivot: integer;
    end var

if begin < end then

        i := begin + 1;
        j := end;
        pivot := v[begin].key;

        while i<j do
            while (i < end) and (v[i].key <= pivot) do
                i := i+1;
            end while

            while (v[j].key > pivot) do
                j := j-1;
            end while

            if i<j then
                swap(v[i], v[j]);
            end if
        end while

        swap(v[begin], v[j]);
        quickSort(v, begin, j-1);
        quickSort(v, j+1, end);

end if

end action

#define N 8

typedef tReg tVec[N];

void quickSort(tVec v; int begin; int end) {

   int i, j, pivot;

   if (begin < end) {
        i = begin + 1;
        j = end;
        pivot = v[begin].key; // se copia la clave en pivot

       while (i < j) {
           while (i < end && v[i].key <= pivot) {
                i++;
            }

           while (v[j].key > pivot) {
                j--;
            }

           if (i < j) {
                swap(&v[i], &v[j]);
            }
        }

        swap(&v[begin], &v[j]);
        quickSort(v, begin, j-1);
        quickSort(v, j+1, end);
    }
}

La llamada inicial a la acción sería en pseudocódigo quickSort( v, 1, N ) y en C quickSort( v, 0, N-1 ) donde se indica que se debe ordenar todo el vector.

Se puede comprobar que cada partición comporta hacer un recorrido del vector completo (N elementos). Al terminar se envía de nuevo a partir las dos subsecuencias, que serán recorridas y, entre las dos tienen N elementos.

Debido a que cada vez la partición divide el vector en dos, es fácil ver que la cantidad de particiones será proporcional al log₂(N). La complejidad del algoritmo es pues O(n log n).

Comparación de algoritmos

La velocidad de un algoritmo u otro depende de muchos factores, entre ellos, la disposición inicial más o menos favorable (esta condición varía según los algoritmos) y la cantidad de elementos a ordenar.

Se ha podido comprobar que en algorítmica la simplicidad es generalmente contraria a la eficiencia. Así, podemos encontrarnos con que algoritmos muy eficientes, por ser complicados, conllevan más tiempo de cómputo que algoritmos más simples cuando se aplican a ordenaciones de pequeño tamaño.

Un análisis de la eficiencia global deberá considerar cómo evoluciona este parámetro a medida que hacemos crecer los datos.

Conclusiones

Disfrutar de colecciones de datos ordenados permite grandes ventajas en los procesos de búsqueda, sin embargo tanto el proceso de ordenación como el de mantenimiento de datos ordenados (inserciones de nuevos elementos o eliminación de elementos) tiene un coste importante en unidades de cómputo que crece rápidamente con el volumen de los datos.

La mejor estrategia será aquella que valore el balance entre la cantidad de búsquedas y la cantidad de modificaciones que se puede hacer a los datos:

Si el dato estructurado con el que se trabaja es muy volátil (continuamente estamos haciendo modificaciones) y pocas veces se hacen búsquedas, tal vez no sea conveniente invertir esfuerzos en ordenar y/o mantener ordenados los datos.
Si se trata de conjuntos de datos que sufren muchas consultas y raramente se modifican, el esfuerzo de cómputo para hacer la ordenación y para mantener los datos ordenados cuando se hace alguna inserción o eliminación significará una pequeña inversión comparado con el tiempo ahorrado en el conjunto de las búsquedas.

Resumen

En este módulo hemos visto varios algoritmos generales de ordenación de tuplas dispuestas en vectores, y sería extensivo a tablas. Con pequeñas modificaciones los códigos de ejemplo se pueden adaptar a hacer ordenaciones de elementos simples (ordenar números, caracteres) y también a hacer ordenaciones descendientes.

Las grandes familias descritas corresponden a algoritmos:

De selección: donde dada una posición del vector, seleccionamos el dato que hay que poner de entre los que no están ordenadas.
De inserción: donde dado un elemento fuera de orden, lo ponemos en su posición relativa entre los elementos que ya tenemos ordenados.
De intercambio: donde vamos comparando cada elemento con su vecino para dejarlos en orden relativo.
Quick Sort: donde la ordenación es el resultado final del particionado recursivo de los datos según su valor

También hemos visto un pequeño análisis de cómo calcular la complejidad de cada uno de los algoritmos y cómo, a medida que el volumen de datos a ordenar es mayor, es crítica la selección del algoritmo a emplear.

Etiquetas:

[_]

Creado por editor1 el 2018/09/17 11:43