Metodos de ordenacion (informatica)

Métodos de ordenación
Introducción
Ordenar significa reagrupar o reorganizar un conjunto de datos u objetos en una secuencia específica. La ordenación es una actividad fundamental y relevante en la vida.
Formalmente se define ordenación de la siguiente manera:
Sea A una lista de N elementos:
A_1,A_2,A_3,………. A_N
Ordenar significa permutar estos elementos de tal forma que queden de acuerdocon una distribución preestablecida.
Ascendente: A_1 ≤A_2 ≤ A_3 ≤ …. ≤ A_N
Descendente: A_1 ≥A_2 ≥ A_3 ≥ …. ≥ A_N
En el procesamiento de datos a los métodos de ordenación se les clasifica en dos grandes categorías, según donde haya sido almacenado:
Ordenación de arreglos u ordenación interna
Ordenación de archivos u ordenación externa
Ordenación interna
Los métodos de ordenacióninterna se explican con arreglos unidimensionales, pero su uso puede extenderse a otros tipos de arreglos y estructuras de datos.
Los métodos de ordenación interna a su vez se pueden clasificar en dos tipos:
Métodos directos (n^2).
Métodos logarítmicos (n*log n).
Los métodos directos tienen una característica de que su implementación es relativamente sencilla y son fáciles de comprender, aunqueson ineficientes cuando N – el número de elementos del arreglo – es el tamaño mediano o grande. Los elementos logarítmicos, por su parte, son más complejos que los directos.
Ordenación por intercambio directo (burbuja).
Conocido coloquialmente como método de burbuja, es al más utilizado entre los estudiantes principiantes de computación por su fácil comprensión y programación. La idea básica deeste algoritmo consiste en comparar pares de elementos adyacentes e intercambiarse entre sí hasta que todos se encuentren ordenados.
Ordenamiento por el método de intercambio directo con señal
Éste método es una modificación del método de intercambio directo analizado en la sección anterior. La idea central de este algoritmo consiste en utilizar una marca o señal para indicar que no se haproducido un intercambio en una pasada.
Ordenamiento por el método de sacudida (Shaker short).
El método de shaker short, más conocido como el método de la sacudida es una optimización del método del cambio directo. La idea básica de este algoritmo consiste en mezclar las dos formas en las que se hace el método de burbuja.
En este algoritmo cada pasad tiene dos etapas. En la primera, de derecha aizquierda, se traslada los elementos más pequeños hacia la parte de izquierda del arreglo, almacenado en una variable la posición del último elemento intercambiado. En la segunda etapa de izquierda a derecha se trasladan los elementos hacia la parte derecha de arreglo, almacenado en una variable la posición del último elemento intercambiado.
Ordenación por inserción directa
El método porinserción directa es que utilizan generalmente los jugadores de cartas cuando las ordenan, de ahí que también se le conozca con el nombre de baraja.
La idea central de este algoritmo consiste en insertar en elemento del arreglo en su parte izquierda, que ya se encuentra ordenada. Este proceso se repite desde el segundo hasta el enésimo elemento.
Ordenación de elemento por inserción binaria.
Este es unamejora de la inserción directa presentado anteriormente, esta consiste en realizar una búsqueda binaria en lugar de una búsqueda secuencial, para insertar un elemento en la parte izquierda del arreglo que ya se encuentra ordenado. Este proceso se repite desde el segundo hasta el enésimo elemento.
Ordenación por selección directa
Este es más eficiente que los mencionados anteriormente. Pero sucomportamiento es mejor que los anteriores y su programación es fácil y comprensible, no es recomendable utilizarlos cuando un número de arreglos es mediano o grande. La idea básica de este algoritmo consiste en buscar el menor del arreglo y colocarlo en la primera posición.
Ordenación por el método de Shell
El método de Shell es una versión mejorada del método de inserción directa. Recibe el...