Un algoritmo es por definición un conjunto ordenado (esto es muy importante) de operaciones sistemáticas que nos permite hacer un cálculo para hallar la solución de todos los problemas de un mismo tipo. Es decir es un conjunto de instrucciones que siempre sigue el siguiente patrón:
- Precisión: Tiene que explicar de manera única e inequívoca cada paso o instrucción.
- Finito: El número de instrucciones a ejecutar debe ser limitada.
- Definición: Los mismos datos de entrada siempre deben proporcionar la misma información de salida.
- Entrada: El número de elementos de entrada puede ser cero o más.
- Resolución: Siempre debe producir un resultado, que será el o los datos de salida.
Cuando un algoritmo se implementa en un determinado lenguaje de programación se convierte en un programa el cual se puede ejecutar en un ordenador, por lo tanto podemos decir que un programa es un algoritmo o conjunto de algoritmos escritos en un lenguaje concreto para que la computadora los pueda interpretar. En dicho caso este programa se llama algoritmo computacional. En cambio si no necesita una computadora para ejecutarse hablamos de algoritmos no computacionales.
En nuestro caso vamos a hablar de algoritmos computacionales.
Sabiendo lo que es un algoritmo nos vamos a centrar en los algoritmos de ordenación, o lo que es lo mismo, el algoritmo que sirve para ordenar y devolvernos ya ordenada una lista que se ha proporcionado inicialmente con elementos colocados al azar.
Los 3 algoritmos de ordenación más conocidos son Bubble sort u ordenación por burbuja, Selection sort u ordenación por selección e Insertion sort u ordenación por inserción. Todos ellos son considerados algoritmos o métodos simples ya que se resuelven por iteración o repetición hasta un número n de veces.
Array = (4, 7, 8, 5, 9);
Queremos que nos lo devuelva ordenado de mayor a menor por ejemplo, o sea (9, 8, 7, 5, 4).
Para ello lo primero que tenemos que hacer es preguntar a los dos primeros valores cual es el mayor. En caso de que el segundo valor sea mayor que el primero, como es el caso, habría que intercambiarlos, en cambio si ya están ordenados, los dejamos como están.
Después habría que repetir el mismo proceso con los valores segundo y tercero. En este caso es mayor el tercer valor asique lo intercambiaríamos, quedando nuestro array = (7, 8, 4, 5, 9).
Después volvemos a repetir el paso anterior con los valores tercero y cuarto, y de nuevo los intercambiamos. (7, 8, 5, 4, 9).
Y por último después de la primera iteración quedaría: (7, 8, 5, 9, 4).
Sigue sin estar ordenado, sin embargo se ha conseguido que el último elemento, el de la derecha del todo, el 4, si quede ordenado como el número menor de todos.
En la siguiente vuelta para ordenar nuestro array ya no es necesario tener en cuenta el último porque ya sabemos que está ordenado, asique compararíamos primer y segundo elemento, después segundo y tercer elemento, y por último tercer y cuarto elemento y quedaría el array: (8, 7, 9, 5, 4).
Ahora ya están ordenados el último y penúltimo elemento.
Volvemos a hacer otra vuelta comparando los valores primero y segundo y después segundo y tercero y el array queda así: (8, 9, 7, 5, 4).
Ya están ordenados los tres últimos elementos por lo que solo es necesaria una vuelta más para dejar el array completamente ordenado: (9, 8, 7, 5, 4).
Así funciona el algoritmo burburja, que se llama así porque en cada vuelta el último elemento va subiendo como una burbuja y queda ordenado.
Ahora implementado a JavaScript es muy sencillo:
function burburja (myArray){ var tam = myArray.length; for ( var temp =1; temp < tam; temp++) { for (var izq = 0; izq< (tam - temp); izq++) { var dcha = izq+1; if (myArray[izq] < myArray[dcha] { ordenar(myArray, izq, dcha); } } }return myArray;}Pasamos un array a nuestra función y dentro de ella lo primero que hacemos es calcular su tamaño, calcular el número de elementos del array.Después creamos un bucle externo que recorra nuestro array tantas veces como elementos tenga menos uno (ya que son las veces necesarias para que quede completamente ordenado).
Internamente creamos otro bucle que recorre los valores comparando cada uno con el siguiente y si el de la izquierda es menor que el de la derecha los intercambia con la función ordenar que veremos a continuación.
Por último nos devuelve el array ordenado.
function ordenar(myArray, valor1, valor2){ var temp = myArray[valor1]; myArray[valor1] = myArray[valor2]; myArray[valor2] = temp; return myArray;}donde valor1 es el índice del primer elemento a intercambiar y valor2 es el índice del segundo elemento a intercambiar.
En el mismo ejemplo de antes Array = (4, 7, 8, 5, 9) si queremos ordenarlo de mayor a menor por ejemplo, primero seleccionaría el 9 y lo pondría en el primer lugar y el 4 ocuparía la última posición (9, 7, 8, 5, 4). En la segunda vuelta seleccionaría el 8 y lo intercambiaría con el 7 para quedarse en la posición correcta. En las siguientes vueltas no modificaría nada ya que ya ha quedado ordenado.
El código de este algoritmo quedaría de la siguiente forma:
function selección(myArray){ var tam = myArray.length; for ( var temp =0; temp < tam -1; temp++) { mayor = temp; for (var comprobar = temp + 1; comprobar < tam; comprobar++) { if (myArray[comprobar] < myArray[mayor] { mayor = comprobar; } } ordenar(myArray, mayor, comprobar); }return myArray;}
El código funciona similar al de la burbuja pero el bucle for externo va recorriendo los valores desde 0 hasta N-2 (son el mismo número de pasos que entre 1 y N-1 como en el burbuja pero el funcionamiento es diferente) operando directamente sobre los elementos para llevarlos a la posición correcta en cada vuelta.
El número de vueltas necesarias para que todos los elementos queden ordenados es igual que en el de burbuja N-1, ya que tras cada iteración dejamos un elemento colocado un su lugar y el que podremos ignorar en las siguientes vueltas.
Sin embargo la función ordenar la modificamos ligeramente para ahorrarnos los pasos cuando nos encontramos con que algún elemento ya está ordenado:
function ordenar(myArray, valor1, valor2){ if (valor1 ==valor2) { return myArray; } var temp = myArray[valor1]; myArray[valor1] = myArray[valor2]; myArray[valor2] = temp; return myArray;}Para conseguirlo hemos incluido un bucle if en el que compruebe si coinciden los valores, es decir si ya están ordenados.
Este algoritmo de inserción tiene un funcionamiento similar al de la colocación de una mano de cartas en una partida de póquer según se van repartiendo las cartas.
Habitualmente ordenamos las cartas por palos, y dentro de ellos por su orden ascendente de la siguiente manera:
Primero se reparte una carta, un solo elemento el cual está ordenado (por ser único). Después cuando hay “j”elementos ordenados de menor a mayor tomamos el elemento j+1 y lo comparamos con todos los elementos que ya están ordenados. Si se encuentra con uno menor, pues los mayores se habrán desplazado a la derecha, se inserta dicho elemento (j+1) desplazándose al resto.
El algoritmo de inserción traducido al lenguaje de JavaScript queda de la siguiente forma:
function inserción(myArray){ var tam = myArray.length, temp, lugar; for ( var obj =0; obj < tam; obj++) { temp = myArray[obj]; for (lugar = obj - 1; lugar >= 0 && myArray[lugar] > temp; lugar--) { myArray[lugar + 1] = myArray[lugar]; } myArray[lugar + 1] = temp; }return myArray;}
Y así quedan definidos los tres algoritmos sencillos de ordenación y el código al implementarlo en JavaScript.
