INSERCIÓN SIMPLE

INTERCALACIÓN SIMPLE

    El método de ordenación por intercalación es utilizado por los jugadores de cartas o naipes para ordenar sus barajas. Consiste en mirar las cartas una a una y cuando se ve cada nueva carta se inserta en el lugar adecuado. Para desarrollar el algoritmo imaginemos que las cartas se encuentran situadas en una fila encima del tapete; a medida que se ve una carta nueva, ésta se compara con la fila y se debe empujar alguna de ellas a la derecha para dejar espacio e insertar la nueva.

    Consideremos un vector de n posiciones. Comencemos con el subíndice i en la segunda posición incrementando en 1, el elemento del subíndice del vector se elimina de la secuencia y se reinserta en el vector en la posición adecuada.

Algoritmo

n=tamaño del vector
int
i,k,aux;
boolean band=false;
for (k=1;k < n; k++){
    aux=vect[k];
    i=k-1;
    band=
false;
    while( i>=0 && !band ){
        if(aux < vect[i]){
            vect[i+1]=vect[i];
            i--;
        }
        else{
            band=
true;
        }
    }
    vect[i+1]=aux;

}

 

n i k aux band vect[k] vect[i] vect[i+1] VECTOR
44 55 12 42 94 18 6 67
8 0 1 55 falso 55 44 -                
        verdadero     55 44 55 12 42 94 18 6 67
  1 2 12 falso 12 55 55 44 55 55 42 94 18 6 67
  0         44 44 44 44 55 42 94 18 6 67
  -1           12 12 44 55 42 94 18 6 67
  2 3 42 falso 42 55 55 12 44 55 55 94 18 6 67
  1         44 44 12 44 44 55 94 18 6 67
  0     verdadero   12 42 12 42 44 55 94 18 6 67
  3 4 94 falso 94 55 -                
        verdadero     94 12 42 44 55 94 18 6 67
  4 5 18 falso 18 94 94 12 42 44 55 94 94 6 67
  3         55 55 12 42 44 55 55 94 6 67
  2         44 44 12 42 44 44 55 94 6 67
  1         42 42 12 42 42 44 55 94 6 67
  0         12                  
        verdadero     18 12 18 42 44 55 94 6 67
  5 6 6 falso 6 94 94 12 18 42 44 55 94 94 67
  4         55 55 12 18 42 44 55 55 94 67
  3         44 44 12 18 42 44 44 55 94 67
  2         42 42 12 18 42 42 44 55 94 67
  1         18 18 12 18 18 42 44 55 94 67
  0         12 12 12 12 18 42 44 55 94 67
  -1           6 6 12 18 42 44 55 94 67
  6 7 67 falso 67 94 94 6 12 18 42 44 55 94 94
  5         55                  
        verdadero     67 6 12 18 42 44 55 67 94
    8                          

Si usted quiere bajar este programa haga click aquí
Si usted quiere bajar el código fuente haga click aquí