Juan Garcés

Personal Blog

Métodos de Ordenamiento

enero 25th, 2013

Ordenamiento por Selección

 

La idea básica de un ordenamiento por selección es la selección repetida de la llave menor restante en una lista de datos no clasificados, como la siguiente llave (dato o registro), en una lista de datos ordenada que crece.


La totalidad de la lista de llaves no ordenadas, debe estar disponible, para que nosotros podamos seleccionar la llave con valor mínimo en esa lista. Sin embargo, la lista ordenada, podrá ser puesta en la salida, a medida que avancemos.

Por ejemplo, consideremos la siguiente lista de llaves no ordenadas:


El primer paso de selección identifica el 2 como valor mínimo, lo saca de dicha lista y lo agrega como primer elemento en una nueva lista ordenada.


El segundo paso identifica el 3 como el siguiente elemento mínimo y lo retira de la lista para incluirlo en la nueva lista de elementos ordenados.


Después del sexto paso, tenemos la siguiente lista.


Para una lista de n registros, este algoritmo requiere n pasadas sobre la lista no ordenada. En la i-ésima pasada, se habrán hecho n-i comparaciones de llaves. Por lo tanto, el número total de comparaciones será:


La cual da n(n-1)/2. Esta ordenación se dice que requiere O(n^2) comparaciones, porque el término n^2 domina a la expresión. El número de comparaciones es proporcional al cuadrado del número de llaves en el conjunto. Así que, duplicar el número de llaves, significará que el proceso tomará cuatro veces más tiempo.

Vemos que este método de ordenamiento implementado como lo está, requiere dos veces más espacio del necesario, debido al uso de dos listas. Una modificación a este método de selección puede ser un método por selección con intercambio, en el cual la llave seleccionada es movido a su posición final por intercambio con la llave que inicialmente ocupaba esa posición. Consideremos otra vez la lista no clasificada:


Después del primer paso, 2 es seleccionado,


Después del segundo paso, 3 es el seleccionado,


Después del sexto paso,


El ordenamiento por selección con intercambio tiene esencialmente los mismos requerimientos de comparaciones que el ordenamiento por selección original, es de O(n^2).

Una implementación de este método de ordenamiento puede ser:

void Seleccion(Lista Numeros,int Largo)
{
    int pos1,menor,recorre,auxiliar;
    /*comienza en la primera posicion y llega hasta uno antes del fin*/
    for(pos1=0;pos1<(Largo-1);pos1++)
    {
        for(menor=pos1,recorre=pos1+1;recorre<Largo;recorre++)
            if(Numeros[menor]>Numeros[recorre])menor=recorre;
        auxiliar=Numeros[menor];
        Numeros[menor]=Numeros[pos1];
        Numeros[pos1]=auxiliar;
    };
};

 

Juan Garcés

Personal Blog