Quicksort

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.