Ingeniería en Computación Estructura de datos “Métodos de ordenamiento”

[pic 1][pic 2]

UNIVERSIDAD NACIONAL AUTÓNOMA DE MÉXICO

FACULTAD DE ESTUDIOS SUPERIORES

ARAGÓN

 Ingeniería en Computación

Estructura de datos

“Métodos de ordenamiento”

Miguel Ángel Sánchez Hernández

 EQUIPO 2:

• Hidalgo de Jesús Iván
• Alarcon Mendoza Susana Herandi
• Pérez Ramirez Orlando Emmanuel

ÍNDICE

Introducción

¿Que es un método de ordenamiento ?................................................        2

Ordenamiento interno…………….…………………………………………        2

Metodo de ordenamiento Burbuja…………………………………………        3

Metodo de ordenamiento Seleccion......................................................        3

Metodo de ordenamiento Inserción ...…………………………………….        3

Método de ordenamiento Quicksort……………………………………….        3

Objetivos……………………………………………………………….        4

Problemática…………………………………………………………..        4

Implementación de la solución………………………...………….        4

Conclusión…………………………………………………………….        7

Referencias bibliográficas………………………………………….        8

Introducción

Métodos de Ordenamiento

¿Qué es un Método de Ordenamiento?

La ordenación de los datos consiste en disponer o clasificar un conjunto de datos (o una estructura) en algún determinado orden con respecto a alguno de sus campos.

Ordenar significa reagrupar o reorganizar un conjunto de datos u objetos en una secuencia específica los procesos de ordenación son frecuentes en nuestra vida, la sociedad debe estar informada y, por lo tanto, constantemente se necesita buscar y recuperar información.

Formalmente la ordenación sería de la siguiente manera:

Sea A una lista N elementos:

 , , , , … , [pic 3][pic 4][pic 5][pic 6][pic 7]

Ordenar significa permutar estos elementos de tal forma que queden de acuerdo con una distribución preestablecida.

• Ascendente: (i < j) entonces (k[i] <= k[j])
• Descendente: (i > j) entonces (k[i] >= k[j])

En el procesamiento de datos a los métodos de ordenamiento se les clasifican en dos grandes categorías, según donde hayan sido almacenados:

• Ordenamiento interno: Se lleva a cabo completamente en la memoria principal de la computadora (RAM).  
• Ordenamiento externo: Se lleva a cabo en memorias secundarias, como discos, tambores, etc.

Ordenamiento interno

Los métodos de ordenación interna a su vez se pueden clasificar en dos tipos:

Métodos directos: Los métodos directos tienen la característica de que su implementación es relativamente sencilla y son fáciles de comprender, aunque son ineficientes cuando el número de elementos de la lista es grande.

Los métodos directos más conocidos son:

• Método de burbuja
• Método de selección
• Método de inserción

Métodos logarítmicos (n * Iog n): Los métodos logarítmicos, son más complejos que los directos y, al ser menos intuitivos, resultan más difíciles de entender. Sin embargo, son más eficientes cuando el número de elementos de la lista es grande.

Los métodos logarítmicos más conocidos son:

• Método de Shell Sort
• Método de QuickSort
• Método de HeapSort

Método de Ordenamiento  por Intercambio Directo (Método Burbuja)

El método de ordenamiento directo, también conocido como método burbuja es el más utilizado por los estudiantes de computación por su fácil comprensión en la programación. Este método puede trabajar de dos maneras diferentes llevando los elementos más pequeños a la izquierda de la lista, o trasladando los elementos más grandes hacia la derecha. La idea básica de este método es comparar pares de elementos adyacentes e intercambiarlos entre sí hasta que todos se encuentren ordenados. Se realizan (n-1) pasadas transportando en cada una de ellas el mayor o menor elementos a su posición ideal.

Método de Ordenamiento de Selección 

El método de selección consiste en encontrar el menor de todos los elementos de la lista e intercambiarlo con el que está en la primera posición. Luego el segundo más pequeño, y así sucesivamente hasta ordenarlo todo. Su implementación requiere O(n2) comparaciones e intercambios para ordenar una secuencia de elementos. 

Este algoritmo mejora ligeramente el algoritmo de la burbuja. Pero cuando hay que ordenar una lista de estructuras más complejas, la operación de intercambiar los elementos sería más costosa en este caso. Su funcionamiento se puede definir de forma general como:

-Buscar el mínimo elemento entre una posición i y el final de la lista

-Intercambiar el mínimo con el elemento de la posición i.

Método de Ordenamiento de Inserción

El algoritmo de ordenamiento por inserción es un algoritmo de fácil aplicación que permite el ordenamiento de una lista. Su funcionamiento consiste en el recorrido por la lista seleccionando en cada iteración un valor como clave y compararlo con el resto insertándo lo en el lugar correspondiente.
El método de inserción directa es el método que utilizan generalmente los juegos de cartas cuando las ordenan, de ahí que también se conozca con el nombre de método de la baraja.

...