Algoritmo de ordenamiento: Quicksort

El algoritmo de ordenamiento rápido (Quicksort en inglés) en un método que nos ayuda a ordenar elementos de un mismo tipo en una lista. A diferencia del algoritmo burbuja (Bubblesort), el algoritmo Quicksort es del tipo divide y vencerás, en donde éste utiliza un pivote para dividir de un lado los valores menores al pivote y del otro lado los valores mayores al pivote, y así sucesivamente hasta lograr su ordenamiento.

Complejidad del algoritmo

El algoritmo Quicksort tiene de complejidad en su caso promedio O(n log n) para ordenar una lista con n elementos, sin embargo el peor caso tiene complejidad O(n²), y éste caso ocurre cuando tenemos todos los elementos de un solo lado, por lo tanto el pivote queda al extremo de la lista. Sin embargo comparado con Bubblesort, el caso promedio es menor.

Ejemplo de uso

Para ejemplificar como funciona éste ordenamiento, mostraremos un video, en donde tenemos una lista de elementos e iteramos con el pivote (que se encuentra como una casilla negra), los valores a comparar se muestran en rojo.

Código de Quicksort en Javascript

Finalmente aquí tenemos el código en Javascript, en donde se recibe como input el array o listado de elementos y realiza las iteraciones con elementos menores y mayores. En el ejemplo mostramos cómo hacerlo en forma recursiva, sin embargo, también es posible hacerlo en forma iterativa.

 function quicksort(array){                       
 if(array.length <=1){ 
    return array       
 }       
 const pivot = Math.floor(
    Math.random() * Math.floor(array.length-1))       
 let smaller = []                     
 let middle = [array[pivot]]       
 let bigger = []       
 for (let i = 0; i < array.length; i++){       
    if(i==pivot){       
      continue       
    }       
    else if (array[i]==array[pivot]){       
      middle.push(array[i])       
    }       
    else if (array[i]<array[pivot]){       
      smaller.push(array[i])       
    }                     
    else {                    
      bigger.push(array[i])                     
    }                      
 }                      
 return [...quicksort(smaller), ...middle, ... quicksort(bigger)]       
}

Conclusión

El algoritmo de ordenamiento rápido permite ordenar una lista en menor tiempo promedio en comparación a otros algoritmos como bubblesort, sin embargo, en el peor caso la ganancia es el mismo.

Así mismo, es necesario considerar la ubicación del pivote en cada iteración, ya que éste determina los elementos menores a la izquierda, y los valores mayores a la derecha, con el objetivo de reducir la complejidad del algoritmo al usar la técnica de divide y vencerás.