Metodos De Ordenamiento

Metodos de Ordenamiento

Seleccion Directa: Considerese el algoritmo para ordenar un array A de enteros en orden ascendente, es decir, del numero mas pequeño al mayor. Es decir, si el array A tiene n elementos, se trata de ordenar los valores del array de modo que el dato cotenido en A[0] sea el valor mas pequeño, el valor almacenado en A [1] el siguiente mas pequeño, y asi hasta A [n-1], queha de contener el elemento de mayor valor. El algoritmo se apoya en sucesivas pasadas que intercambian el elemento mas pequeño sucesivamente con el primer elemento de la lista, A [0] en la primera pasada. En sintesis, se busca el elemento mas pequeño de la lista y se intercambia con A [0], primer elemento de la lista.

A [0] | A [1] | A [2] | .... | A [n-1] |

Despues de terminar esta primerapasada, el frente de la lista esta ordenado y el resto de la lista A[1], A[2], ..., A[n-1] permanece desordenado. La siguiente pasada busca en esta lista desordenada y selecciona el elemento mas pequeño, que se almacena entonces en la posicion A[1]. De este modo los elementos A[0] y A[1] estan ordenados y la sublista A[2], A[3], ..., A[n-1] desordenada; entonces se selecciona el elemento maspequeño y se intercambia con A[2]. El proceso continua n-1 pasadas y en ese momento la lista desordenada se reduce a un elemento (el mayor de la lista) y el array completo ha quedado ordenado.

Un ejemplo practico ayudara a la comprension del algoritmo. Consideremos un array A con 5 valores enteros 51, 21, 39, 80, 36:

Los pasos a seguir son:

1. Sleccionar el elemento mas pequeño de la listaA; intercambiarlo con el primer elemento A[0]. Ahora la entrada mas pequeña esta en la primera posicion del vector.
2. Considerar las posiciones de la lista A[1], A[2], A[3], ...seleccionar el elemento mas pequeño e intercambiarlo con A[1]. Ahora las dos primeras entradas estan de A estan en orden.
3. Continuar este proceso encontrando o seleccionando el elemento mas pequeño de losrestantes elementos de la lista, intercambiandolos adecuadamente.

Codificacion en C

La función ordSeleccion() ordena una lista o vector de números reales de n elementos. En la
pasada i, el proceso de selección explora la sublista A[i] a A[n-1] y fija el índice del elemento
más pequeño. Después de terminar la exploración, los elementos A[i] y A[indiceMenor] in-
tercambian las posiciones.
/*ordenar un array de n elementos de tipo double
utilizando el algoritmo de ordenación por selección
*/
void ordSeleccion (double a[], int n)
{
int indiceMenor, i, j;
/* ordenar a[0]..a[n-2] y a[n-1] en cada pasada */
for (i = 0; i < n-1; i++)
{
/* comienzo de la exploraciónen índice i */
indiceMenor = i;
/* j explora la sublista a[i+1]..a[n-1] */
for (j = i+1; j < n; j++)
if(a[j] < a[indiceMenor])
indiceMenor = j;
/* sitúa el elemento más pequeño en a[i] */
if (i != indiceMenor)
{
double aux = a[i];
a[i] = a[indiceMenor];
a[indiceMenor] = aux ;
}
}
}

El análisis del algoritmo de selección es sencillo y claro, ya que requiere un número fijo de
comparaciones que sólo dependen del tamaño de la lista o vector (array) y no de ladistribución
inicial de los datos.
Insercion Directa: El método de ordenación por inserción es similar al proceso típico de ordenar tarjetas de nombres (cartas de una baraja) por orden alfabético, que consiste en insertar un nombre en su posición correcta dentro de una lista o archivo que ya está ordenado. Así el proceso en el caso de la lista de enteros A = 50, 20, 40, 80, 30.

Los Pasos a seguir:1. El primer elemento A[0] se considera ordenado; es decir, la lista inicial consta de un elemento.
1. Se inserta A[1] en la posición correcta, delante o detrás de A[0], dependiendo de que sea menor o mayor.
2. Por cada bucle o iteración i (desde i=1 hasta n-1) se explora la sublista A[i-1] . . A[0] buscando la posición correcta de inserción; a la vez se mueve hacia abajo (a la...