Quick Sort

El ordenamiento rápido (quicksort en inglés) es un algoritmo de ordenacion creado por el científico británico en computación C. A. R. Hoare.

Quick Sort es un algoritmo de ordenamiento eficiente que utiliza una estrategia de dividir y conquistar para ordenar una lista de elementos. Es un algoritmo ampliamente utilizado debido a su eficiencia y versatilidad para ordenar diferentes tipos de datos.
- Elige un elemento de la lista, al que llamaremos pivote (por ejemplo, el primer elemento).
- Reorganiza la lista de manera que todos los elementos menores al pivote se coloquen a su izquierda, y los mayores a su derecha. A esto se le llama “particionar” la lista.
- El pivote está en su posición final y se divide la lista en dos sub-listas alrededor de él. Se tiene una sub-lista con elementos menores al pivote y otra con elementos mayores.
- Repite los pasos 1 a 3 para cada sub-lista. Es decir, selecciona un nuevo pivote para cada una de ellas y particiona las sublistas nuevamente.
- Continúa hasta que todas las sublistas contengan sólo un elemento, momento en el que la lista entera estará ordenada.

Ejemplo

7 2 1 6 8 5 3 4
2 1 3 4 5 6 7 8
1 2 3 4 5 6 7 8

Es importante por varias razones:

• Eficiencia: Es uno de los algoritmos de ordenamiento más eficientes que existen, ya que su complejidad temporal promedio es de O(n log n), lo que significa que es muy rápido en la mayoría de los casos, incluso para grandes conjuntos de datos.
• Adaptabilidad: Es un algoritmo adaptable, lo que significa que puede ser utilizado para ordenar una amplia gama de tipos de datos, incluyendo números, cadenas de texto, objetos personalizados y mucho más.
• Implementación: Es fácil de implementar y puede ser utilizado en una amplia variedad de aplicaciones. Además, es un algoritmo de ordenamiento estable, lo que significa que preserva el orden de elementos iguales en la lista.

Código de ejemplo en Rust

fn main() {
    let arr: Vec = vec![19, 7, 15, 12, 16, 18, 4, 11, 13];
    println!("{:?}", quick(arr));
}

fn quick(arr: Vec) -> Vec {
    if arr.len() <= 1 {
        return arr;
    }
    let pivot: i8 = arr[0];
    let left: Vec = arr[1..].iter().cloned().filter(|&x| x < pivot).collect();
    let right: Vec = arr[1..].iter().cloned().filter(|&x| x >= pivot).collect();

    let mut result: Vec = quick(left);
    result.push(pivot);
    result.extend(quick(right));
    result
}