Metodos De Ordenamiento De Datos

UNIDAD 5.
METODOS DE ORDENAMIENTO


COMPETENCIA ESPECIFICA DE LA UNIDAD. Aplicar el método de ordenamiento pertinente en la solución de un problema real.

5.1 ALGORITMOS DE ORDENAMIENTO INTERNO

5.1.1 BURBUJA

El método de intercambio directo, conocido también con el nombre de burbuja, es uno de los más utilizados, por su fácil comprensión y programación, pero también esprobablemente el método más ineficiente.

Este método puede trabajar de dos maneras diferentes. Llevando los elementos más pequeños hacia la parte izquierda del arreglo o bien llevando los elementos más grandes hacia la parte derecha del mismo.

La idea básica de este algoritmo consiste en comparar pares de elementos adyacentes e intercambiarlos entre sí hasta que todos se encuentren ordenados. Serealizan (n – 1) pasadas, transportando en cada una de las mismas el menor o mayor elemento (según sea el caso) a su posición ideal. Al final de las (n – 1) pasadas los elementos del arreglo estarán ordenados.

Suponiendo que se desea ordenar el siguiente arreglo, transportando en cada pasada el menor elemento hacia la parte izquierda del arreglo:



|15 |67 |8 |16 |44|27 |12 |35 |


Luego de cada pasada, el arreglo queda de la siguiente manera:

|Primera |8 | |15 | |67 | |12 |
|pasada: | | | | | | | |


Luego de cada pasada, el arreglo queda de la siguiente manera:

|Primera |15 | |8 | |16 | |44 ||pasada: | | | | | | | |

Se selecciona A[ 1 ], por lo tanto X = 15

PRIMER PASADA:

Recorrido de derecha a izquierda:

|12 |67 |8 |16 |44 |27 |15 |35 |

Recorrido de izquierda a derecha:

|12 |15 |8 |16 |44 |27 |67 |35 |


SEGUNDA PASADA:

Recorrido dederecha a izquierda:

|12 |8 |15 |16 |44 |27 |67 |35 |

Como el recorrido de izquierda a derecha debería iniciarse en la misma posición donde se encuentra el elemento X, el proceso se termina ya que el elemento X se encuentra en la posición correcta:

12 |8 |15 |16 |44 |27 |67 |35 | |

1er. Conjunto 2do. ConjuntoDespués de haber ubicado al elemento X en su lugar, se procede a ordenar el resto del arreglo, quedando de la siguiente manera:

12 | |8 | |15 | |16 | |44 | |27 | |67 | |35 | | |

12 | |8 | |15 | |16 | |35 | |27 | |44 | |67 | | |

12 | |8 | |15 | |16 | |27 | |35 | |44 | |67 | | |

8 | |12 | |15 | |16 | |27 | |35 | |44 | |67 | | |

El algoritmo de ordenación por el método quicksort en suversión iterativa es el siguiente:

// TOP, INI, FIN y POS son variables de tipo entero
// PILAMENOR y PILAMAYOR son arreglos unidimensionales

QUICKSORT(A[ ], N){
TOP = 1, PILAMENOR[TOP]=1 y PILAMAYOR[TOP]=N;
Repetir Mientras (TOP > 0){
Hacer INI = PILAMENOR[TOP], FIN=PILAMAYOR[TOP] y TOP=TOP – 1;
Llamar al algoritmo ORDENA con INI, FIN y POS;
Si (INI < POS-1) entonces{Hacer TOP = TOP + 1, PILAMENOR[TOP]=INI y PILAMAYOR[TOP]=POS – 1;
}
Si (FIN > POS +1) entonces{
Hacer TOP = TOP + 1, PILAMENOR[TOP]=POS+1 y PILAMAYOR[TOP]= FIN;
}
}
}

// INI y FIN representan las posiciones de los extremos izquierdo y derecho respectivamente, del conjunto de elementos a evaluar. POS es una variable donde se almacenará elresultado de este algoritmo

ORDENA (INI, FIN, POS){
Hacer IZQ=INI, DER=FIN, POS=INI y BAND=VERDADERO;
Repetir Mientras (BAND=VERDADERO){
Repetir Mientras (A[POS] = A[IZQ] y POS != IZQ){
IZQ=IZQ + 1;
}
Si (POS = IZQ) entonces Hacer BAND=FALSO;
Si no {
Hacer AUX=A[POS], A[POS]=A[IZQ], A[IZQ]=AUX y POS=IZQ;
}
}
}
}

El...