Algoritmos de ordenamiento

Algoritmos de Ordenamiento

Debido a que las estructuras de datos son utilizadas para almacenar informacin, para poder recuperar esa informacin de manera eficiente es deseable que aquella estordenada. Existen varios mtodos para ordenar las diferentes estructuras de datos bsicas.
En general los mtodos de ordenamiento no son utilizados con frecuencia, en algunos casos slo una vez. Hay mtodosmuy simples de implementar que son tiles en los casos en dnde el nmero de elementos a ordenar no es muy grande (ej, menos de 500 elementos). Por otro lado hay mtodos sofisticados, ms difciles deimplementar pero que son ms eficientes en cuestin de tiempo de ejecucin.
Los mtodos sencillos por lo general requieren de aproximadamente n x n pasos para ordenar n elementos.
Los mtodos simples son:insertion sort (o por insercin directa) selection sort, bubble sort, y shellsort, en dnde el ltimo es una extensn al insertion sort, siendo ms rpido. Los mtodos ms complejos son el quick-sort, el heapsort, radix y address-calculation sort. El ordenar un grupo de datos significa mover los datos o sus referencias para que queden en una secuencia tal que represente un orden, el cual puede ser numrico,alfabtico o incluso alfanumrico, ascendente o descendente.
Se ha dicho que el ordenamiento puede efectuarse moviendo los registros con las claves. El mover un registo completo implica un costo, el cualse incrementa conforme sea mayor el tamao del registro. Es por ello que es deseable evitar al mximo el movimiento de los registros. Una alternativa es el crear una tabla de referencias a losregistros y mover las referencias y no los datos. A continuacin se mostrarn los mtodos de ordenamiento empezando por el ms sencillo y avanzando hacia los mas sofisticados
La eficiencia de los algoritmos semide por el nmero de comparaciones e intercambios que tienen que hacer, es decir, se toma n como el nmero de elementos que tiene el arreglo a ordenar y se dice que un algoritmo realiza O(n2)...