Métodos de Ordenamiento

Los 3 Métodos de Ordenamiento más populares

Hoy les comparto los métodos de ordenamiento de datos más populares que hay, unos más eficientes que otros pero todos conocidos, y de una vez les mostraré un poco de C# para que se den cuenta de la similitud con Java, los ejemplos en código están en ambos lenguajes.

1) Bubble Sort (Ordenamiento Burbuja):

Es el algoritmo de ordenamiento más sencillo de todos, conocido también como método del intercambio directo, el funcionamiento se basa en la revisión de cada elemento de la lista que va a ser ordenada con el elemento siguiente, intercambiando sus posiciones si están en el orden equivocado, para esto se requieren varias revisiones hasta que ya no se necesiten más intercambios, lo que indica que la lista ha sido ordenada.

El origen del nombre de este algoritmo proviene de la forma con la que suben por la lista los elementos durante los intercambios, tal y como si fueran "burbujas", el algoritmo fundamental de este método es la simple comparación de elementos siendo así el más fácil de implementar.

Codificación en Java:

public static int[] OrdenarBurbuja(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;
                }
         }
    }
    return n;

}

Codificación en C#:

Public int[] OrdenarBurbuja(int[]x)
{

        int t= x.Length, temp;

        for(int i=1 ; i< t ; i++)
        {

                for(int j = t-1 ; j >= i; j--)

                {

                        if(x[j] < x[j-1])

                        {

                                temp= x[j];

                                x[j]= x[j-1];

                                x[j-1]= temp;

                        }

                }

        }

}

Ejemplo del ordenamiento de burbuja ordenando una lista de números aleatorios.

2) Quick Sort (Ordenamiento Rápido):

Es el algoritmo de ordenamiento más eficiente de todos, se basa en la técnica de "Divide y Vencerás", que permite en promedio, ordenar n elementos en un tiempo proporcional a n*log(n).
Algoritmo Fundamental:

1. Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote.
2. Resituar 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.
3. 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.
4. Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.

Codificación en Java:

void Quicksort(int[] vector, int first, int last)

{
     int i=first, j=last;
     int pivote=vector[(first + last) / 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(first<j)

     {

          Quicksort(vector,first, j);

     }

     if(last>i)

     {

          Quicksort(vector,i, last);

     }

}

Codificación en C#:

void Quicksort(int[] v, int prim, int ult)
{
 if (prim < ult)
 {
  /*Selecciona 1 elemento del vector y coloca los menores
   que él a su izq y los mayores a su derech*/
  int p = Pivote(v, prim, ult, ult);
 
  /* Repite el proceso para c/u de las particiones

     generadas en el paso anterior */
  Quicksort(v, prim, p - 1);
  Quicksort(v, p + 1, ult);
 }
}
 
/* Implementación no clásica de la función Pivote. En lugar de
recorrer el vector simultáneamente desde ambos extremos hasta el
cruce de índices, se recorre desde el comienzo hasta el final */
int Pivote(int[] v, int prim, int ult, int piv)
{
 int p = v[piv];
 int j = prim;
 
 // Mueve el pivote a la última posición del vector
 Intercambia(v, piv, ult);
 
 /* Recorre el vector moviendo los elementos menores
  o iguales que el pivote al comienzo del mismo */
 for (int i = prim; i < ult; i++)
 {
  if (v[i] <= p)
  {
   Intercambia(v, i, j);
   j++;
  }
 }
 
 // Mueve el pivote a la posición que le corresponde
 Intercambia(v, j, ult);
 
 return j;
}
 
void Intercambia(int[] v, int a, int b)
{
 if (a != b)
 {
  int tmp = v[a];
  v[a] = v[b];
  v[b] = tmp;
 }
}

Quicksort en acción sobre una lista de números aleatorios. Las líneas horizontales son valores pivote.

3) Heap Sort (Ordenamiento por Montículos):

Es un algoritmo de ordenamiento no recursivo, no estable, consiste en almacenar todos los elementos del vector a ordenar en un montículo (heap), y 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.

Codificación en Java:

public class heap_Sort
{
      public static void main(String a[])
      {
            int i;
            int arr[] = {1,3,4,5,2};
            System.out.println("Heap Sort");  
            System.out.println("\n---------------\n");
            System.out.println("\nUnsorted array\n\n");
            for (i = 0; i < arr.length; i++)
                  System.out.print(" "+arr[i]);
            for(i=arr.length; i>1; i--)
            {
                  fnSortHeap(arr, i - 1);
            }
            System.out.println("Sorted array");
            System.out.println("\n---------------\n");
            for (i = 0; i < arr.length; i++)
            {
                  System.out.print(" "+arr[i]);
            }
            public void fnSortHeap(int arr[], int arr2)
            {
                  int i, o;
                  int lCh, rCh, mCh, root, tmp;
                  root = (arr2-1)/2;

                  for(o = root; o >= 0; o--)
                  {
                        for(i=root;i>=0;i--)
                        {
                              lCh = (2*i)+1;
                              rCh = (2*i)+2;
                              if((lCh <= arr2) && (rCh <= arr2))
                              {
                                    if(arr[rCh] >= arr[lCh])
                                    {
                                          mCh = rCh;
                                    }
                                    else
                                    {
                                          mCh = lCh;
                                    }
                              }
                              else
                              {
                                    if(rCh > arr2)
                                    {
                                          mCh = lCh;
                                    }
                                    else
                                    {
                                          mCh = rCh;
                                    }
                              }

                              if(arr[i] < arr[mCh])
                              {
                                    tmp = arr[i];
                                    arr[i] = arr[mCh];
                                    arr[mCh] = tmp;
                              }
                        }
                  }
                  tmp = arr[0];
                  arr[0] = arr[arr2];
                  arr[arr2] = tmp;
                  return;
            }
      }
}

Funcionamiento del Heap Sort: