Algoritmos de ordenación: Quicksort en Javascript

Cómo funciona el algoritmo quicksort para ordenar arrays

Image for post
Image for post

Llevaba tiempo queriendo escribir algún post sobre algoritmos de ordenación ya que son ese tipo de cosas que estudiamos en la universidad y luego las olvidamos sin caer en la cuenta de lo útiles que pueden llegar a ser cuando queremos optimizar nuestro código.

Así que ayer estuve probando a implementar el algoritmo quicksort en Javascript(uno de los más eficientes a la hora de ordenar un array) para un proyecto que necesitaba llevar a cabo una ordenación relativamente compleja. En este artículo os contaré el proceso que he seguido.

¡Espero que os sirva!

Rendimiento de quicksort

Worst-case performance: O(n^2)

Best-case performance: O(n log n)

Average performance: O(n log n)

No está mal teniendo en cuenta que el método burbuja tiene de media O(n^2)

🤔 ¿Cómo funciona?

Quicksort funciona escogiendo un elemento del array al que denominaremos pivote de modo que podamos dividir el array inicial en dos:

  • los mayores que él
  • los menores que él

situando este elemento pivote en el medio tras la separación.

A continuación, para cada uno de esos dos arrays volveremos a escoger un pivote y repetiremos la misma operación. Llegará un momento en que los arrays resultantes tengan o bien un elemento o bien ninguno si ya no existe un elemento con el que compararlos. El resto de los elementos habrán sido separados como pivotes en algún punto del algoritmo y ya se encontrarán en su posición correcta:

Image for post
Image for post
Quicksort

También existe versión animada si la preferís:

Image for post
Image for post
quicksort animation

💡 ¿Cómo lo implementamos?

Para implementar el algoritmo quicksort en javascript nos basaremos en el pseudocódigo extraído de la wikipedia:

algorithm quicksort(A, lo, hi) is
if lo < hi then
p := partition(A, lo, hi)
quicksort(A, lo, p - 1)
quicksort(A, p + 1, hi)

algorithm partition(A, lo, hi) is
pivot := A[hi]
i := lo
for j := lo to hi - 1 do
if A[j] < pivot then
swap A[i] with A[j]
i := i + 1
swap A[i] with A[hi]
return i

Lo primero que haremos será definir la función encargada de ejecutar el algoritmo. Como queremos que pueda ordenar todo tipo de arrays (no solo de números, sino también de objetos) le permitiremos recibir por argumentos una función adicional que especifique el método de ordenación de los objetos:

const defaultSortingAlgorithm = (a, b) => {
if (a < b) {
return -1;
}
if (a > b) {
return 1;
}
return 0;
};
const quickSort = (
unsortedArray,
sortingAlgorithm = defaultSortingAlgorithm
) => {
// quicksort implementation
};

Si observamos el pseudocódigo de la wikipedia, observamos que como pivote inicial se está escogiendo el final del array (esto puede provocar problemas de rendimiento incrementándolo hasta O(n^2) cuando el array ya viene ordenado) así que para no complicar mucho el artículo nos ceñiremos a él. Además, notad que el pseudocódigo está escrito en forma recursiva dado que no sabemos cuantas particiones nos tocará hacer conforme ordenamos el array. Con todo esto llegamos a:

Como veis, lo primero que hacemos es clonar el array para que la función sea inmutable y así no modifiquemos el array de entrada.

A partir de ahí definimos 3 métodos:

  • swapArrayElements , para intercambiar los elementos de un array
  • partition , que se encarga de escoger el pivote e intercambiar los elementos de modo que los mayores que él queden a su derecha y los menores a su izquierda. Como veis, la comparación la hago con el método de ordenación que me hayan pasado o bien con el que he establecido por defecto. Este método devuelve la posición en la que se quedó el pivote.
  • recursiveSort , el cual implementa el algoritmo quicksort tal y como está definido en la wikipedia. Notad que es necesario establecer la condición de parada start < end para que de este modo interrumpamos la recursividad si hemos llegado a arrays de 0 o 1 elementos.

Finalmente, lo que hace el método quickSort es invocar a recursiveSort pasándole el array así como la posición inicial y final.

Con esto ya tendríamos funcionando el algoritmo quicksort en javascript:

¿Quieres recibir más artículos como este?

Suscríbete a nuestra newsletter:

Written by

Entre paseo y paseo con Simba desarrollo en Symfony y React

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store