Introducción

Cuando comenzamos a estudiar algoritmos, uno de los temas más recurrentes para ejemplificar la materia es la ordenación de datos. Básicamente se trata de, partiendo de una lista con elementos dispuestos al azar, encontrar la forma de procesarla para devolverla ordenada.

Para esto, existen varios tipos de algoritmos diferentes que resuelven el problema a través de distintos acercamientos; estudiarlos es una buena forma de entender cómo se diseñan y cómo se mide el rendimiento de los mismos según cada uno de los escenarios posibles en los que pueden aplicarse.

En este artículo, repasaremos tres métodos muy conocidos de ordenación diferentes: bubblesort, selectionsort e insertionsort.

Cada uno de estos tres algoritmos se resuelven por iteración y, ya que son muy sencillos de codificar, se los considera como métodos simples. Pasemos sin más a estudiar cada uno de ellos para descubrir cuál(es) es el más interesante a la hora de implementarlo en un proyecto.

Preparando el terreno

Por lo general, todos los algoritmos de ordenación funcionan de una forma similar. Toman una lista de elementos, en nuestro caso un array, comparan sus elementos siguiendo una estrategia definida y, según el resultado de dicha comparación, mueven los datos de un lugar a otro hasta conseguir una lista (array) final ordenado.

Teniendo en cuenta lo anterior, un punto clave de nuestros métodos será mover valores entre los índices del array que queremos ordenar. Es decir, necesitaremos una función para intercambiar los valores de un array entre dos posiciones dadas.

Como no tenemos en Javascript una función similar, crearemos una. Por seguir la convención, llamaremos a nuestra función swap y aceptará tres parámetros: el array sobre el que actuamos y los índices de aquellos dos elememtos que queremos intercambiar. Su codificación es muy simple:

/**
 * @function
 * @name swap
 * @description Swap two elements in an array
 * @param {array} myArr The target array.
 * @param {int} indexOne The index of the first element to swap.
 * @param {int} indexTwo The index of the second element to swap.
 * @returns {array} The array with the two elements swapped.
 */
function swap(myArr, indexOne, indexTwo){
  var tmpVal = myArr[indexOne];
  myArr[indexOne] = myArr[indexTwo];
  myArr[indexTwo] = tmpVal;
  return myArr;
}

He comentado la función siguiendo la convención JSDoc para que resulte más clara. Como podemos ver, no realizo comprobación de tipos ni si existen los índices que se pretenden intercambiar. No es el objetivo de este artículo.

Una rápida demostración de su funcionamiento sería:

var myArr = ['a', 'b', 'c', 'd'];
console.log( swap( myArr, 0, 1) ); // ["b", "a", "c", "d"]

Nuestra función hace el trabajo que se le espera: ha tomado los índices 0 y 1 del array para devolver uno nuevo con esos valores intercambiados. Un poco más adelante, afinaremos esta función para que ofrezca un mejor rendimiento.

Estamos listos para comenzar a implementar nuestros métodos de ordenación de datos!

Bubble Sort (u ordenamiento por burbuja)

Imaginemos que estamos en un parque con nuestra familia y queremos hacer una foto en la que salgan todos. Decidimos que podemos ordenarlos según sus edades de tal modo que tengamos al más joven a la izquierda y al más mayor a la derecha. Sin embargo, como no les hemos dicho nada, se han colocado de forma aleatoria:

Para aplicar un ordenamiento de tipo burbuja a este conjunto de elementos, tenemos que prestar atención a las dos primeras personas de la izquierda. Le preguntamos a cada uno por su edad y, si la que está a la izquierda es mayor que la de su derecha, intercambiamos sus posiciones. En el caso contrario, no hacemos nada ya que se encontrarían ordenados de forma relativa entre ellos.

En nuestro ejemplo, la persona de la izquierda es mayor que la de su derecha por lo que tenemos que realizar el primer intercambio:

Ahora fijamos nuestra atención en la segunda y tercera posición para repetir el proceso anterior: preguntamos por sus edades e intercambiamos posición si fuera necesario. En nuestro ejemplo, no tenemos que realizar ahora ningún intercambio, por lo que avanzaríamos para comparar la tercera y cuarta posición entre ellas. De nuevo, están ya ordenados de forma relativa puesto que la persona de la derecha, es mayor que la de su izquierda.

Avanzamos sin alterar nada hasta comparar la cuarta persona con la quinta. Ahora si nos volvemos a encontrar con que la persona de la izquierda es mayor que la derecha, por lo que es necesario un nuevo intercambio:

Hemos completado una vuelta sobre nuestro conjunto y de momento estamos aún lejos de tenerlo ordenado. Sin embargo, si que hemos conseguido algo importante: el elemento de la derecha está ya ubicado en su posición final; es decir, que como si de una burbuja se tratase, el elemento más grande (en este caso la persona más mayor) ha ido bullendo hasta su posición final.

El siguiente paso, sería volver a repetir el proceso ignorando la persona (el elemento) que está a la derecha del conjunto (puesto que ya está en su posición final).

Comparamos ahora la dos primeras posiciones y observamos que están ya ordenadas, por lo que pasamos directamente a comparar la segunda con la tercera posición. De nuevo tenemos los elementos ordenados de forma relativa entre ellos por lo que pasariamos evaluar la tercera y cuarta posición.

Llegados a ese punto, observamos que la persona de la izquierda es mayor que la de su derecha, por lo que intercambiamos posiciones obteniendo:

Hemos completado la segunda vuelta; comenzamos de nuevo e ignoramos ahora los dos últimos elementos. Finalmente, tras todas las iteraciones posibles, obtenemos:

Una vez que hemos comprendido cómo funciona, es hora de implementarlo en código.

La idea tras este algoritmo es que, a cada iteración por el conjunto, un elemento es llevado hasta su posición final y tiene que ser por lo tanto ignorado en las siguientes. Esto se traduce en que, a cada paso, se debe compara un elemento menos que en el anterior. Si N es el número de items en la lista, entonces en la primera iteración necesitamos comparar N – 1; en la segunda, N – 2, y así sucesivamente. Este tipo de códigos basado en bucles dependientes se resuelven muy fácilmente:

function bubbleSort(myArr){
  var size = myArr.length;
 
  for( var pass = 1; pass < size; pass++ ){ // outer loop
    for( var left = 0; left < (size - pass); left++){ // inner loop
      var right = left + 1;
      if( myArr[left] > myArr[right] ){
        swap(myArr, left, right);
      }
    }
  }
 
  return myArr;
}

El código anterior, resulta muy sencillo de seguir. Un bucle externo recorre nuestro array tantas veces como elementos tenga menos uno. El bucle interno compara cada uno de los valores que encuentra (left) con aquel que inmediatamente posterior (right). Si left es mayor que right, se intercambia la posición y se continúa con el siguiente par.

Comprobamos nuestro código anterior con un array simple:

var myArr = ['d', 'f', 'd', 'c', 'a', 'e', 'b'];
console.log( bubbleSort( myArr ) ); // ["a", "b", "c", "d", "d", "e", "f"]

La función nos devuelve nuestro array ordenado aunque, como seguramente intuimos, es probable que estemos realizano un alto número de iteraciones para ello…

Más adelante, mediremos el rendimiento de este algoritmo para compararlo con los dos restantes.

Selection sort (u ordenamiento por selección)

Imaginemos que tenemos una estanteria llena de libros de diferente tamaño (altura). Como no hemos seguido ningún criterio a la hora de colocarlos, están dispuestos de forma aleatoria y nos gustaría cambiar esto. Querríamos tenerlos colocados según su tamaño de tal modo que en el extremo izquierdo tuviéramos al más alto y en el derecho al más bajo.

Sin embargo, son libros pesados y no parece interesante estar desplazándolos uno a uno como en el caso anterior. Lo ideal sería revisar todos los libros, seleccionar el siguiente según el orden que hemos establecido y colocarlo directamente en su posición final. Esta selección que da nombre al algoritmo permite tomar un elemento y desplazarlo en un único movimiento a su posición definitiva.

En varias ocasiones, mientras escaneamos los libros, encontraremos que éstos están ya en su posición final y que no es necesario moverlos. También notaremos que tras cada movimiento, el conjunto de libros ordenados crece mientras que el de los desordenados disminuye lo que muestra el patrón que permite concluir el proceso.

La secuencia completa para ordenar el resto de los libros sería el siguiente:

Como hemos comentado más arriba, en este tipo de ordenaciones, a diferencia de lo que ocurre con el método de burbuja, podemos encontrarnos continuamente con que un elemento ya está ordenado y no requiere de ese intercambio. Para ahorrar ese paso, modificaremos ligeramente la función swap:

function swap(myArr, indexOne, indexTwo){
  if( indexOne == indexTwo ){
    return myArr;
  }
  var tmpVal = myArr[indexOne];
  myArr[indexOne] = myArr[indexTwo];
  myArr[indexTwo] = tmpVal;
  return myArr;
}

Ahora estamos comprobando que las posiciones a intercambiar no sean la misma y, por tanto, estemos realizando una operación inútil.

La implementación del selection sort se construye a partir de un buble externo y otro interno, como en el anterior, pero con sutiles diferencias.

En primer lugar, el exterior recorre los valores entre cero y N-2 en lugar de entre 1 y N-1. Aunque en realidad se trate finalmente del mismo número de pasos (N-1), operamos directamente sobre los slots para enviar ahí el valor correcto en cada una de las iteraciones. Por ejemplo, en el primer paso, nuestro objetivo es desplazar el elemento correcto hasta la posición cero; en el segundo, nuestro objetivo es rellenar la posición 1, y así sucesivamente.

De nuevo, necesitamos un número de iteraciones N-1 puesto que tras cada ciclo, tendremos un elemento ubicado en su posición definitiva que podemos ignorar.

El código sería el siguiente:

function selectionSort( myArr ){
  var size = myArr.length;
  for( var slot = 0; slot < size -1; slot ++ ){ // outer loop
    var smallest = slot;
    for( var check = slot + 1; check < size; check++ ){ // inner loop
      if( myArr[check] < myArr[smallest] ){
        smallest = check;
      }
    }
    swap( myArr, smallest, slot );
  }
  return myArr;
}

Lo probamos:

var myArr = ['d', 'f', 'd', 'c', 'a', 'e', 'b'];
console.log( selectionSort( myArr ) ); // ["a", "b", "c", "d", "d", "e", "f"]

Como ocurría con el método anterior, un simple vistazo a la lógica del código nos puede poner sobre la pista de que quizá, hacemos más comparaciones de las que podrían ser necesarias. Eso por no entrar en la complejidad ciclomática de tres niveles que presenta.

Insertion Sort (u ordenación por inserción)

Este algoritmo es muy similar al que utilizaríamos para ordenar las cartas en una mano de póquer a medida que nos las van sirviendo.

La idea tras este concepto es la siguiente:

• Separamos según los palos en el siguiente orden: picas, tréboles, diamantes y corazones.
• Por cada uno de esos palos, ordenamos de forma ascendiente: As, 2, 3, …, 9, 10, jota, reina y rey.

La siguiente sucesión de imágenes nos mostraría el proceso de ordenación según fuéramos descubriendo cartas:

Inicialmente se tiene un solo elemento, que obviamente es un conjunto ordenado. Después, cuando hay K elementos ordenados de menor a mayor, se toma el elemento K + 1 y se compara con todos aquellos ya ordenados, deteniéndose cuando se encuentra uno menor (todos los elementos mayores han sido desplazados una posición a la derecha). En este punto se insertaría el elemento K + 1 desplazándose al resto.

Avanzando en el ejemplo anterior, la siguiente carta se ordenaría siguiendo el mismo criterio:

El resto de la secuencia sería:

El código sería el siguiente:

function insertionSort( myArr ) {
  var size = myArr.length,
      slot,
      tmp;
 
  for ( var item = 0; item < size; item++ ) { // outer loop     
    tmp = myArr[item];
    for ( slot = item - 1; slot >= 0 && myArr[slot] > tmp; slot-- ){ // inner loop
      myArr[ slot + 1 ] = myArr[slot];
    }
    myArr[ slot + 1 ] = tmp;
  }
  return myArr;
};

Y la comprobación de rigor:

var myArr = ['d', 'f', 'd', 'c', 'a', 'e', 'b'];
console.log( insertionSort( myArr ) ); // ["a", "b", "c", "d", "d", "e", "f"]

Es cierto que este código es más difícil de seguir a simple vista y quizá no seamos capaces de advertir qué nivel de complejidad presenta. Pero no hay problema; ha llegado el momento de medir cada uno de los métodos anteriores y comparar los resultados.

Comparando los algoritmos de ordenación básicos

Una vez que hemos presentado algunos de estos algoritmos básicos, vamos a analizar su rendimiento de un modo práctico. Esta comparación no será definitiva en tanto a qué método escoger independientemente del escenario, sino que supone un ejemplo de cómo implementar un sistema de métrica sencillo sobre un código a evaluar.

Para ello, debemos contemplar los tres escenarios clave a la hora de medir un algoritmo de ordenación:

• Todos los datos se encuentran de partida ya ordenados (el mejor de los casos).
• Todos los datos se encuentran de partida ya ordenados pero en sentido inverso al deseado (el peor de los casos).
• Los datos se encuentran dispuestos en cualquier orden (el caso más habitual).

Para simular cada uno de estos estados, crearemos 3 listas diferentes de 1000 elementos sobre la que aplicaremos nuestros algoritmos y sus mediciones:

var TEST_SIZE = 1000,
    sortedArr = [],
    reverseArr = [],
    randomArr = [];
 
for( var x = 1; x0; x-- ){
  reverseArr.push(x);
}
 
for( var x = 1; x

Con nuestros arrays preparados, nos falta implementar algún tipo de contador para medir el número de iteraciones que realizan nuestros algoritmos. Para ello, nos valdremos de una variable contadora que introduciremos en el interior (inner loop) de cada una de nuestras funciones:

var counter = 0;
 
function bubbleSort(myArr){
  var size = myArr.length;
  counter = 0;
 
  for( var pass = 1; pass < size; pass++ ){ // outer loop
    for( var left = 0; left < (size - pass); left++){ // inner loop       
      var right = left + 1;
      counter++;
      if( myArr[left] > myArr[right] ){
        swap(myArr, left, right);
      }
    }
  }
  console.log('Bubble Sort: ', counter );
  return myArr;
}
 
function selectionSort( myArr ){
  var size = myArr.length;
  counter = 0;
 
  for( var slot = 0; slot < size -1; slot ++ ){ // outer loop
    var smallest = slot;
    for( var check = slot + 1; check < size; check++ ){ // inner loop
      counter++;
      if( myArr[check] < myArr[smallest] ){
        smallest = check;
      }
    }
    swap( myArr, smallest, slot );
  }
  console.info( 'Selection  Sort: ', counter );
  return myArr;
}
 
function insertionSort( vector ) {
  var innerCounter = 0;
  counter = 0;
  for (var i=1; i < vector.length; i++) {
    var temp = vector[i];
    var j = i-1;
    counter++;
    while (j >= 0 && vector[j] > temp) {
      innerCounter++;
      vector[j + 1] = vector[j];
      j--;
    }
    vector[j+1] = temp;
  }
  console.info('Insertion Sort: ', innerCounter || counter );
  return vector;
};

El contador de la función insertionSort es diferente a los otros dos ya que aquí puede darse el caso (improbable) de que no se entre en el bucle interno. Esto pasaría, efectivamente, si la lista que manejáramos correspondiese a la que hemos etiquietado como el ‘mejor caso’; es decir, donde todos sus elementos estuviesen ya ordenados.

Con nuestros contadores ya preparados, solo tenemos que ejecutar los algoritmos de ordenación sobre cada uno de los arrays que hemos preparado antes. El resultado que obtenemos es el siguiente:

bubbleSort( sortedArr ); // 499500
bubbleSort( reverseArr ); // 499500
bubbleSort( randomArr ); // 499500
 
selectionSort( sortedArr ); // 499500
selectionSort( reverseArr ); // 499500
selectionSort( randomArr ); // 499500
 
insertionSort( sortedArr ); // 999
insertionSort( reverseArr ); // 499500
insertionSort( randomArr ); // 257994

Tenemos varios datos interesantes en estas mediciones:

• La ordenación por burbuja y por selección relaizan siempre el mismo número de comparaciones.
• El número de comparaciones que requieren la ordenación por burbujas y por selección es independiente del estado de los datos de entrada.
• El número de comparaciones requeridas por el algoritmo de inserción es muy sensible al estado inicial de los datos. En el peor de los casos, requiere el mismo número de comparaciones que los otros; en el mejor, le basta con una iteración menos que el número total de elementos que contiene el array.

Lo más importante de los datos anteriores es que tanto la burbuja como la selección son insensibles al estado de los datos. Pueden considerarse así como algoritmos de «fuerza bruta» en oposición a la inserción que puede describirse como adaptable: si precisa menos trabajo, realiza menos trabajo.

Conclusión

Tras los datos arrojados por los métodos anteriores, podemos hacernos una idea de como rinden estos métodos básicos que hemos presentado. Sin embargo, hay que tener cuidado con no extraer más conclusiones de la cuenta.

Para realmente conocer la diferencia entre sus comportamientos, deberíamos también medir diferentes escenarios como cuánto afecta el número de objetos que componen cada lista de forma precisa (esto sería la escalabilidad) y el tiempo de ejecución real de cada sistema de ordenación (el coste de CPU).

Como idea final, podemos obtener que, por lo general, un algoritmo de inserción realiza, como mínimo, un trabajo similar al de la burbuja o la selección. Para la gran mayoría de escenarios, sin embargo, su rendimiento se demuestra muy superior y, por tanto, resulta una opción mejor.

Para la segunda parte de este artículo, estudiaremos algoritmos avanzados como el shellsort, el célebre quicksort o el potente mergesort. Al igual que con los básicos, realizaremos métricas sobre su rendimiento para tener una primera impresión sobre cuál es el método más adecuado para cada uno de los posibles escenarios que pueden presentarse.