Algoritmos de ordenamiento I. Sucesión y Burbuja


A lo largo del artículo veremos algunos de los principales tipos de ordenamientos que se utilizan en la programación, y cuan útiles pueden sernos.

¿Qué es ordenar?

Es la acción de ubicar ciertos elementos, que cuentan con un valor comparativo, en la posición que le correspondería en un listado.

A partir de este punto, les dejo la siguiente pregunta ¿Cómo ordenarías este listado de números enteros?

5 2 1 3 4

Seguramente el método que utilizaste fue observar cada elemento y seleccionaste el menor de ellos, hecho esto, el menor encontrado, lo ubicaste en la primera posición y continuaste buscando a partir de la segunda el segundo elemento más pequeño, y así sucesivamente hasta que el listado quedó totalmente ordenado.

Pues este método que la mayoría utilizamos inconscientemente, es uno de las formas utilizadas en la programación para ordenar un listado de elementos. Pero, ¿Existen otros métodos?, pues sí, existen disímiles maneras de ordenar un listado, y se diferencian tanto en la forma de realizar el procedimiento como en la eficiencia de dicho procedimiento.

Estas otras formas las veremos más adelante, pero primero debemos conocer las principales características con las que cuenta un algoritmo de ordenamiento:

  • Estables: Se dice que son estables, cuando una vez ordenado el listado, los elementos que tienen igual valor, quedan en el mismo orden en que se encontraban en el listado original. En caso contrario se dice que el algoritmo no es estable.
  • Complejidad: La complejidad de un algoritmo está dada por la cantidad de iteraciones que realiza una vez que es utilizado. La complejidad, generalmente se mide tomando el peor de los casos, que sería en donde el algoritmo tiene que hacer la mayor cantidad de iteraciones. A partir de este dato podemos comparar los diferentes métodos de ordenamientos, en más o menos rápidos que otros.

Pues una vez que conoces estos datos, podemos comenzar a ver los métodos de ordenamiento más utilizados, y los iremos explicando desde los más fáciles hasta los más complejos. En este primer artículo los algoritmos que veremos serán:

  • Ordenamiento Mínimo sucesivo
  • Ordenamiento Burbuja

Mínimo sucesivo

Este es el primer método que veremos, dado que fue el analizado al principio del artículo y además es uno de los más fáciles de entender. En esencia su funcionamiento es ir buscando los menores elementos de las sub-listas y colocarlos al principio.

Por cada operación, la nueva sub-lista a ordenar será la sub-lista anterior menos el elemento que ha sido ordenado. Este método tiene la característica de no ser estable, dado que mientras vamos realizando las operaciones, podemos intercambiar el orden original de elementos iguales, a continuación les muestro un ejemplo.

Algoritmo mínimo sucesivo

Fig1: Algoritmo mínimo sucesivo

Como podemos ver en la imagen, inicialmente el 4 rojo estaba primero que el 4 verde, pero al aplicar el algoritmo ambos quedan intercambiados. A continuación te muestro el código de este método en el lenguaje de programación C++.

int main(){

  int cantidad, lista[1000];
  cin >> cantidad; //Leer la cantidad de elementos a ordenar

  for(int i=0; i<cantidad; i++)
    cin>>lista[i]; //Leer los elementos de la lista

  //Se aplica el ordenamiento
  for(int i=0; i<cantidad; i++)
    for(int j=i+1; j<cantidad; j++)
    /*
      Si el elemento en la posición j es menor que el elemento
      en la posición i, se intercambian
    */
      if(lista[i] > lista[j])
        swap(lista[i],lista[j]);

  // Se muestra el listado final
  for(int i=0; i<cantidad; i++)
    cout << lista[i] << " ";
  
  cout << endl;

  return 0;
}

Para calcular la complejidad de este algoritmo es necesario ver los ciclos que se utilizan en el mismo, por tanto al tener un ciclo para recorrer la lista posición por posición, esto nos hace el algoritmo de complejidad N, donde N es la cantidad de elementos de la lista, pero como por cada posición recorrida tenemos que buscar el elemento que debería ir en esa posición, entonces esto es otro ciclo de complejidad N, por lo que se puede deducir que la cantidad máxima de iteraciones que hace el algoritmo va a ser N^2 iteraciones para el peor de los casos.

Ordenamiento Burbuja

A continuación te muestro otro algoritmo sencillo de complejidad cuadrática, pero, ¿Cómo funciona este método?.

El método burbuja se basa en recorrer N veces la lista original e ir intercambiando los elementos adyacentes que no cumplan con la condición de estar ordenados (es decir que el de la izquierda, no sea menor que el de la derecha), esta operación se realiza N veces (N es la cantidad de elementos de la lista) y al terminar el listado queda completamente ordenado.

En la siguiente imagen te muestro cómo se va ordenando la lista en cada iteración.

Algoritmo burbuja

Fig2: Algoritmo burbuja

Como puedes ver, este método sí es estable, dado que los elementos iguales, quedan en el mismo orden en que estaban inicialmente, y es apreciable al igual que el algoritmo anterior la complejidad, dado que hay que hacer N recorridos y por cada uno N comparaciones, dándole al método una complejidad de N^2 iteraciones en el peor de los casos.

A continuación te muestro el código de este método en el lenguaje de programación C++.

int main(){

    int cantidad, lista[1000];
    cin >> cantidad;  //Leer la cantidad de elementos a ordenar

    for(int i=0; i < cantidad; i++)  
      cin >> lista[i]; //Leer los elementos de la lista
    
    for(int i = 0; i < cantidad; i++) 
        //Aplicar ordenamiento
        for(int j = 0; j < cantidad-1; j++)
          //Si el elemento en j+1 es menor que el elemento en j, se intercambian             
          if(lista[j] > lista[j+1]) 
            swap(lista[j],lista[j+1]);
    
    //se muestra el listado final
    for(int i = 0; i < cantidad; i++) 
      cout << lista[i] << " ";    
    
    cout<<endl;

    return 0;
}

Conclusiones

Los métodos que hemos visto a lo largo del artículo son a modo de resumen, los métodos de complejidad cuadrática más conocidos, aunque existen otros que no hemos mencionado.

En próximos artículos, veremos algoritmos más eficiente de ordenamiento, donde sus complejidades para el peor de los casos son de N*log(N) iteraciones, pero con un funcionamiento mucho más complejo.

Bueno esto es todo por ahora, espero los métodos vistos les sirvan en futuros proyectos y cualquier duda o sugerencia que puedan tener con respecto a lo visto, pueden dejarla en los cometarios. Hasta la próxima.