Ordenación rápida en Arduino con algoritmo QuickSort


En la entrada anterior vimos el algoritmo Bubble Sort como ejemplo de un algoritmo muy extendido pero ineficiente para ordenar un vector.

En esta entrada vamos a implementar el algoritmo QuickSort tanto ascendente como descendente. Quick Sort es un algoritmo de ordenación mucho más moderno y eficiente. De hecho, es el algoritmo estándar de ordenación en C#.

QuickSort tiene una complejidad promedio de O(n•log n) y de O(n^2) en el peor de los casos. En comparación, los algoritmos menos eficientes como Bubble Sort o Insertion Sort tienen O(n^2) tanto en promedio como en peor caso.

El algoritmo QuickSort permite una implementación sencilla en C++ que puede funcionar sin problemas en un procesador como Arduino.

Anuncio:

Y estos son los resultados del benchmark, realizados en un Arduino Nano a 16Mhz.

El tiempo para ordenar la muestra de 100 elementos con QuickSort es de 1.54ms frente a 12.65ms con Bubble Sort, es decir, 8.21 veces más rápido. En el caso de la muestra de 500 elementos el tiempo para QuickSort es 9.76ms frente a 325,92ms con Bubble Sort, 33.39 veces más rápido a favor de QuickSort.

Como vemos, QuickSort es uno de los algoritmos de ordenación más eficiente, y su implementación es lo suficientemente sencilla para que no sea un impedimento para implementar incluso en procesadores sencillos como Arduino.  

QuickSort en una librería

¿Y si lo metemos en una librería para que sea más cómodo de usar? Por supuesto que sí, aquí una librería de QuickSort para Arduino. ¡A disfrutarlo!

Si te ha gustado esta entrada y quieres leer más sobre Arduino puedes consultar la sección
tutoriales de Arduino

Anuncio:

Previous Ordenar un vector con Arduino y algoritmo Bubble Sort
Next Librería Arduino QuickSort
1000