Quicksort

Un algoritmo de ordenación muy académico es el quicksort.

Es un método de ordenamiento de datos que utiliza la estrategia de divide y vencerás. 😉

Se divide el conjunto de datos que se quiere ordenar en 2 subconjuntos: uno con los datos más pequeños y otro con los datos más grandes.

Luego se ordena cada subconjunto de forma independiente y finalmente se combinan los resultados.

Ejemplo

Dados los números: 3, 8, 5, 4, 1, 9, 7

Se toma como pivote el número 5 y se dividen los números en 2 subconjuntos:

• Subconjunto A: 3, 4, 1
• Subconjunto B: 8, 9, 7

Luego se ordena cada subconjunto de forma independiente:

• Subconjunto A: 1, 3, 4
• Subconjunto B: 7, 8, 9

Finalmente, se combinan los resultados y se obtiene el siguiente orden: 1, 3, 4, 5, 7, 8, 9

Ejemplo de implementación:

/**
 * O(n log (n)) - O(n²)
 */
fun quickSort(
    list: List<Int>
): List<Int> {
    if (list.size < 2) {
        return list
    }

    val index = list.size / 2
    val pivot = list[index]

    val equal = list.filter { it == pivot }
    val less = list.filter { it < pivot }
    val greater = list.filter { it > pivot }

    return quickSort(less) + equal + quickSort(greater)
}

Y su correspondiente test unitario:

import org.junit.Assert.assertTrue
import org.junit.Test

class QuickSortKtTest {

    @Test
    fun `check quickSort order a list`() {
        val list = listOf(
            1,
            5,
            6,
            3,
            7
        )

        val orderedList = quickSort(list)

        assertTrue(
            listOf(
                1,
                3,
                5,
                6,
                7
            ) == orderedList
        )
    }
}

Ventajas

• Es un algoritmo de ordenamiento muy eficiente en la mayoría de los casos
• No requiere mucho espacio adicional

Desventajas

Es posible que el algoritmo no funcione correctamente si el pivote es el elemento más grande o más pequeño del conjunto de datos.

Puntación Big O

En notación Big O, tiene un rendimiento desde O(n log (n)) en el mejor de los casos, a O(n2) en el peor de ellos.

Conclusión

Es también un clásico, al igual que el algortimo de la burbuja. Pero mucho más rápido.

Y también es un buen modo de iniciarse en este campo para luego entender otros algoritmos más complejos.