Algoritmo QuickSort

Te explico cómo funciona el algoritmo QuickSort, el algoritmo más eficiente y rápido de ordenación

El algoritmo QuickSort es, hoy por hoy, el algoritmo más eficiente y rápido para ordenación de listas.

Este algoritmo se basa que partir el array a ordenar en dos array más pequeños y aplicarle a cada uno de ellos la misma función de partir. Sí, te has dado cuenta, usaremos la recursividad.

Explicación del algoritmo

1. Se toma cualquier elemento del array al que llamaremos pivote, a mí me gusta usar el primer elemento del array
2. A continuación comparamos a cada uno de los elementos con el pivote, si el elemento es más pequeño que el pivote lo metemos en una lista (yo la llamo arraySmaller) y si no pues a la otra lista (arrayBigger)
3. Si te das cuenta, los dos nuevos array obtenidos no tienen porqué estar ordenados, pero lo que es seguro es que el pivote estará ordenado entre los dos arrays, quiero decir que el pivote será el elemento central.
4. A continuación lo que haré será pasar los dos nuevos arrays obtenidos (arraySmaller y arrayBigger) por la misma función recursiva hasta que los arrays se queden vacíos

Código y explicación

        
  const input:number[]=[52,62,97,25,48,59,80,33,27,53,68,31,26,13,63,77,40,89,96,52,65];

  const quickSort=(input: number[]):number[] => {
    if(input.length===0) return []; //caso base
    const pivot:number=input[0];
    let arrayBigger:number[]=[];
    let arraySmaller:number[]=[];
    for(let i:number=1;i<input.length;i++){
      if(input[i]<pivot){
        arraySmaller.push(input[i])
      }else{
        arrayBigger.push(input[i])
      }
    }
    return [...quickSort(arraySmaller),pivot,...quickSort(arrayBigger)];
  }
        
  console.log(quickSort(input));         
        

[LOG]: [13, 25, 26, 27, 31, 33, 40, 48, 52, 52, 53, 59, 62, 63, 65, 68, 77, 80, 89, 96, 97]

1. Lo primero que hacemos para toda función recursiva es definir el caso base o situación de salida para no caer en un bucle infinito, en nuestro ejercicio el caso base será cuando el array a ordenar esté vacío.
2. A continuación tomo como pivote el primer elemento del array
3. Defino dos nuevos arrays vacíos
4. Recorro todos los elementos del array (excepto el primero porque lo hemos tomado como pivote) y los voy comparando con el pivote. Si el elemento es más pequeño que el pivote lo inserto en la lista arraySmaller, y si es mayor que el pivote lo inserto en la lista arrayBigger.
5. Devulevo un array que será el resultado de ordenar el array arraySmaller concatenado con el pivote y por último concatenado con el resultado de ordenar el array arrayBigger.

Hasta luego 🖖