Lic. En Turismo

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 distintosacercamientos; 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 muysencillos 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 unaestrategia 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 notenemos 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 targetarray.
* @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ónsiguiendo 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 laque 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 acada 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...