Ordenamiento por inserción directa
---------------------------------------------------------------
El método de ordenación por inserción directa consiste en recorrer todo
el array comenzando desde el segundo elemento hasta el final. Para
cada elemento, se trata de colocarlo en el lugar correcto entre todos los
elementos anteriores a él o sea entre los elementos a su izquierda en el
array.
Dada una posición actual p, el algoritmo se basa en que los elementos
A[0], A[1], ..., A[p-1] ya están ordenados.
public static void insercionDirecta(int A[]){
int p, j;
int aux;
for (p = 1; p < A.length; p++){ // desde el segundo elemento hasta
aux = A[p]; // el final, guardamos el elemento y
j = p - 1; // empezamos a comprobar con el anterior
while ((j >= 0) && (aux < A[j])){ // mientras queden posiciones
y el
// valor de aux sea menor que los
A[j + 1] = A[j]; // de la izquierda, se desplaza a
j--; // la derecha
A[j + 1] = aux; // colocamos aux en su sitio
Programación Java: Ordenamiento por Inserción directa
Ordenamiento por inserción binaria
Es una variante del método de inserción directa, en la que se sustituye
la búsqueda secuencial por una búsqueda binaria (que se puede aplicar
dado que la zona de búsqueda contiene elementos ordenados).
Para cada elemento ai comprendido entre las posiciones 2 y N:
1. Se aplica una búsqueda binaria entre las posiciones [1, I-1], para
determinar la posición que debería ocupar el elemento a ordenar,
respecto a los de dicho intervalo.
2. Todos los elementos del intervalo anterior que sean mayores que
el que se pretende colocar, se desplazarán una posición a la
derecha.
3. Se coloca el valor en su nueva posición, ya en orden.
PSEUDOCÓDIGO
MÓDULO ordenacion_insercion_binaria
DATOS
PARÁMETROS
Transforma V() de tipo T
Recibe N entera
VARIABLES
I, J enteras
AUX de tipo T
INICIO
Para I desde 2 hasta N
AUX ← V(I)
IZQ ← 1
DER ← I-1
Mientras ( IZQ ≤ DER ) hacer
CEN ← (IZQ+DER)\ 2 ** división entera
Si ( V(CEN) ≤ AUX ) entonces
IZQ ← CEN+1
sino
DER ← CEN-1
fin-si
fin-mientras
J ← I
Mientras (J > IZQ) hacer
V(J) ← V(J-1)
J ← J-1
fin-mientras
V(IZQ) ← AUX
fin-para
FIN
CÓDIGO C
/*Ordena un vector (de menor a mayor) por el método de inserción
binaria*/
ordInsBinaria(int *v, int n)
{
int i, j, aux, izq, der, cen;
for(i=1;i<n;i++)
{
aux=v[i];
izq=0;
der=i-1;
while(izq<=der)
{
cen=(izq+der)/2;
if(v[cen]>aux)
{
der=cen-1;
}
else
{
izq=cen+1;
}
}
j=i;
while(j>izq)
{
v[j]=v[j-1];
j=j-1;
}
v[izq]=aux;
}
}
Algoritmo de Ordenación por Inserción Binaria
