Metodos De Ordenamiento

Investigación Corta
“Sorting”
Guatemala, 3 de octubre de 2004
Sorting
Uno de los problemas fundamentales de la ciencia de la computación es ordenar una lista de objetos. Para esta necesidad existe una solución, llamada “sorting algorithms”, término cuya traducción en español es “algoritmos de ordenamiento”. Algunos algoritmos son simples y casi deducidos intuitivamente. Otros son extremadamentecomplicados pero dan resultados inmediatos (Weisstein, 1999). A continuación se presenta una breve introducción al tema.
¿Qué es sorting?
En español significa ordenamiento. En las ciencias de la computación y en las matemáticas, un algoritmo de sorting es aquel que coloca a los elementos de una lista en determinado orden. Los órdenes más utilizados son los órdenes numéricos y lexicográficos. Unproceso de sorting (ordenamiento) eficiente es necesario para optimizar el uso de otros algoritmos. Es muy utilizado para organizar “human readable output” (Lamont, 2003).
Sorting es el arreglo de números (u otros objetos ordenables) en una lista, en el correcto orden lexicográfico. Por tanto la alfabetización es una forma de ordenamiento. Debido a la importancia extrema que tiene el ordenamiento dedatos en casi todos los algoritmos de computación y database, muchos esfuerzos han sido enfocados a la creación y el análisis de eficientes algoritmos de ordenamiento (Weisstein, 1999).
Clasificación de algoritmos de Sorting
En las ciencias de la computación los algoritmos de ordenamiento se clasificados según (Lamont, 2003):
Complejidad computacional. Son aquellos que se clasifican en términosde la eficiencia que tenga determinado algoritmo para organizar una lista de tamaño n. Normalmente un buen comportamiento es aquel en que el número de comparaciones es n logn (Lamont, 2003).
Uso de memoria (Lamont, 2003). Internal Sort, se le llama a cualquier algoritmo que utilice main mamory exclusivamente, durante el ordenamiento. Esto asume una “high-speed random acces to all memory”. ExternalSort, se le llama a cualquier algoritmo que utilice memoria externa, como lo podría ser un disco o algún tipo de cinta magnética (Scitec 2004).
Estabilidad. Los algoritmos que mantienen cierto tipo de estabilidad mantienen el orden relativo de ingreso de los valores de misma magnitud. Es decir, un algoritmo es estable si al ingresar S y R con la misma tecla, pero si R aparece antes que S en lalista original, R aparecerá antes de S en la lista ordenada (Lamont, 2003).
Entre los algoritmos de tipo estable están: Bubble Sort, Insertion Sort, Bucket Sort, Merge Sort y Coctail Sort. Entre los algoritmos de tipo inestable están: Selection Sort, Shell sort, Quick Sort, Heap Sort y Smooth Sort (Lamont, 2003).
Nomenclatura para estimados de Tiempo, de algoritmos de ordena miento:
Es posiblepronosticar un estimado de tiempo de la ejecución de los algoritmos utilizando la notación O (big-oh). Por ejemplo un algoritmo que ejecuta en O(n2) indica que el tiempo de ejecución crece según el cuadrado de el tamaño de la data (Knuth, 1998).
Algunos Algoritmos de Sorting más populares:
Bubble Sort:
Es el método de ordenamiento más fácil de realizar y más fácil de comprender. Este se considera el mássimple y es utilizado a nivel mundial. El algoritmo inicia al principio de el conjunto de información a ordenar. Compara los primeros dos elementos, y si el primero es más grande que el segundo, los intercambia y luego repite este procedimiento hasta que no hayan ocurrido cambios en la última evaluación. El algoritmo realiza esto para cada par de elementos adyacentes, hasta que no tiene máselementos que comparar. Sin embargo este algoritmo es muy ineficiente, y es raramente utilizado, excepto para fines educacionales. Una variante de este método de ordenamiento es llamado Shuttle Sort (Lamont, 2003).
Insertion Sort:
Este método de ordenamiento es muy similar al Bubble Sort, con la diferencia que éste es más eficiente ya que reduce las comparaciones entre los elementos. Un elemento es...