Tarea 3 de Esctructura




Ordenamiento

El ordenamiento de datos (sort en inglés) consiste en colocar los datos en algún orden particular (por ejemplo; ascendente o descendente).
Es una de las tareas que consume más tiempo; por este motivo, se han desarrollado cientos de métodos diferentes para la ordenación de datos, y es imposible determinar cuál es el mejor en todas las circunstancias.
Los métodos de ordenamientomás usados son:

- Método de la burbuja, es el método más común, pero tiene pocas características positivas y es mejor no utilizarlo.
- Método de selección
- Método de inserción, son útiles para arreglos pequeños.
- Método de Shell, es el método que más se utiliza, incluso para arreglos con miles de entradas.

Ordenamiento por Burbuja

A este método también se le conoce como “Ordenamiento porHundimiento”.
Los valores más pequeños gradualmente burbujean hacia la parte alta del arreglo, como las burbujas de aire que ascienden en el agua, mientras que los valores más grandes se hunden al fondo del arreglo.
La técnica consiste en pasar varias veces por el arreglo. En cada paso, se comparan pares sucesivos de elementos. Por ejemplo, si se desea ordenar los valores del arreglo:

X[i] = [6  8  5 3]

en orden ascendente, existen dos procedimientos:

Método 1

1)    Se definen dos subíndices (i y j), el primero para definir el número de pase por el arreglo y el segundo para las comparaciones.

2)    Aunque hay (n=4) elementos en el arreglo, solo se efectúan (n-1=3) comparaciones en cada pase. Así mismo, sólo se necesitan (n-1=3) pases por el arreglo, por lo tanto los rangos de cadasubíndice son:
i :   1 .. n-1
j :   1 .. n-1

Por lo tanto, los bucles a utilizar son los siguientes:

Para i=1 Hasta n-1 Variación 1
Para j=1 Hasta n-1 Variación 1

3)    Se realiza una comparación entre ambos elementos del par sucesivo de elementos.

Si X[j]>X[j+1] Entonces

Primero se compara X[1] con X[2], luego X[2] con X[3] y X[3] con X[4].
Si uno de los pares está en orden descendente, seintercambian sus valores en el arreglo.
Si el par está en orden ascendente (o son idénticos los valores), se quedan tal como están.

4)    En el caso de que se requiera de un intercambio y con la finalidad de garantizar la conservación de los valores del arreglo, se utiliza una variable auxiliar (t) sobre la cual se copiara el valor del primer elementos del par (X[j]). Por ejemplo:

Gráfica 1. Pase delprimer elemento a la variable auxiliar.


Es decir: t = X[j]


Enseguida se hace una copia del valor del segundo elemento del par (X[j+1]) sobre el primer elemento (X[j]):

Gráfica 2. Pase del segundo elemento al primer elemento.


Es decir: X[j] = X[j+1]


Luego se hace una copia del valor de la variable auxiliar (t) sobre el segundo elemento (X[j+1]):

Gráfica 3. Pase de la variable auxiliar alsegundo elemento.


Es decir: X[j+1] = t




Finalmente, los elementos quedarán ordenados de la siguiente manera:

Gráfica 4. Ubicación definitiva del ordenamiento

Un valor grande puede moverse hacia abajo del arreglo muchas posiciones con un solo pase, pero un valor pequeño se moverá hacia arriba una sola posición.



En el primer pase, se garantiza que el mayor valor se hunde hasta el fondo delarreglo.
En el segundo pase se garantiza que el segundo valor mayor se hunde hasta la penúltima posición y así sucesivamente.

Método 2

1)    Este método consiste en comparar todos los elementos del arreglo en pares de elementos, para ello se definen dos subíndices, i para definir al primer elemento del par y j para el segundo elemento.

2)    Se determina el rango de cada subíndice, teniendo encuenta que para realizar las comparaciones, el primer elemento del par X[i], comenzará en la posición 1 y el segundo se iniciará en una posición más adelante que el primero X[j]=X[i+1].
El primero terminará en una posición menor que el último X[n-1] y el segundo en la última posición X[n]. En el ejemplo las comparaciones serían:

Grafica  5. Determinación de los rangos de cada subíndice.



Por...