Los programadores que pasan del desarrollo web y de PC a la codificación para dispositivos móviles o sistemas integrados descubren que dedican más tiempo a seleccionar y codificar sus propias estructuras de datos y algoritmos. Con menos memoria y almacenamiento de datos limitado, no hay espacio para bibliotecas o marcos preconstruidos. Entonces, para aquellos que necesitan escribir sus propias rutinas de clasificación, aquí hay algunas consideraciones sobre cómo elegir el tipo de burbuja humilde.
Fondo
La clasificación de burbujas es un algoritmo simple que ordena una lista de elementos en la memoria. Dada una matriz, el código compara repetidamente cada par de elementos adyacentes y los intercambia si no están en orden. El proceso se repite hasta que no se producen más intercambios. Si fuera posible ver la matriz mientras la clasificación está en curso, los valores bajos "burbujearían" hacia la parte superior mientras que los valores grandes se hundirían hasta la parte inferior. Aquí está el código relevante en Visual Basic 2010:
Video del día
While swap = True swap = False For i = 0 To tbl.length - 2 Si tbl (i)> tbl (i + 1) Entonces tmp = tbl (i) tbl (i) = tbl (i + 1) tbl (i + 1) = tmp swap = True End If Next End while
Cuándo elegir el tipo de burbuja
Este algoritmo tiene varias ventajas. Es simple de escribir, fácil de entender y solo requiere unas pocas líneas de código. Los datos se ordenan en su lugar, por lo que hay poca sobrecarga de memoria y, una vez ordenados, los datos están en la memoria, listos para su procesamiento. La principal desventaja es la cantidad de tiempo que se tarda en clasificar. El tiempo promedio aumenta casi exponencialmente a medida que aumenta el número de elementos de la tabla. Diez veces la cantidad de elementos toma casi cien veces más tiempo para clasificar.
Otros tipos de matrices
Los algoritmos de clasificación varían en complejidad, velocidad y gastos generales. El tipo de burbuja es el menos complejo pero también uno de los más lentos. Otros ordenamientos basados en matrices, como el ordenamiento por inserción y el ordenamiento por intercambio, son un poco más rápidos pero requieren más código (consulte las referencias a continuación). La principal ventaja de los ordenamientos basados en matrices es que utilizan la menor cantidad de código y ocupan la menor cantidad de memoria de trabajo. Considere estos tipos para arreglos simples con menos de unos pocos cientos de elementos.
Algoritmos de clasificación complejos
Los conjuntos de datos más grandes requieren un código más complejo y más memoria. La clasificación rápida y la clasificación por montón dividen y copian los conjuntos de datos para optimizar el número de comparaciones. La clasificación rápida divide continuamente la lista y luego la vuelve a ensamblar en orden. La clasificación de pila copia los datos en una estructura de árbol y luego atraviesa el árbol para copiar los datos nuevamente en orden. Ambos son rápidos y eficientes, pero requieren más código y mucho más almacenamiento de trabajo. Elija estos algoritmos para grandes conjuntos de datos.
