PDF de programación - Métodos de Ordenamiento

TÍTULO:

Métodos de Ordenamiento

FACULTAD: Sistemas

ASIGNATURA: Estructura de Datos

AUTOR: Víctor M. Cabezas

PROFESOR: Ing. Pablo Hinojosa

FECHA: Guayaquil, Agosto 16 de 2012



Debido a que las estructuras de datos son utilizadas para almacenar información, para poder recuperar esa
información de manera eficiente es deseable que aquella esté ordenada. Existen varios métodos para ordenar las
diferentes estructuras de datos básicas.

En general los métodos de ordenamiento no son utilizados con frecuencia, en algunos casos sólo una vez. Hay
métodos muy simples de implementar que son útiles en los casos en dónde el número de elementos a ordenar no
es muy grande (ej, menos de 500 elementos). Por otro lado hay métodos sofisticados, más difíciles de implementar
pero que son más eficientes en cuestión de tiempo de ejecución.

Los métodos sencillos por lo general requieren de aproximadamente n x n pasos para ordenar n elementos.

Los métodos simples son: insertion sort (o por inserción directa) selection sort, bubble sort, y shellsort, en dónde el
último es una extensón al insertion sort, siendo más rápido. Los métodos más complejos son el quick-sort, el heap
sort, radix y address-calculation sort. El ordenar un grupo de datos significa mover los datos o sus referencias para
que queden en una secuencia tal que represente un orden, el cual puede ser numérico, alfabético o incluso
alfanumérico, ascendente o descendente.

Se ha dicho que el ordenamiento puede efectuarse moviendo los registros con las claves. El mover un registo
completo implica un costo, el cual se incrementa conforme sea mayor el tamaño del registro. Es por ello que es
deseable evitar al máximo el movimiento de los registros. Una alternativa es el crear una tabla de referencias a los
registros y mover las referencias y no los datos.



1. Insertion Sort

Este es uno de los métodos más sencillos. Consta de tomar uno por uno los elementos de un arreglo y recorrerlo
hacia su posición con respecto a los anteriormente ordenados. Así empieza con el segundo elemento y lo ordena
con respecto al primero. Luego sigue con el tercero y lo coloca en su posición ordenada con respecto a los dos
anteriores, así sucesivamente hasta recorrer todas las posiciones del arreglo. Este es el algoritmo:

Procedimiento Insertion Sort

Este procedimiento recibe el arreglo de datos a ordenar a[] y altera las posiciones de sus elementos hasta dejarlos
ordenados de menor a mayor. N representa el número de elementos que contiene a[].



paso 1: [Para cada pos. del arreglo]
paso 2: [Inicializa v y j]


paso 3: [Compara v con los anteriores]
paso 4: [Recorre los datos mayores]
paso 5: [Decrementa j]

paso 5: [Inserta v en su posición]
paso 6: [Fin]



For i <- 2 to N do

v <- a[i]


j <- i.

While a[j-1] > v AND j>1 do
Set a[j] <- a[j-1],



Set a[j] <- v.



End.

set j <- j-1.

Ejemplo:

Si el arreglo a ordenar es a = ['a','s','o','r','t','i','n','g','e','x','a','m','p','l','e'],

el algoritmo va a recorrer el arreglo de izquierda a derecha. Primero toma el segundo dato 's' y lo asigna a v y i
toma el valor de la posición actual de v.

Luego compara esta 's' con lo que hay en la posición j-1, es decir, con 'a'. Debido a que 's' no es menor que 'a' no
sucede nada y avanza i.

Ahora v toma el valor 'o' y lo compara con 's', como es menor recorre a la 's' a la posición de la 'o'; decrementa j, la
cual ahora tiene la posición en dónde estaba la 's'; compara a 'o' con a[j-1] , es decir, con 'a'. Como no es menor
que la 'a' sale del for y pone la 'o' en la posición a[j]. El resultado hasta este punto es el arreglo siguiente: a =
['a','o','s','r',....]

Así se continúa y el resultado final es el arreglo ordenado :

a = ['a','a','e','e','g','i','l','m','n','o','p','r','s','t','x']



2. Selection Sort

El método de ordenamiento por selección consiste en encontrar el menor de todos los elementos del arreglo e
intercambiarlo con el que está en la primera posición. Luego el segundo mas pequeño, y así sucesivamente hasta
ordenar todo el arreglo.



Procedimiento Selection Sort

paso 1: [Para cada pos. del arreglo]
paso 2: [Inicializa la pos. del menor]
paso 3: [Recorre todo el arreglo]
paso 4: [Si a[j] es menor]
paso 5: [Reasigna el apuntador al menor]
paso 6: [Intercambia los datos de la pos.

paso 7: [Fin]


min y posición i]



menor <- i

For i <- 1 to N do

For j <- i+1 to N do



min = j

If a[j] < a[menor] then



Swap(a, min, j).
End.

Ejemplo:

El arreglo a ordenar es a = ['a','s','o','r','t','i','n','g','e','x','a','m','p','l','e']. Se empieza por recorrer el arreglo hasta
encontrar el menor elemento. En este caso el menor elemento es la primera 'a'. De manera que no ocurre ningún
cambio. Luego se procede a buscar el siguiente elemento y se encuentra la segunda 'a'. Esta se intercambia con el
dato que está en la segunta posición, la 's', quedando el arreglo así después de dos recorridos: a =
['a','a','o','r','t','i','n','g','e','x','s','m','p','l','e'].

El siguiente elemento, el tercero en orden de menor mayor es la primera 'e', la cual se intercambia con lo que está
en la tercera posición, o sea, la 'o'. Le sigue la segunda 's', la cual es intercambiada con la 'r'. El arreglo ahora se ve
de la siguiente manera: a = ['a','a','e','e','t','i','n','g','o','x','s','m','p','l','r']. De esta manera se va buscando el
elemento que debe ir en la siguiente posición hasta ordenar todo el arreglo.

El número de comparaciones que realiza este algoritmo es :

para el primer elemento se comparan n-1 datos, en general para el elemento i-ésimo se hacen n-i comparaciones,
por lo tanto, el total de comparaciones es la sumatoria para i de 1 a n-1 (n-i) = 1/2 n (n-1).

3. Shellsort

Denominado así por su desarrollador Donald Shell (1959), ordena una estructura de una manera similar a la del
Bubble Sort, sin embargo no ordena elementos adyacentes sino que utiliza una segmentación entre los datos. Esta
segmentación puede ser de cualquier tamaño de acuerdo a una secuencia de valores que empiezan con un valor
grande (pero menor al tamaño total de la estructura) y van disminuyendo hasta llegar al '1'. Una secuencia que se
ha comprobado ser de las mejores es: ...1093, 364, 121, 40, 13, 4, 1. En contraste, una secuencia que es mala
porque no produce un ordenamiento muy eficiente es ...64, 32, 16, 8, 4, 2, 1.

Su complejidad es de O(n1.2) en el mejor caso y de O(n1.25) en el caso promedio.



void shellsort ( int a[], int n)
/* Este procedimiento recibe un arreglo a ordenar a[] y el tamaño del arreglo n. Utiliza en este caso una serie de
t=6 incrementos h=[1,4,13,40,121,364] para el proceso (asumimos que el arreglo no es muy grande). */
{



}


int x,i,j,inc,s;

for(s=1; s < t; s++) /* recorre el arreglo de incrementos */
{



}

a[j+h] = a[j];
j = j-h;

inc = h[s];
for(i=inc+1; i < n; i++)
{



}

x = a[i];
j = i-inc;
while( j > 0 && a[j] > x)
{


}
a[j+h] = x;





4. Bubble Sort

El bubble sort, también conocido como ordenamiento burbuja, funciona de la siguiente manera: Se recorre el
arreglo intercambiando los elementos adjacentes que estén desordenados. Se recorre el arreglo tantas veces hasta
que ya no haya cambios. Prácticamente lo que hace es tomar el elemento mayor y lo va recorriendo de posición en
posición hasta ponerlo en su lugar.

Procedimiento Bubble Sort

For i <- N downto 1 do
paso 1: [Inicializa i al final de arreglo]

paso 2: [Inicia desde la segunda pos.]
paso 4: [Si a[j-1] es mayor que el que le sigue]
paso 5: [Los intercambia]

j-1, j).
paso 7: [Fin]



For j <- 2 to i do



If a[j-1] < a[j] then



Swap(a,

End.

Tiempo de ejecución del bubble sort:





para el mejor caso (un paso) O(n)
peor caso n(n-1)/2
promedio O(n2)



5. Merge Sort

El método Quicksort divide la estructura en dos y ordena cada mitad recursivamente. El caso del MergeSort es el
opuesto, es decir, en éste método de unen dos estructuras ordenadas para formar una sola ordenada
correctamente.

Tiene la ventaja de que utiliza un tiempo proporcional a: n log (n), su desventaja radica en que se requiere de un
espacio extra para el procedimiento.

Este tipo de ordenamiento es útil cuando se tiene una estructura ordenada y los nuevos datos a añadir se
almacenan en una estructura temporal para después agregarlos a la estructura original de manera que vuelva a
quedar ordenada.

Procedimiento MergeSort

/*recibe el arreglo a ordenar un índice l que indica el límite inferior del arreglo a ordenar y un índice r que indica el
límite superior*/

void mergesort(int a[], int l, int r)
{



int i,j,k,m,b[MAX];
if (r > l)
{

b[i-1] = a[i-1];

m = (r+l) /2;
mergesort(a, l, m);
mergesort(a, m+1, r);
for (i= m+1; i > l;i--)

for (j= m; j < r;j++)

for (k=l ; k <=r; k++)



if(b[i] < b[j])
a[k] = b[i++];
else
a[k] = b[j--];

b[r+m-j] = a[j+1];



}



}

a = {a,s,o,r,t,i,n,g,e,x,a,m,p,l,e}
{a,s,
o,r,
a,o,r,s,
i,t,
g,n,
g,i,n,t,
a,g,i,n,o,r,s,t,
e,x,
a,m,