Algoritmos JavaScript: Quicksort

Quicksort es un algoritmo de búsqueda más eficiente queorden de selección,en la mayoría de los casosy hace uso de la recursividad.

La recursividad significa que llamamos a una función desde dentro de la misma función. Es una práctica muy útil, a veces, y este es uno de esos casos.

Dije "en la mayoría de los casos" porque, como veremos, en el peor de los casos, la clasificación de burbujas puede tardar el mismo tiempo que la clasificación de selección:O(n^2). Pero en el mejor de los casos, se ejecutará enO(n log n), que está en el medio entreO(n)yO(n^2).

¿Como funciona? Dada una matriz, elegimos un elemento, llamadopivote. Luego obtenemos todos los elementos más pequeños que el pivote y los elementos más grandes que el pivote.

Luego ejecutamos la misma operación en la matriz 2 que componen los elementos más pequeños y más grandes.

Es más fácil ver el código que describirlo:

const quickSort = (originalList) => {
  const list = [...originalList]

if (list.length < 2) { return list }

const pivot = list[0]

const smaller = list.filter((item) => item < pivot) const bigger = list.filter((item) => item > pivot)

return […quickSort(smaller), pivot, …quickSort(bigger)] }

En este caso, elegí el pivote para ser el primer elemento de la matriz, pero también podría ser el elemento del medio, por ejemplo:

const pivot = list[Math(floor(list.length / 2)]

Observe cómo copiamos primero la matriz, por lo que llamamosquickSort()no modifica la matriz original, solo devuelve una nueva matriz ordenada:

const a = [1, 6, 3, 4, 5, 1, 0, 4, 8]

console.log(quickSort(a)) //[0, 1, 1, 3, 4, 4, 5, 6, 8 console.log(a) //[1, 6, 3, 4, 5, 1, 0, 4, 8]


Más tutoriales de js: