TODOS LOS METODOS DE ORDENAMIENTO

UNIVERSIDAD NACIONAL AUTÓNOMA DE MÉXICO

FACULTAD DE CONTADURÍA Y ADMINISTRACIÓN

Licenciatura En Informática

Programación (Estructuras de Datos)

Autor: L.I. María de Lourdes Isabel

Ponce Vásquez

AGOSTO 2013 - DICIEMBRE 2013

Contenido

UNIDAD 4. METODOS DE ORDENAMIENTO        4

4.1.1. Introducción        4

4.1.2. Definición        4

4.1.3. Clasificación        4

4.1.4. Eficiencia del Ordenamiento        5

4.2. Método de la Burbuja        6

4.3. Método por Sacudida (Shaker Sort)        7

4.4. Método de Inserción Directa (Simple)        8

4.5. Método de Selección        9

4.6. Método Shell        10

4.7. Método Rápido (QuickSort)        12

4.8. Método Externo por Mezcla Directa        14

Objetivos Específicos

• Métodos de Ordenamiento

• Distinguir entre las diferentes estrategias de ordenamiento
• Conocer las formas de clasificar los ordenamientos
• Comparar la eficiencia de los diversos métodos de

ordenamientos

UNIDAD 4. METODOS DE ORDENAMIENTO

1. Introducción

Muchas actividades humanas humanas requieren usar colecciones de elementos que se encuentren en un orden específico. La entrega de correo, anuarios, listas telefónicas y listas de alumnos son algunos ejemplos de datos ordenados; los estudiantes de.

Por esto, una de las tareas que realizan frecuentemente las computadoras en el procesamiento de datos es la ordenación.

El estudio de diferentes métodos de ordenamiento es interesante desde un punto de vista teórico y, naturalmente, práctico, particularmente es importante conocer el tiempo que requiere cada algoritmo para realizar su función, ya que esto determinará cuál es la mejor elección al momento de decidir cuál es el método más adecuado dependiendo del conjunto a ordenar.

Esta unidad estudia los algoritmos y técnicas de ordenamiento más usuales. También se estudia el análisis de los algoritmos utilizados en diferentes métodos de ordenamiento para conseguir la máxima eficiencia en su uso real. La unidad analiza los métodos básicos y avanzados más empleados en programas profesionales .

1. Definición

El ordenamiento o clasificación de datos (sort) es la operación que consiste en reagrupar o reorganizar un conjunto (estructura) de datos en una secuencia específica. Disponer en algún determinado orden con respecto a uno de los campos de elementos del conjunto.

En terminología de ordenamiento, el elemento por el cual se ordena (o se busca) se denomina clave.

Una lista se dice que está ordenada por la clave k si la lista está en orden ascendente o descendente con respecto a esta clave. La lista se dice que está en orden ascendente si:

        i < j implica que k[i] <= k[j]

y se dice que está en orden descendente si:

        i > j implica que k[i] <= k[j]

para todos los elementos de la lista.

En general, un conjunto de elementos se almacenan en forma ordenada con el fin de simplificar la recuperación de información manualmente, o facilitar el acceso mecanizado a los datos de una manera más eficiente.

1. Clasificación

Existen diferentes algoritmos de ordenación elementales o básicos cuyos detalles de implementación se pueden encontrar en diferentes libros de algoritmos. La enciclopedia de referencia es KNUTH 1973 y sobre todo la 2a. edición publicada en 1998. Los algoritmos presentan diferencias entre ellos que los convierten en más o menos eficientes y prácticos según sea la rapidez y eficiencia demostrada por cada uno de ellos.

Generalmente se clasifican como:

• Ordenamiento Interno. Cuando los datos se almacenan en RAM (arreglos, listas enlazadas o árboles).
• Ordenamiento Externo. Si los datos se almacenan en memoria secundaria (archivos).

Otra forma de clasificar los métodos de ordenación es en dos grandes grupos:

• Métodos Directos: de implementación sencilla y fácil de comprender, pero ineficientes para un númro medio o grande de elementos. Entre ellos están: Burbuja, Selección, Inserción
• Métodos Indirectos (logarítmicos ó avanzados): Son más complejos, sofisticados y difíciles de entender, pero son más eficientes ya que requieren menos comparaciones y movimientos para ordenar. Entre ellos están: Shell, Rápido(quick), Mezcla(merge), Radixsort.

En el caso de listas pequeñas, los métodos directos se muestran eficientes, sobre todo porque los algoritmos son sencillos; su uso es muy frecuente.

Sin embargo, en listas grandes estos métodos se muestran ineficaces y es preciso recurrir a los métodos avanzados.

También es posible clasificarlos dependiendo del tipo de instrucciones que se usan como:

• Métodos Iterativos: sólo emplean ciclos para ordenar. Burbuja, Selección, Inserción, Shell.
• Métodos Recursivos: son más complejos, requieren de mayor atención y conocimiento para ser entendidos. Son rápidos y efectivos, utilizan generalmente la técnica Divide y vencerás, que consiste en dividir un problema grande en varios pequeños para que sea mas fácil resolverlos. Mediante llamadas recursivas a sí mismos, es posible que el tiempo de ejecución y de ordenación sea óptimo. Mezcla, Rápido.

1. Eficiencia del Ordenamiento

La eficiencia es el factor que mide la calidad y rendimiento de un algoritmo. 

En el caso de la operación de ordenamiento, los criterios que generalmente se siguen para determinar su eficiencia son:

• tiempo menor de ejecución en computadora;
• menor número de instrucciones

Sin embargo, generalmente el mejor criterio para medir la eficiencia de un método de ordenamiento será la medida del número de comparaciones entre los elementos afectados. El algoritmo de ordenación A será más eficiente que el B, si requiere menor número de comparaciones.

1. Método de la Burbuja

El método de intercambio directo o mejor conocido como burbuja, es el más usado entre los principiantes por su fácil comprensión y programación; pero probablemente es el más ineficiente.

El método de la burbuja consiste en comparar todos los elementos de una lista contra todos, si se cumple que uno es mayor o menor a otro, entonces se intercambian de posición. Puede funcionar llevando los elementos más pequeños a la izquierda o los más grandes a la derecha.

Procedimiento Burbuja(E/S TaDatos aDatos)

Var

        eCont1, eCont2, eAux : entero

Inicio

        Desde eCont1 = 1 Hasta Longitud(aDatos) hacer

                Desde eCont2 = eCont1 + 1 Hasta Longitud(aDatos) hacer

                        Si (aDatos[eCont1] > aDatos[eCont2]) entonces

...