Nombre Password [ Regístrate ]

Ordenación

 

Cuestiones generales

Su finalidad es organizar ciertos datos (normalmente arrays o ficheros) en un orden creciente o decreciente mediante una regla prefijada (numérica, alfabética...). Atendiendo al tipo de elemento que se quiera ordenar puede ser:

- Ordenación interna: Los datos se encuentran en memoria (ya sean arrays, listas, etc) y son de acceso aleatorio o directo (se puede acceder a un determinado campo sin pasar por los anteriores).

- Ordenación externa: Los datos están en un dispositivo de almacenamiento externo (ficheros) y su ordenación es más lenta que la interna.

 

Ordenación interna

Los métodos de ordenación interna se aplican principalmente a arrays unidimensionales. Los principales algoritmos de ordenación interna son:

Selección: Este método consiste en buscar el elemento más pequeño del array y ponerlo en primera posición; luego, entre los restantes, se busca el elemento más pequeño y se coloca en segudo lugar, y así sucesivamente hasta colocar el último elemento. Por ejemplo, si tenemos el array {40,21,4,9,10,35}, los pasos a seguir son:

{4,21,40,9,10,35} <-- Se coloca el 4, el más pequeño, en primera posición : se cambia el 4 por el 40.
{4,9,40,21,10,35} <-- Se coloca el 9, en segunda posición: se cambia el 9 por el 21.
{4,9,10,21,40,35} <-- Se coloca el 10, en tercera posición: se cambia el 10 por el 40.
{4,9,10,21,40,35} <-- Se coloca el 21, en tercera posición: ya está colocado.
{4,9,10,21,35,40} <-- Se coloca el 35, en tercera posición: se cambia el 35 por el 40.

Si el array tiene N elementos, el número de comprobaciones que hay que hacer es de N*(N-1)/2, luego el tiempo de ejecución está en O(n2)

var
   lista: array[1..N] of byte;
   aux, i, j, menor: byte;

BEGIN
 for i:= 1 to N-1 do
  begin
   menor:= i;
   for j:= i+1 to N do
    if (lista [j+1]<lista[j]) then
     begin
      if (lista[j]<lista[menor]) then  {si el elemento j es menor que el menor}
       menor:=j;                       {pasa a ser el menor}
      aux:= lista[i];                  {se intercambian los elemento}
      lista[i]:=lista[menor];          {de las posiciones i y menor}
      lista[menor]:=aux;               {usando la variable auxiliar}
     end;
  end;
END.

Burbuja: Consiste en comparar pares de elementos adyacentes e intercambiarlos entre sí hasta que estén todos ordenados. Con el array anterior, {40,21,4,9,10,35}:

Primera pasada:
{21,40,4,9,10,35} <-- Se cambia el 21 por el 40.
{21,4,40,9,10,35} <-- Se cambia el 40 por el 4.
{21,4,9,40,10,35} <-- Se cambia el 9 por el 40.
{21,4,9,10,40,35} <-- Se cambia el 40 por el 10.
{21,4,9,10,35,40} <-- Se cambia el 35 por el 40.

Segunda pasada:
{4,21,9,10,35,40} <-- Se cambia el 21 por el 4.
{4,9,21,10,35,40} <-- Se cambia el 9 por el 21.
{4,9,10,21,35,40} <-- Se cambia el 21 por el 10.

Ya están ordenados, pero para comprobarlo habría que acabar esta segunda comprobación y hacer una tercera.

Si el array tiene N elementos, para estar seguro de que el array está ordenado, hay que hacer N-1 pasadas, por lo que habría que hacer (N-1)*(N-i-1) comparaciones, para cada i desde 1 hasta N-1. El número de comparaciones es, por tanto, N(N-1)/2, lo que nos deja un tiempo de ejecución, al igual que en la selección, en O(n2).

var
   lista: array[1..N] of byte;
   aux, i, j: byte;

BEGIN

{Dar valores a los elementos del array}

 for i:= 1 to N do
  for j:= 1 to N-i do
   if (lista [j+1]<lista[j]) then
    begin
     aux:= lista[j+1];
     lista[j+1]:=lista[j];
     lista[j]:=aux;
    end;
END.

Inserción directa: En este método lo que se hace es tener una sublista ordenada de elementos del array e ir insertando el resto en el lugar adecuado para que la sublista no pierda el orden. La sublista ordenada se va haciendo cada vez mayor, de modo que al final la lista entera queda ordenada. Para el ejemplo {40,21,4,9,10,35}, se tiene:

{40,21,4,9,10,35} <-- La primera sublista ordenada es {40}.

Insertamos el 21:
{40,40,4,9,10,35} <-- aux=21;
{21,40,4,9,10,35} <-- Ahora la sublista ordenada es {21,40}.

Insertamos el 4:
{21,40,40,9,10,35} <-- aux=4;
{21,21,40,9,10,35} <-- aux=4;
{4,21,40,9,10,35} <-- Ahora la sublista ordenada es {4,21,40}.

Insertamos el 9:
{4,21,40,40,10,35} <-- aux=9;
{4,21,21,40,10,35} <-- aux=9;
{4,9,21,40,10,35} <-- Ahora la sublista ordenada es {4,9,21,40}.

Insertamos el 10:
{4,9,21,40,40,35} <-- aux=10;
{4,9,21,21,40,35} <-- aux=10;
{4,9,10,21,40,35} <-- Ahora la sublista ordenada es {4,9,10,21,40}.

Y por último insertamos el 35:
{4,9,10,21,40,40} <-- aux=35;
{4,9,10,21,35,40} <-- El array está ordenado.

En el peor de los casos, el número de comparaciones que hay que realizar es de N*(N+1)/2-1, lo que nos deja un tiempo de ejecución en O(n2). En el mejor caso (cuando la lista ya estaba ordenada), el número de comparaciones es N-2. Todas ellas son falsas, con lo que no se produce ningún intercambio. El tiempo de ejecución está en O(n).

El caso medio dependerá de cómo están inicialmente distribuidos los elementos. Vemos que cuanto más ordenada esté inicialmente más se acerca a O(n) y cuanto más desordenada, más se acerca a O(n2).

El peor caso es igual que en los métodos de burbuja y selección, pero el mejor caso es lineal, algo que no ocurría en éstos, con lo que para ciertas entradas podemos tener ahorros en tiempo de ejecución.

var
 lista: array[1..N] of byte;
 i, j, aux: byte;
 encontrado: boolean;

BEGIN

{Dar valores a los elementos del array}

 for i:= 2 to N do
  begin
   aux:= lista[i];                     {se intenta añadir el elemento i}
   encontrado:=false;
   j:=i-1;
   while not(encontrado) and (j>=1) do {se recorre la sublista de atras a adelante
                                       para buscar la nueva posicion del elemento i}
    begin
     if (aux>lista[j]) then            {si se encuentra la posición}
      begin
       lista[j+1]:=aux;                {se coloca}
       encontrado:=true;               {y se sale del bucle para colocar el siguiente número}
      end
     else                              {si no, se sigue buscando}
      begin
       lista[j+1]:=lista[j];
       dec(j);
      end;
    end;
   if (j=0) then lista[1]:= aux;       {si se han mirado todas las posiciones y no se ha
                                       encontrado, es que es la primera posicion}
  end;
END.

Inserción binaria: Es el mismo método que la inserción directa, excepto que la búsqueda del orden de un elemento en la sublista ordenada se realiza mediante una búsqueda binaria (ver algoritmos de búsqueda), lo que en principio supone un ahorro de tiempo. No obstante, dado que para la inserción sigue siendo necesario un desplazamiento de los elementos, el ahorro, en la mayoría de los casos, no se produce, si bien hay compiladores que realizan optimizaciones que lo hacen ligeramente más rápido.

Shell: Es una mejora del método de inserción directa, utilizado cuando el array tiene un gran número de elementos. En este método no se compara a cada elemento con el de su izquierda, como en el de inserción, sino con el que está a un cierto número de lugares (llamado salto) a su izquierda. Este salto es constante, y su valor inicial es N/2 (siendo N el número de elementos, y siendo división entera). Se van dando pasadas hasta que en una pasada no se intercambie ningún elemento de sitio. Entonces el salto se reduce a la mitad, y se vuelven a dar pasadas hasta que no se intercambie ningún elemento, y así sucesivamente hasta que el salto vale 1.

Por ejemplo, lo pasos para ordenar el array {40,21,4,9,10,35} mediante el método de Shell serían:

Salto=3:
   Primera pasada:
   {9,21,4,40,10,35} <-- se intercambian el 40 y el 9.
   {9,10,4,40,21,35} <-- se intercambian el 21 y el 10.
Salto=1:
   Primera pasada:
   {9,4,10,40,21,35} <-- se intercambian el 10 y el 4.
   {9,4,10,21,40,35} <-- se intercambian el 40 y el 21.
   {9,4,10,21,35,40} <-- se intercambian el 35 y el 40.
   Segunda pasada:
   {4,9,10,21,35,40} <-- se intercambian el 4 y el 9.

Con sólo 6 intercambios se ha ordenado el array, cuando por inserción se necesitaban muchos más.

var
 lista: array[1..N] of byte;
 aux, i, salto, cambios: byte;


BEGIN
 salto:= N div 2;
 while not(salto=0) do                   {el salto va desde N/2 hasta 1}
  begin
   cambios:=1;
   while not(cambios=0) do               {mientras se intercambien elementos}
    begin
     cambios:=0;
     for i:= (salto+1) to N do           {se pasa una vez}
      begin
       if (lista[i-salto]>lista[i]) then {y se reordenan si no lo estan}
        begin
         aux:=lista[i];
         lista[i]:=lista[i-salto];
         lista[i-salto]:=aux;
         inc(cambios);
        end;
      end;
    end;
   salto:= salto div 2;
  end;
END.

Ordenación rápida (quicksort): Este método se basa en la táctica "divide y vencerás" (ver sección divide y vencerás), que consiste en ir subdividiendo el array en arrays más pequeños, y ordenar éstos. Para hacer esta división, se toma un valor del array como pivote, y se mueven todos los elementos menores que este pivote a su izquierda, y los mayores a su derecha. A continuación se aplica el mismo método a cada una de las dos partes en las que queda dividido el array.

Normalmente se toma como pivote el primer elemento de array, y se realizan dos búsquedas: una de izquierda a derecha, buscando un elemento mayor que el pivote, y otra de derecha a izquierda, buscando un elemento menor que el pivote. Cuando se han encontrado los dos, se intercambian, y se sigue realizando la búsqueda hasta que las dos búsquedas se encuentran.Por ejemplo, para dividir el array {21,40,4,9,10,35}, los pasos serían:

{21,40,4,9,10,35} <-- se toma como pivote el 21. La búsqueda de izquierda a derecha encuantra el valor 40, mayor que pivote, y la búsqueda de derecha a izquierda encuentra el valor 10, menor que el pivote. Se intercambian:
{21,10,4,9,40,35} <-- Si seguimos la búsqueda, la primera encuentra el valor 40, y la segunda el valor 9, pero ya se han cruzado, así que paramos. Para terminar la división, se coloca el pivote en su lugar (en el número encontrado por la segunda búsqueda, el 9, quedando:
{9,10,4,21,40,35} <-- Ahora tenemos dividido el array en dos arrays más pequeños: el {9,10,4} y el {40,35}, y se repetiría el mismo proceso.

Intercalación: no es propiamente un método de ordenación, consiste en la unión de dos arrays ordenados de modo que la unión esté también ordenada. Para ello, basta con recorrer los arrays de izquierda a derecha e ir cogiendo el menor de los dos elementos, de forma que sólo aumenta el contador del array del que sale el elemento siguiente para el array-suma. Si quisiéramos sumar los arrays {1,2,4} y {3,5,6}, los pasos serían:

Inicialmente: i1=0, i2=0, is=0.
Primer elemento: mínimo entre 1 y 3 = 1. Suma={1}. i1=1, i2=0, is=1.
Segundo elemento: mínimo entre 2 y 3 = 2. Suma={1,2}. i1=2, i2=0, is=2.
Tercer elemento: mínimo entre 4 y 3 = 3. Suma={1,2,3}. i1=2, i2=1, is=3.
Cuarto elemento: mínimo entre 4 y 5 = 4. Suma={1,2,3,4}. i1=3, i2=1, is=4.
Como no quedan elementos del primer array, basta con poner los elementos que quedan del segundo array en la suma:
Suma={1,2,3,4}+{5,6}={1,2,3,4,5,6}

var
 i1,i2,is: byte;
 lista1: array[1..N1] of byte;
 lista2: array[1..N2] of byte;
 suma: array[1..N1+N2] of byte;

BEGIN
 i1:=1;
 i2:=1;
 is:=1;
 while (i1<=N1) and (i2<=N2) do
  begin
   if (lista1[i1]<lista2[i2]) then
    begin
     suma[is]:=lista1[i1];
     inc(i1);
    end
   else
    begin
     suma[is]:=lista2[i2];
     inc(i2);
    end;
   inc(is);
  end;

 if (i1<N1) then          {se termina de añadir el array que no haya llegado al final}
  for i:=i1 to N1 do
   begin
    suma[is]:=lista1[i];
    inc(is);
   end
  else
   begin
    for i:=i2 to N2 do
     begin
      suma[is]:=lista2[i];
      inc(is);
     end;
   end;
END.

Fusión: Consta de dos partes, una parte de intercalación de listas y otra de divide y vencerás.

- Primera parte: ¿Cómo intercalar dos listas ordenadas en una sola lista ordenada de forma eficiente?

Suponemos que se tienen estas dos listas de enteros ordenadas ascendentemente:

lista 1: 1 -> 3 -> 5 -> 6 -> 8 -> 9
lista 2: 0 -> 2 -> 6 -> 7 -> 10

Tras mezclarlas queda:

lista: 0 -> 1 -> 2 -> 3 -> 5 -> 6 -> 6 -> 7 -> 8 -> 9 -> 10

Esto se puede realizar mediante un único recorrido de cada lista, mediante dos punteros que recorren cada una. En el ejemplo anterior se insertan en este orden -salvo los dos 6 que puede variar según la implementación-: 0 (lista 2), el 1 (lista 1), el 2 (lista 2), el 3, 5 y 6 (lista 1), el 6 y 7 (lista 2), el 8 y 9 (lista 1), y por llegar al final de la lista 1, se introduce directamente todo lo que quede de la lista 2, que es el 10.

En la siguiente implementación no se crea una nueva lista realmente, sólo se modifican los enlaces destruyendo las dos listas y fusionándolas en una sola. Se emplea un centinela que apunta a sí mismo y que contiene como clave el valor más grande posible. El último elemento de cada lista apuntará al centinela, incluso si la lista está vacía.

struct lista
{
  int clave;
  struct lista *sig;
};


struct lista *centinela;
centinela = (struct lista *) malloc(sizeof(struct lista));
centinela->sig = centinela;
centinela->clave = INT_MAX;
...

struct lista *fusion(struct lista *l1, struct lista *l2)
{
  struct lista *inic, *c;

  if (l1->clave < l2->clave) { inic = l1; l1 = l1->sig; }
  else { inic = l2; l2 = l2->sig; }
  c = inic;
  while (l1 != centinela && l2 != centinela) {
    if (l1->clave < l2->clave) {
      c->sig = l1; l1 = l1->sig;
    }
    else {
      c->sig = l2; l2 = l2->sig;
    }
    c = c->sig;
  }
  if (l1 != centinela) c->sig = l1;
  else if (l2 != centinela) c->sig = l2;
  return inic;
}

- Segunda parte: divide y vencerás. Se separa la lista original en dos trozos del mismo tamaño (salvo listas de longitud impar) que se ordenan recursivamente, y una vez ordenados se fusionan obteniendo una lista ordenada. Como todo algoritmo basado en divide y vencerás tiene un caso base y un caso recursivo.

* Caso base: cuando la lista tiene 1 ó 0 elementos (0 se da si se trata de ordenar una lista vacía). Se devuelve la lista tal cual está.

* Caso recursivo: cuando la longitud de la lista es de al menos 2 elementos. Se divide la lista en dos trozos del mismo tamaño que se ordenan recursivamente. Una vez ordenado cada trozo, se fusionan y se devuelve la lista resultante.

El esquema es el siguiente:

Ordenar(lista L)
inicio
  si tamaño de L es 1 o 0 entonces
    devolver L
  si tamaño de L es >= 2 entonces
    separar L en dos trozos: L1 y L2.
    L1 = Ordenar(L1)
    L2 = Ordenar(L2)
    L = Fusionar(L1, L2)
    devolver L
fin

El algoritmo funciona y termina porque llega un momento en el que se obtienen listas de 2 ó 3 elementos que se dividen en dos listas de un elemento (1+1=2) y en dos listas de uno y dos elementos (1+2=3, la lista de 2 elementos se volverá a dividir), respectivamente. Por tanto se vuelve siempre de la recursión con listas ordenadas (pues tienen a lo sumo un elemento) que hacen que el algoritmo de fusión reciba siempre listas ordenadas.

Se incluye un ejemplo explicativo donde cada sublista lleva una etiqueta identificativa.


Dada: 3 -> 2 -> 1 -> 6 -> 9 -> 0 -> 7 -> 4 -> 3 -> 8 (lista original)

se divide en:
3 -> 2 -> 1 -> 6 -> 9 (lista 1)
0 -> 7 -> 4 -> 3 -> 8 (lista 2)
·    se ordena recursivamente cada lista:
·    3 -> 2 -> 1 -> 6 -> 9 (lista 1)
·  ·      se divide en:
·  ·      3 -> 2 -> 1 (lista 11)
·  ·      6 -> 9 (lista 12)
·  ·          se ordena recursivamente cada lista:
·  ·          3 -> 2 -> 1 (lista 11)
·  ·  ·            se divide en:
·  ·  ·            3 -> 2 (lista 111)
·  ·  ·            1 (lista 112)
·  ·  ·                se ordena recursivamente cada lista:
·  ·  ·                3 -> 2 (lista 111)
·  ·  ·                    se divide en:
·  ·  ·                    3 (lista 1111, que no se divide, caso base). Se devuelve 3
·  ·  ·                    2 (lista 1112, que no se divide, caso base). Se devuelve 2
·  ·  ·                    se fusionan 1111-1112 y queda:
·  ·  ·                         2 -> 3. Se devuelve 2 -> 3
·  ·  ·                1 (lista 112)
· · · 1 (lista 1121, que no se divide, caso base). Se devuelve 1
· · · se fusionan 111-112 y queda: · · · 1 -> 2 -> 3 (lista 11). Se devuelve 1 -> 2 -> 3 · · 6 -> 9 (lista 12) · · · se divide en: · · · 6 (lista 121, que no se divide, caso base). Se devuelve 6 · · · 9 (lista 122, que no se divide, caso base). Se devuelve 9 · · · se fusionan 121-122 y queda: · · · 6 -> 9 (lista 12). Se devuelve 6 -> 9
· · se fusionan 11-12 y queda: · · 1 -> 2 -> 3 -> 6 -> 9. Se devuelve 1 -> 2 -> 3 -> 6 -> 9 · 0 -> 7 -> 4 -> 3 -> 8 (lista 2) · ... tras repetir el mismo procedimiento se devuelve 0 -> 3 -> 4 -> 7 -> 8 · se fusionan 1-2 y queda: · 0 -> 1 -> 2 -> 3 -> 3 -> 4 -> 6 -> 7 -> 8 -> 9, que se devuelve y se termina.

 

La implementación propuesta emplea un centinela sobre la lista inicial que apunte hacia sí mismo y que además contiene el máximo valor de un entero. La lista dispone de cabecera y centinela, pero obsérvese como se elimina durante la ordenación.

#include <stdlib.h>
#include <limits.h>

struct lista
{
  int clave;
  struct lista *sig;
};
/* lista con cabecera y centinela */
struct listacc
{
  struct lista *cabecera,
               *centinela;
};

/* centinela declarado como variable global */
struct lista *centinela;

  /* fusiona dos listas */
struct lista *fusion(struct lista *l1, struct lista *l2)
{
  struct lista *inic, *c;

  if (l1->clave < l2->clave) { inic = l1; l1 = l1->sig; }
  else { inic = l2; l2 = l2->sig; }
  c = inic;
  while (l1 != centinela && l2 != centinela) {
    if (l1->clave < l2->clave) {
      c->sig = l1; l1 = l1->sig;
    }
    else {
      c->sig = l2; l2 = l2->sig;
    }
    c = c->sig;
  }
  if (l1 != centinela) c->sig = l1;
  else if (l2 != centinela) c->sig = l2;
  return inic;
}

  /* algoritmo de ordenación por fusión mediante divide y vencerás */
struct lista *ordenfusion(struct lista *l)
{
  struct lista *l1, *l2, *parte1, *parte2;

    /* caso base: 1 ó 0 elementos */
  if (l->sig == centinela) return l;


    /* caso recursivo */
  /* avanza hasta la mitad de la lista */
  l1 = l; l2 = l1->sig->sig;
  while (l2 != centinela) {
    l1 = l1->sig;
    l2 = l2->sig->sig;
  }
  /* la parte en dos */
  l2 = l1->sig;
  l1->sig = centinela;

  /* ordena recursivamente cada parte */
  parte1 = ordenfusion(l);
  parte2 = ordenfusion(l2);

  /* mezcla y devuelve la lista mezclada */
  l = fusion(parte1, parte2);
  return l;
}


  /* operaciones de lista */
void crearLCC(struct listacc *LCC)
{
  LCC->cabecera = (struct lista *) malloc(sizeof(struct lista));
  LCC->centinela = (struct lista *) malloc(sizeof(struct lista));
  LCC->cabecera->sig = LCC->centinela;
  LCC->centinela->sig = LCC->centinela;
}

  /* inserta un elemento al comienzo de la lista */
void insertarPrimero(struct listacc LCC, int elem)
{
  struct lista *nuevo;

  nuevo = (struct lista *) malloc(sizeof(struct lista));
  nuevo->clave = elem;
  nuevo->sig = LCC.cabecera->sig;
  LCC.cabecera->sig = nuevo;
}

int main(void)
{
  struct listacc LCC;
  crearLCC(&LCC);
  centinela = LCC.centinela;
  centinela->clave = INT_MAX;

  insertarPrimero(LCC, 8);
  insertarPrimero(LCC, 3);
  insertarPrimero(LCC, 4);
  insertarPrimero(LCC, 7);
  insertarPrimero(LCC, 0);
  insertarPrimero(LCC, 9);
  insertarPrimero(LCC, 6);
  insertarPrimero(LCC, 1);
  insertarPrimero(LCC, 2);
  insertarPrimero(LCC, 3);
  LCC.cabecera = ordenfusion(LCC.cabecera->sig);

  return 0;
}

Este es un buen algoritmo de ordenación, pues no requiere espacio para una nueva lista y sólo las operaciones recursivas consumen algo de memoria. Es por tanto un algoritmo ideal para ordenar listas.

La complejidad es la misma en todos los casos, ya que no influye cómo esté ordenada la lista inicial -esto es, no existe ni mejor ni peor caso-, puesto que la intercalación de dos listas ordenadas siempre se realiza de una única pasada. La complejidad es proporcional a N·logN, característica de los algoritmos "Divide y Vencerás". Para hacer más eficiente el algoritmo es mejor realizar un primer recorrido sobre toda la lista para contar el número de elementos y añadir como parámetro a la función dicho número.

 

 


© (2001-2008) ALGORITMIA.NET - Política de privacidad