Introducción a la clasificación de algoritmos en JavaScript
Al igual que la mayoría de los otros lenguajes de programación, puede encontrarse con escenarios en los que debe ordenar algunos números en JavaScript en orden ascendente o descendente. Para hacerlo, podemos usar muchos algoritmos, tales como clasificación de burbujas, clasificación de selección, clasificación de combinación, clasificación rápida, etc. Estos algoritmos no solo difieren en cómo funcionan, sino que cada uno tiene sus diferentes demandas en términos de memoria y tiempo, tomemos profundice en algunos de los algoritmos de clasificación importantes y vea cómo puede usarlos en su código JavaScript.
Los 6 mejores algoritmos de clasificación en JavaScript
Aquí hay algunos algoritmos de ordenación en JavaScript explicados a continuación con ejemplos:
1. Algoritmo de clasificación de burbujas
Considerada como una de las herramientas más comunes de este comercio, la ordenación de burbujas funciona creando un ciclo que compara cada elemento de la matriz con otro elemento. Si el elemento comparado es más pequeño que el disponible, intercambiamos sus lugares. Esto continúa hasta que tengamos un pase donde ningún elemento de la matriz sea más grande que el elemento que está al lado.
Bubble Sort tiene una complejidad de tiempo O (n 2 ) y una complejidad de espacio O (n).
Código:
function swap(arr, firstIndex, secondIndex)(
var temp = arr(firstIndex);
arr(firstIndex) = arr(secondIndex);
arr(secondIndex) = temp;
)
function bubbleSortAlgo(arraaytest)(
var len = arraaytest.length,
i, j, stop;
for (i=0; i < len; i++)(
for (j=0, stop=len-i; j < stop; j++)(
if (arraaytest(j) > arraaytest(j+1))(
swap(arraaytest, j, j+1);
)
)
)return arraaytest;
)
console.log(bubbleSortAlgo((3, 6, 2, 5, -75, 4, 1)));
Salida:
2. Algoritmo de clasificación de selección
Ahora que hemos terminado de discutir el Algoritmo de clasificación de burbujas, echemos un vistazo a un algoritmo popular para la clasificación llamado Clasificación de selección.
A diferencia de Bubble Sort, nos centramos en encontrar el valor más pequeño en la matriz para realizar la clasificación. Aquí hay un desglose paso a paso de cómo funciona la Selección de selección:
- Asumimos que el primer elemento de la matriz es el más pequeño.
- Comparamos este elemento con el siguiente elemento de la matriz.
- Si el siguiente elemento es más pequeño que el que tenemos a mano, establecemos el siguiente elemento como el nuevo valor más pequeño.
- Seguimos repitiendo estos pasos hasta llegar al final de la matriz.
- Cuando encontramos un valor en la matriz que es más pequeño que el que comenzamos, intercambiamos sus posiciones.
- Seguimos haciendo las comparaciones y pasando al siguiente elemento. Hasta que se ordena toda la matriz.
Al igual que el algoritmo de clasificación de burbujas, la clasificación de selección tiene una complejidad de tiempo O (n 2 ) y una complejidad de espacio O (n).
Código:
function SelectionSortAlgo(array, compare_Function) (
function comp(a, b) (
return a - b;
)
var min = 0;
var index = 0;
var temp = 0;
compare_Function = compare_Function || compare;
for (var i = 0; i < array.length; i += 1) (
index = i;
min = array(i);
for (var j = i + 1; j < array.length; j += 1) (
if (compare_Function(min, array(j)) > 0) (
min = array(j);
index = j;
)
)
temp = array(i);
array(i) = min;
array(index) = temp;
)
return array;
)
console.log(SelectionSortAlgo((9, 15, 2, 44, -1, 36, 1), function(a, b) ( return a - b; )));
Salida:
3. Algoritmo de clasificación de fusión
Similar a Bubble Sort y Selection Sort, Merge sort es uno de los algoritmos de clasificación populares en informática, puede implementarlo en la mayoría de los lenguajes de programación y tiene un buen rendimiento sin que sea demasiado necesitado de recursos.
Ordenar por fusión utiliza el método de división y conquista para ordenar una matriz o cualquier lista de elementos. El término divide y vence significa que dividimos un gran problema en varios problemas más pequeños y luego resolvemos estos pequeños problemas. Una vez que se resuelven los problemas más pequeños, combinamos los resultados que dan como resultado la solución al gran problema.
Comprender el algoritmo es simple en realidad:
- Dividimos la matriz dada en n matrices, cada una de estas matrices contiene solo 1 elemento.
- Combinar las matrices para producir una nueva matriz.
- Repita el paso 2 hasta que solo quede 1 matriz, que será la matriz ordenada.
Código:
function merge_sort_algo(left, right)
(
var i = 0;
var j = 0;
var result = ();
while (i < left.length || j < right.length) (
if (i === left.length) (
// j is the only index left_part
result.push(right(j));
j++;
)
else if (j === right.length || left(i) <= right(j)) (
result.push(left(i));
i++;
) else (
result.push(right(j));
j++;
)
)
return result;
)
console.log(merge_sort_algo((1, 44, 6), (84, 7, 5)));
Salida:
4. Algoritmo de ordenación rápida
Quicksort es una de las formas más eficientes de clasificar elementos en sistemas informáticos. Similor para fusionar ordenación, Quicksort trabaja en el algoritmo de dividir y conquistar. En esto, encontramos un elemento dinámico en la matriz para comparar todos los demás conjuntos de elementos y luego los movemos de una manera en la que todos los elementos antes de nuestros elementos dinámicos seleccionados son más pequeños y todos los elementos después del elemento dinámico son de mayor tamaño. Una vez que hayamos hecho eso, la clave es seguir haciéndolo repetidamente y tendremos nuestra matriz ordenada.
Los siguientes son los pasos que se pueden seguir para implementar el algoritmo de clasificación rápida:
- Seleccionamos un elemento de la matriz y lo llamamos "Punto de pivote"
- Comenzamos un puntero llamado puntero izquierdo desde el cual se encuentra en el primer elemento de la matriz.
- Del mismo modo, comenzamos un puntero llamado puntero derecho en el último elemento de la matriz.
- Si el valor del elemento en el puntero izquierdo es menor en comparación con el punto de pivote seleccionado, movemos el puntero izquierdo hacia la izquierda (agreguemos +1) y seguimos repitiéndolo hasta que el valor en el puntero izquierdo sea mayor que el valor del punto de pivote o igual a él.
- Si el valor del elemento en el puntero derecho de la lista es mayor que el valor del elemento pivote, modelaremos el puntero derecho a la izquierda. Repita esto hasta que el valor en el puntero del lado derecho sea menor (o igual) al valor de pivote.
- Cuando el valor del puntero izquierdo es menor o igual que el valor del puntero derecho, intercambie los valores.
- Mueva el puntero derecho a la izquierda por uno, el puntero izquierdo a la derecha por uno.
- Repita hasta que los punteros izquierdo y derecho se encuentren.
Código:
function quickSortAlgo(origArray) (
if (origArray.length <= 1) (
return origArray;
) else (
var left = ();
var right = ();
var newArray = ();
var pivot = origArray.pop();
var length = origArray.length;
for (var i = 0; i < length; i++) (
if (origArray(i) <= pivot) (
left.push(origArray(i));
) else (
right.push(origArray(i));
)
)
return newArray.concat(quickSortAlgo(left), pivot, quickSortAlgo(right));
)
)
var myArray = (13, 50, 2, 45, -1, 74, 11 );
var arreySorted = quickSortAlgo(myArray);
console.log(arreySorted);
Salida:
5. Algoritmo de clasificación de inserción
Cuando se trata de facilitar la implementación, el tipo de inserción es ampliamente conocido como uno de los algoritmos más simples. En el orden de inserción, los elementos de la matriz se comparan entre sí y luego se ordenan en un orden particular. Esto es muy similar a organizar cartas en una baraja. El tipo de inserción de nombre proviene del proceso de elegir un elemento e insertarlo en su lugar correcto y luego repetirlo para todos los elementos.
Así es como funciona el algoritmo:
- El primer elemento de la matriz se considera ya ordenado.
- Elija el siguiente elemento de la matriz.
- Compare el elemento seleccionado con todos los elementos en la matriz.
- Desplaza cada elemento de la matriz que sea mayor que el valor del elemento seleccionado.
- Insertar el elemento
- Repita los pasos 2 a 5 hasta que se ordene la matriz.
Código:
function insertion_Sort_algo(arr)
(
for (var i = 1; i < arr.length; i++)
(
if (arr(i) < arr(0))
(
arr.unshift(arr.splice(i, 1)(0));
)
else if (arr(i) > arr(i-1))
(
continue;
)
else (
for (var j = 1; j < i; j++) (
if (arr(i) > arr(j-1) && arr(i) < arr(j))
(
arr.splice(j, 0, arr.splice(i, 1)(0));
)
)
)
)
return arr;
)
console.log(insertion_Sort_algo((44, 20, 26, 54, -9, 41, 16)));
Salida:
6. Algoritmo de ordenación del montón
La ordenación en montón es una forma de ordenar elementos mediante el uso de la estructura de datos "Montón". El método es bastante similar a la técnica de selección de selección que discutimos anteriormente. Ahora puede que se esté preguntando acerca de los montones y cómo se definen, antes de llegar al algoritmo, comprendamos primero los montones.
En pocas palabras, un montón es un árbol binario con algunas reglas adicionales. Una regla establece que, en el montón, el árbol debe ser un árbol binario completo, lo que simplemente significa que es necesario llenar todos los nodos en el nivel actual antes de agregar otro. La siguiente regla para el montón es que debe haber una relación principal y secundaria definida con los valores de los elementos del montón.
En un montón mínimo, el valor de un padre debe ser menor que sus hijos. En un montón máximo, como puedes adivinar, el valor de un padre debe ser mayor que su hijo.
Ahora que las definiciones están fuera del camino, echemos un vistazo a cómo funciona el montón:
- Primero construimos un montón máximo que asegura que el elemento de mayor valor esté en la parte superior.
- Cambiamos el elemento superior con el último elemento del montón y eliminamos el elemento superior del montón y lo almacenamos en una matriz ordenada.
- Seguimos repitiendo los pasos uno y dos hasta que solo quede un elemento en el montón.
Una cosa a tener en cuenta es que los montones no son compatibles de forma nativa en JavaScript, por lo tanto, tenemos que recurrir a la implementación de montones utilizando matrices. La complejidad espacial de la ordenación del montón es O (1), que es excelente y, aunque es un poco más complicada en comparación con la ordenación por fusión o inserción en lo que respecta a la comprensión y la implementación, creo que para obtener beneficios de rendimiento, en última instancia, es mejor usarla en grandes proyectos
Código:
var arrLength;
function heapRoot(input, i) (
var left = 2 * i + 1;
var right = 2 * i + 2;
var max = i;
if (left input(max)) (
max = left;
)
if (right input(max)) (
max = right;
)
if (max != i) (
swap(input, i, max);
heapRoot(input, max);
)
)
function swap(input, index_A, index_B) (
var temp = input(index_A);
input(index_A) = input(index_B);
input(index_B) = temp;
)
function heapSortAlgo(input) (
arrLength = input.length;
for (var i = Math.floor(arrLength / 2); i >= 0; i -= 1) (
heapRoot(input, i);
)
for (i = input.length - 1; i > 0; i--) (
swap(input, 0, i);
arrLength--;
heapRoot(input, 0);
)
)
var arr = (12, 10, 22, 55, -8, 64, 14);
heapSortAlgo(arr);
console.log(arr);
Salida:
Conclusión
La ordenación es una parte importante de la creación de aplicaciones y sitios web con JavaScript. Ahora que está familiarizado con algunos de los algoritmos más importantes para hacer el trabajo, debería sentirse más seguro en JS Development.
Un hecho importante a tener en cuenta acerca de varias clasificaciones es que realmente no tiene que estresarse demasiado con respecto a qué algoritmo usar en la mayoría de los casos. Ahora que el hardware de la computadora es tan potente, los procesadores modernos de teléfonos y computadoras de escritorio no se cansarán de clasificar incluso cientos de elementos en unos pocos milisegundos. Solo en los casos en que está atascado con hardware lento o en situaciones en las que puede optimizar cada sección de código donde cambiar los algoritmos de clasificación puede ser beneficioso.
Artículos recomendados
Esta es una guía para ordenar algoritmos en JavaScript. Aquí discutimos los 6 mejores algoritmos de clasificación en JavaScript junto con ejemplos e implementación de código. También puede consultar los siguientes artículos para obtener más información:
- Compiladores JavaScript
- Invertir en JavaScript
- Introducción a JavaScript
- Cuadrados en Java
- Algoritmos de clasificación rápida en Java
- Matrices en estructura de datos
- Algoritmo de C ++ | Ejemplos de algoritmo C ++