Clasificación interna

La ordenación interna es cualquier proceso de ordenación de datos que se realiza completamente dentro de la memoria principal de un ordenador. Esto es posible siempre que los datos a ordenar sean lo suficientemente pequeños como para almacenarse en su totalidad en la memoria principal, como en un disco duro. Cualquier lectura o escritura de datos en este medio más lento puede ralentizar considerablemente el proceso de ordenación. Este problema tiene implicaciones para los diferentes algoritmos de ordenación .

Algunos algoritmos de ordenación interna comunes incluyen:

1. Ordenación de burbuja
2. Ordenación por inserción
3. Ordenación rápida
4. Ordenación por montículo
5. Ordenación por radix
6. Ordenación por selección

Consideremos el algoritmo Bubblesort , donde los registros adyacentes se intercambian para ordenarlos correctamente, de modo que parezcan "burbujear" hacia arriba y hacia abajo en el espacio de datos. Si esto se realiza por bloques, al ordenar todos los registros del bloque 1, pasamos al bloque 2, pero descubrimos que algunos registros del bloque 1 deben "burbujear" a través del bloque 2, y viceversa (es decir, hay registros en el bloque 2 que pertenecen al bloque 1, y registros en el bloque 1 que pertenecen al bloque 2 o a bloques posteriores). Esto provoca que los bloques se lean y se escriban en el disco muchas veces a medida que los registros cruzan los límites entre ellos, lo que resulta en una degradación considerable del rendimiento. Si todos los datos se pueden almacenar en memoria como un único bloque grande, se evita esta pérdida de rendimiento.

Por otro lado, algunos algoritmos manejan mejor la ordenación externa . El algoritmo Merge Sort divide los datos en fragmentos, los ordena mediante otro algoritmo (como Bubble Sort o Quick Sort ) y luego los recombina de dos en dos, de manera que cada fragmento recombinado esté en orden. Este método minimiza la cantidad de lecturas y escrituras de fragmentos de datos en el disco y es un método popular de ordenación externa.