Juan Garcés

Personal Blog

Métodos de Ordenamiento

enero 25th, 2013

Ordenamiento por Inserción

 

La idea básica de una clasificación por inserción es tomar la siguiente llave de una lista no clasificada e insertarla en su posición relativa correspondiente en una lista creciente de datos clasificados.


La lista completa de llaves ordenadas deberá estar disponible, a lo largo del proceso, para poder insertar una llave en su posición relativa apropiada. La lista puede alimentarse durante el proceso.

Compare esta técnica de ordenamiento con el método de ordenamiento por selección. Cuando usted ordena una mano de cartas de juego, si usted toma cada carta cuando se la entregan y la coloca en la ranura apropiada, con respecto a las demás cartas que ya tiene, entonces está usando un ordenamiento por inserción. Sin embargo, si usted espera hasta que ña mano entera se reparta, después procede a identificar qué carta debe ir más a la izquierda y la coloca, y así para cada una, se dice entonces que está usando ordenamiento por selección.
Ambas técnicas son relativamente pobres, pues cada una es de O(n^2), pero cada una es relativamente fácil, de comprender y de programar. Ambas son muy utilizadas.

Considere otra vez nuestro ejemplo de listas de llaves no clasificadas:


Como con el método de ordenamiento por selección, el ordenamiento por inserción también puede ser implementado para que funcione sobre una sola lista (o espacio de trabajo) al hacer que el elemento que se está analizando sea insertado entre los que ya han sido analizados y ordenados, vemos esto gráficamente:


Se mueve el elemento (en este caso el 2) hasta la posición que le corresponde y luego se sigue con los demás en la misma forma, lográndose el efecto de la inserción.

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

void Insercion(Lista Numeros, int Largo)
{
    int pos1, auxiliar,pos2;
    for(pos1=1;pos1<Largo;pos1++)
    {
        pos2=pos1;
        while((pos2>0)&&(Numeros[pos2]<Numeros[pos2-1]))
        {
            auxiliar=Numeros[pos2];
            Numeros[pos2]=Numeros[pos2-1];
            Numeros[pos2-1]=auxiliar;
            pos2–;
        };
    };
};

 

Juan Garcés

Personal Blog