C - Algoritmos de ordenación

En la entrada de hoy os voy a explicar varios algoritmos de ordenación aplicables a cualquier lenguaje de programación, pero que os explicaré en lenguaje C.

Algoritmo de la burbuja (Bubblesort)
Consiste en realizar n - 1 pasadas por el vector y comparará si la posición actual es mayor que la siguiente, y en caso afirmativo hará un intercambio de posiciones. A continuación os dejo el código de este algortimo:

void Burbuja(int A [n]) // Suponemos de 0 a n-1
{
   int i,j;
   for ( i=0; i< n-1; i++){ //Realiza las n-1 pasadas
      for (j=0; j < n-i; j++){ //el recorrido
         if (A[j] > A[j+1]) { //Si no están en orden
            Intercambiar( &A[j] , &A[j+1]); //Se intercambian
         }
      }
   }
}

Y por si todavía no os ha quedado claro, os dejo un vídeo dónde lo explica mediante juegos de cartas:




Algoritmo de inserción directa o método de la baraja (InsetionSort)
En este algoritmo se asume que la primera posición del vector ya está ordenado, por lo que comparamos las siguientes posiciones con sus anteriores. Si comparando una posición con su anterior, su valor es menor, intercambiarán posiciones, pero seguirá comparando el mismo valor que antes, pero con las demás posiciones. Así, hasta que todo el vector este ordenado. A continuación tenéis el código del algoritmo:

void Insercion(int A [n]) // Suponemos de 0 a n-1
{
   int i, j, v;
   for( i=1;i< n; i++) {
      v = A[i];
      j = i-1;
      while ((j>=0) && (A[j]>v)) {
         A[j+1]=A[j];
         j--;
      }
      A[j+1]= v;
   }
}

Si todavía seguís con dudas, os dejo un vídeo de la misma temática que el anterior:




Ordenación por selección directa (SelectionSort)
Este algoritmo es bastante fácil de entender. Busca dentro del vector el valor más bajo posible y lo intercambia con el de la primera posición. Después busca, en los valores que quedan por colocar, el más bajo y lo intercambia con el siguiente del que hemos colocado antes. Y así hasta que todo el vector este ordenado. A continuación tenéis el código de este algoritmo:

void Seleccion(int A[n])
{
   int i, j, iaux;
   for ( i = 0; i < n - 1; i++){
      int posMin = i;
      for ( j = i+1; j < n; j++){
         //si este es menor aun
         if (A[j] < A[posMin]){
            posMin = j;
         }
      }
      //intercambiar la posición i y el
      //mínimo encontrado
      iaux = A[i];
      A[i] = A[posMin];
      A[posMin] = iaux;
   }
}

Si aún no entendéis la mecánica del algoritmo, lo entenderéis mejor con el siguiente vídeo:




Vídeos | La tecla de Escape