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.
Los miembros de "Los androides Premium" escuchan contenido adicional en audio sobre este artículo... ¡y otros más de 100!
Hay que suscribirse para disfrutar de todo el contenido premium desde la web y la app, así como participar en las actividades premium: videoconferencias y canales premium en Discord.
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.