Flujo de un algoritmo

Los algoritmos de ordenación fueron para mí, en un época de mi vida, una especie de obsesión geek que me llevó a investigar, en los albores de Internet, miles de horas delante de la pantalla del ordenador con el único objeto de diseñar algo que fuera más rápido que lo que yo ya conocía. Eran tiempos en los que aún había más información en los libros que en la Red, y en el escritorio se apilaban revistas de informática, libros de programación, disquetes de 5,25″ y decenas de papeles con garabatos esbozados entre apuntes de direcciones web.

El hecho de disponer de una lista (numérica o alfanumérica) desordenada y conseguir ordenarla en un límite de tiempo lógico, ha traído de cabeza a los informáticos de medio mundo desde los tiempos aquellos en los que los primeros profesionales diseñaban aplicaciones bancarias para entidades financieras en lenguaje Cobol. El éxito consistía en lograr obtener un orden rápido y efectivo, ya que no era lo mismo esperar unos segundos para clasificar una matriz de 100 elementos que reordenar las cincuenta mil transacciones que se podían generar en una sucursal bancaria en un día.

El algoritmo de ordenamiento era, pues, muy importante. Pero cada algoritmo que se diseñaba para tal fin no era otra cosa que la genialidad de una mente preclara que, por casualidad o no, discurría un sistema de “cambiar éste de aquí por aquel de allí” para, sucesivamente, recorrer la lista de valores hasta ordenarla completamente.

Las máquinas computadoras, por definición, son tontas de manual. Un ordenador es incapaz de ordenar inteligentemente una lista de valores simplemente contemplándolos, como haría un ser humano. Es por ello que hay que desarrollar algoritmos, que no son ni más ni menos que una sucesión de procesos u operaciones perfectamente documentadas que se ejecutan con el fin de solucionar un problema dado. Posteriormente, estos algoritmos se codifican en un lenguaje de programación para que un ordenador los entienda y los maneje convenientemente.

Entonces, los algoritmos de ordenación son pautas que un software debe seguir para lograr ordenar una lista de elementos rápida y adecuadamente. Existen muchos y de muy variada condición y complejidad. Todos tienen pros y contras y todos contaron en su día (y cuentan hoy) con partidarios y detractores.

A día de hoy cada vez se han hecho menos necesarios estos métodos, ya que los elementos utilizados se almacenan en bases de datos muy avanzadas tecnológicamente y que poseen algoritmos de clasificación y ordenamiento propios. Pero no está mal para cualquier desarrollador conocerlos, porque, de hecho, a la hora de ponerse a programar los necesitaremos en multitud de ocasiones.

Siempre que escribo un post en el que va a haber códigos de ejemplo, nunca sé que lenguaje de programación utilizar; son tantos en la cabeza… Normalmente decido a bulto, para no decantarme por uno solo, así que hoy le ha tocado a Java porque sí, y punto. Se pueden encontrar en Internet multitud de ejemplos en los más variados lenguajes. Es posible que tampoco reseñemos absolutamente todos los algoritmos de ordenación que existen, pero sí vamos a estudiar los más importantes y extendidos.

1. Método de inserción directa (Insertion sort).
Este algoritmo es muy elemental, antiguo y lento, aunque su utilización está justificada en problemas pequeños debido a su bajo consumo de recursos. Este método toma cada elemento del arreglo para ser ordenado y lo compara con los que se encuentran en posiciones anteriores a la de él dentro del arreglo. Si resulta que el elemento con el que se está comparando es mayor que el elemento que ordenar, se recorre hacia la siguiente posición superior. Si por el contrario, resulta que el elemento con el que se está comparando es menor que el elemento que ordenar, se detiene el proceso de comparación, pues se encontró que el elemento ya está ordenado y se coloca en su posición (que es la siguiente a la del último número con el que se comparó).

Código

void Insercion (int[] v) {
   for (int i=1; i<v.length; i++) {
      int aux = v[i];
      int j;
      for (j=i-1; j>=0 && v[j]>aux; j--)
         v[j+1] = v[j];
         v[j+1] = aux;
    }
}

2. Método de selección (Selection sort).
Este método también es muy lento, sin embargo, por su estructura, reduce al mínimo el número de intercambios. Consiste en encontrar el menor de todos los elementos del arreglo e intercambiarlo con el que está en la primera posición. Luego el segundo más pequeño, y así sucesivamente hasta ordenar todo el arreglo.

Código

void Selecccion (int[] a) {
   for (int i = 0; i < a.length - 1; i++) {
     int min = i;
     for (int j = i + 1; j < a.length; j++) {
        if (a[j] < a[min]) {
           min = j;
        }
     }
     if (i != min) {
        int aux= a[i];
        a[i] = a[min];
        a[min] = aux;
     }
   }
}

3. Método de la burbuja (Bubble sort).
Este archiconocido método es muy parecido al de inserción directa pero mucho más rápido. Fue muy popular cuando apareció porque sustituía a los anteriores bajando drásticamente la velocidad de ordenación. Se recorre el arreglo intercambiando los elementos adyacentes que estén desordenados. Se recorre el arreglo tantas veces hasta que ya no haya cambios. Prácticamente lo que hace es tomar el elemento mayor y lo va corriendo de posición en posición hasta ponerlo en su lugar.

Código

void Burbuja (int[] n) {
   int temp;
   int t = n.length;
   for (int i = 1; i < t; i++) {
      for (int k = t-1; k >= i; k--) {
         if(n[k] < n[k-1]){
            temp = n[k];
            n[k] = n[k-1];
            n[k-1]=  temp;
         }
      }
   }
}

4. Método de Shell (Shell sort).
El método de ordenación Shell, así llamado en honor a su inventor Donald Shell, es considerado un algoritmo avanzado cuya velocidad es notablemente mayor con respecto a los anteriores. Este método utiliza una segmentación entre los datos; funciona comparando elementos que están distantes. La distancia entre comparaciones decrece conforme el algoritmo se ejecuta hasta la última fase, en la cual se comparan los elementos adyacentes, por esta razón se le llama también ordenación por disminución de incrementos.

Código

void Shell (int[] a) {
   for ( int increment = a.length / 2;
      increment > 0;
      increment = (increment == 2 ? 1 : (int) Math.round(increment / 2.2))) {
      for (int i = increment; i < a.length; i++) {
         for (int j = i; j >= increment && a[j - increment] > a[j]; j -= increment) {
            int temp = a[j];
            a[j] = a[j - increment];
            a[j - increment] = temp;
         }
      }
   }
}

5. Método de mezcla (Merge sort).
La ordenación por mezcla o combinación de capas se basa en la estrategia de dividir para conquistar (divide y vencerás). Primero divide el arreglo en dos, ordena recursivamente cada una de las partes y luego las mezcla. El procedimiento debe entonces recibir el arreglo y un par de índices que delimitan los bordes de la ordenación.

Código

public class Mezcla {
   private int A[];
   public int[] Ordenar (int[] L) {
      int n = L.length;
      if (n > 1){ int m = (int) (Math.ceil(n/2.0));
         int [] L1 = new int[m];
         int [] L2 = new int[n-m];
         for (int i = 0; i < m; i++) {
           L1[i] = L[i];
         }
         for (int i = m; i < n; i++) {
            L2[i-m] = L[i];
         }
         L = Mezcla(Ordenar(L1), Ordenar(L2));
      }
      return L;
   }

   public int[] Eliminar (int [] l) {
      int [] L = new int[l.length-1];
      for(int i = 1; i < l.length; i++){
         L[i-1] = l[i];
      }
      return L;
   }

   public int[] Mezcla(int[] L1, int[] L2) {
      int[] L = new int[L1.length+L2.length];
      int i = 0;
      while ((L1.length != 0) && (L2.length != 0)) {
         if (L1[0] < L2[0]) {
            L[i++] = L1[0];
            L1 = eliminar(L1);
            if (L1.length == 0){ while (L2.length != 0) {
               L[i++] = L2[0];
               L2 = Eliminar(L2);
            }
         }
      }
      else {
         L[i++] = L2[0];
         L2 = Eliminar(L2);
         if (L2.length == 0) {
            while (L1.length != 0) {
               L[i++] = L1[0];
               L1 = eliminar(L1);
            }
         }
      }
   }
   return L;

   void GenerarNumeros() {
      Random ran = new Random();
      int x;
      for(int i = 0; i < A.length; i++) {
         x = (int)(ran.nextDouble()*10000);
         A[i] = x;
      }
   }

   void imprimir() {
      for(int i = 0; i < A.length; i++) {
         System.out.println(A[i]);
      }
   }

   int[] getA(){
      return A;
   }

   void setA(int []A){
      this.A = A;
   }
}

6. Método de montículos (Heap sort).
Este algoritmo consiste en almacenar todos los elementos del vector que se desea ordenar en un montículo (heap), para luego extraer el nodo que queda como nodo raíz del montículo (cima) en sucesivas iteraciones obteniendo el conjunto ordenado. Basa su funcionamiento en una propiedad de los montículos por la cual la cima contiene siempre el menor elemento (o el mayor, según se haya definido el montículo) de todos los almacenados en él.

Código

import java.util.Arrays;
public class Heap {
   void main(String[] args) {
      int[] arry_int={49,38,65,97,76,13,27,55};
      Heap OrdenaHeap=new OrdenaHeap();
      hsort.OrdenaHeap(arry_int);
   }

   void AjustaHeap(int[] arr, int s,int m) {
      int temp=arr[s];
      for(int j=2*s+1;j<m;j=j*2+1) {
         if(j+1<m && arr[j]>arr[j+1]) ++j;
            if(temp<arr[j])break;
               arr[s]=arr[j];
               s=j;
               arr[s]=temp;
            }
         }

   void OrdenaHeap (int[] arr) {
      for(int i=(arr.length/2-1);i>=0;--i) {
         AjustaHeap(arr,i,arr.length);
      }
      for(int j=arr.length-1;j>0;--j) {
         System.out.println("Elemento superior del montículo arrr[0]="+arr[0]);
         System.out.println("arr["+j+"]="+arr[j]);
         System.out.println("se cambia con"+j+"element");
         int temp=arr[0];
         arr[0]=arr[j];
         arr[j]=temp;
         AjustaHeap(arr,0,j);
         System.out.println(Arrays.toString(arr));
      }
   }
}

7. Método de ordenamiento rápido (Quick sort).
Consiste en elegir un elemento de la lista para ordenar, al que llamaremos pivote. Resituamos los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él y al otro los mayores. Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la implementación deseada. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada. La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote y otra por los elementos a su derecha. Se repite este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado el procedimiento, todos los elementos estarán ordenados.

Código

void Rapido (int[] vector, int primero, int ultimo) {
   int i=primero, j=ultimo;
   int pivote=(vector[primero]+vector[ultimo])/2;
   int auxiliar;
   do {
      while(vector[i]<pivote) i++;   
      while(vector[j]>pivote) j--;

      if (i<=j) {
         auxiliar=vector[j];
         vector[j]=vector[i];
         vector[i]=auxiliar;
         i++;
         j--;
      }
   }
   while (i<=j);

   if(primero<j) ordenarQuicksort(vector,primero, j);
   if(ultimo>i) ordenarQuicksort(vector,i, ultimo);
}

8. Método de ordenamiento Radix (Radix sort).
Es un algoritmo de ordenamiento que ordena enteros procesando sus dígitos de forma individual. La mayor parte de los ordenadores digitales simbolizan internamente todos sus datos como representaciones electrónicas de números binarios, por lo que procesar los dígitos de las representaciones de enteros por representaciones de grupos de dígitos binarios es lo más conveniente.

Código

public class Radix {
   void Radix (int[] arr) {
      if(arr.length == 0)
      return;
      int[][] np = new int[arr.length][2];
      int[] q = new int[0x100];
      int i,j,k,l,f = 0;
      for(k=0;k<4;k++) {
         for(i=0;i<(np.length-1);i++)
         np[i][1] = i+1;
         np[i][1] = -1;
         for(i=0;i<q.length;i++)
         q[i] = -1;
         for(f=i=0;i<arr.length;i++) {
            j = ((0xFF<<(k<<3))&arr[i])>>(k<<3);
            if(q[j] == -1)
            l = q[j] = f;
         else {
            l = q[j];
            while(np[l][1] != -1)
            l = np[l][1];
            np[l][1] = f;
            l = np[l][1];
         }
         f = np[f][1];
         np[l][0] = arr[i];
         np[l][1] = -1;
      }
      for(l=q[i=j=0];i<0x100;i++)
      for(l=q[i];l!=-1;l=np[l][1])
      arr[j++] = np[l][0];
   }

   void main(String[] args) {
      int i;
      int[] arr = new int[15];
      System.out.print("original: ");
      for(i=0;i<arr.length;i++) {
         arr[i] = (int)(Math.random() * 1024);
         System.out.print(arr[i] + " ");
      }

      Radix (arr);
      System.out.print("\nordenados: ");
      for(i=0;i<arr.length;i++)
      System.out.print(arr[i] + " ");
      System.out.println("\nHecho.");
   }
}

6 comentarios a “Algoritmos de ordenamiento”