• Algoritmo Burbuja
• Algoritmo QuickSort

Burbuja

Un algoritmo clásico de ordenamiento es el llamado algoritmo Burbuja. Este es un método bastante intuitivo pero muy lento comparado al QuickSort. Presentamos este otro algoritmo como una alternativa y con fines de estudio. Sin embargo, nuestro consejo es utilizar el QuickSort siempre que se pueda ya que el el Burbuja es extremadamente lento con respecto al QuickSort. Para mayores detalles vea la sección de Complejidad Computacional.

La idea de este algoritmo es ir seleccionando el mayor valor del arreglo y colocarlo al final, después seleccionar el segundo mayor y colocarlo en penúltimo lugar y así sucesivamente... Supongamos que tenemos una lista de tamaño N. Pensemos que deseamos colocar el entero de mayor valor al final del arreglo. Un método que podemos emplear (para no guardar índices ni valores máximos) es recorrer el arreglo con un índice i desde 0 hasta N - 2. En cada iteración checamos si el entero en la posición i + 1 es menor que el entero en posicion i, de ser así, entonces intercambiamos los valores de las posiciones i + 1 e i. Con este proceso hemos enviado el entero de mayor valor a la posición N - 1. Si volvieramos aplicar este proceso al arreglo resultante, entonces tendríamos los dos enteros de mayor valor se encuentran en la última y penúltima posición. Es fácil generalizar la idea si queremos ordenar los N elementos. Empleamos dos for con los índices adecuados.

Un ejemplo sencillo de 6 números es el arreglo {5,7,11,3,2,4} si aplicamos el método de arriba mencionado entonces tenemos:

Como podemos ver, el 11 es arrastrado (como si una burbuja subiera desde el fondo del agua) hasta el final una vez que se ha topado con él. Si volvieramos a repetir el proceso, entonces nos topariamos con el 7 y este subiría hasta el penúltimo lugar (ya que el mayor está en el último). Así podriamos realizar N - 1 iteraciones. En general el algoritmo quedaría como:

void Intercambia(int *A,int Pos1,int Pos2)
{
int Temp = A[Pos2];
A[Pos2] = A[Pos1];
A[Pos1] = Temp; 
}

///********************************

void Burbuja(int *A,int N)
{
int i,j,Temp;

// Repetimos el procesos N - 1 veces para un arreglo de tamaño N.
for(i = 0; i < (N-1); i++)
  {
  // En cada iteración llegamos hasta N - 1 - i pues hemos ordenado
  // a i enteros en los i iteraciones pasadas.
  for(j = 0; j < (N - 1 - i); j++)
    {
    // Comparamos e intercambiamos de ser el caso.
    if( A[j + 1] < A[j] )
      { Intercambia(A,j,j+1); }
    }
  }
}

Ir al índice

QuickSort

Uno de los algoritmos más poderosos en ordenamiento es precisamente el algoritmo llamado QuickSort. Su filosofía es dividir el problema (de manera recursiva) en dos problemas de menor tamaño y con ello disminuir la complejidad del problema.

Alguien dijo "Divide y Venceras", eso es justamente lo que hace el QuickSort ya que dado un arreglo de valores (en nuestro caso supondremos que son enteros), escoge un valor al cual llamaremos Pivote y divide todos los demás elementos en dos listas, en una se colocan todos aquellos números que son menores o iguales al Pivote y en la otra lista se dejan los que son iguales mayores al Pivote. La forma en que se hace esta separación es muy ingeniosa.

Digamos que deseamos ordenar un arreglo en el intervalo Ini y Fin. Es decir, sólo consideramos los elementos contenidos en ese intervalo (inclusive los elementos Ini y Fin). Para separar, empléamos dos índices: F e I. El primero recorre la lista desde Ini hasta Fin y F en sentido inverso. Para el índice I se selecciona el primer elemento que es menor (mayor en el caso del índice F) al Pivote. Una vez que se cuenta con estos elementos, se intercambia el elemento de la posición I por el de la posición F y avanzan los índices (F disminuye e I aumenta). Este proceso se repite hasta que I > F, cuando eso sucede quiere decir que la lista se ha separado en dos partes. La primera que va desde Ini hasta F y la segunda desde I hasta Fin. En la parte tenemos valores que son menores o iguales al Pivote mientras que en la segunda tenemos los valores que son mayores o iguales al Pivote. Por lo tanto, llamamos de manera recursiva al Quicksort pero con sendos extremos como parámetros.

void intercambia(int *array,int pos1,int pos2)
{
int temp = array[pos2];
array[pos2] = array[pos1];
array[pos1] = temp; 
}

///********************************

void quickSort(int *array,int ini,int fin)
{
if( ini >= fin ) 
  { return; }
  
int i, f, pivote, Temp;

// Establecemos los extremos temporales y el pivote.
i = ini;
f = fin;
pivote = array[(ini+fin)/2];

do
 {
 // Buscamos el primer elemento de izquierda a derecha que sea mayor
 // al pivote.
 while( array[i] < pivote )
   { i++; }

 // Buscamos el primer elemento de derecha a izquierda que sea menor
 // al pivote.
 while( array[f] > pivote )
   { f--; }

 if( i <= f )
   {
   // Intercambiamos los extremos.
   intercambia(array,i,f);
   
   // Aumentamos los contadores.
   i++; 
   f--;
   }
 } while (i < f);

// Una vez hecha la partición llamamos recursivamente al Quicksort.
quickSort(array,ini,f);
quickSort(array,i,fin);
}

Ir al índice

Estadísticas

Regresar