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.

La idea central de este algoritmo consiste en insertar un elemento del arreglo en su parte izquierda, ya que se encuentra ordenada. Este proceso se repite desde el segundo hasta el n-ésimo elemento.

Método de Ordenamiento de quicksort

El método de ordenación Quicksort fue desarrollado por Hoare en el año 1960.
Es el algoritmo de ordenación más rápido. Se basa en la técnica divide y vencerás, que consiste en ir subdividiendo la lista en listas más pequeñas, y ordenar éstos. Para hacer esta división, se toma un valor de la lista como pivote, y se mueven todos los elementos menores que este pivote a su izquierda, y los mayores a su derecha. A continuación se aplica el mismo método a cada una de las dos partes en las que queda dividido la lista.

Después de elegir el pivote se realizan dos búsquedas:

Una de izquierda a derecha, buscando un elemento mayor que el pivote, otra de derecha a izquierda, buscando un elemento menor que el pivote.

Cuando se han encontrado los dos elementos anteriores, se intercambian, y se sigue realizando la búsqueda hasta que las dos búsquedas se encuentran.

La implementación del método de ordenación Quicksort es claramente recursiva.

Objetivos

• Entender los métodos de ordenamiento y sus aplicaciones, de igual forma saber aplicar los 4 métodos vistos en clase y visualizar su graficación en la  ventana.
• Entender la importancia de estos métodos en la programación de estructura de datos.
• Saber que necesidades satisfacen los métodos de ordenamientos y en qué circunstancias los encontramos.
• Poder implementar nuestra lista simple  a los métodos de ordenamiento

Problemática 

Un problema muy común en la vida cotidiana es la búsqueda de información, la mayoría de las veces encontramos páginas o lugares desordenados en estas es muy difícil encontrar lo que buscamos una de las soluciones  para aumentar la eficacia de búsqueda sería ordenar los elementos o datos para que de esta manera sea más práctica y rápida la búsqueda.

...