INSERCIÓN BINARIA.-

El algoritmo de inserción directa se mejora fácilmente al notar que la secuencia destino aj..ai-1, donde debe insertarse el nuevo elemento, ya está ordenada . Por eso puede ser empleado un método más rápido para determinar el punto de inserción . La elección obvia es una búsqueda binaria que prueba la secuencia destino en la mitad y continúa buscando hasta encontrar el punto

de inserción. El algoritmo de clasificación modificado recibe el nombre de inserción binaria.

PROCEDURE InsercionBinaria;

VAR

i,j,m,L,R:index;

x:item;

BEGIN

FOR i=2 TO n DO

x=a[i];

L:=1;

R:=i;

WHILE L<R DO

m:=(L+R) DIV 2;

IF a[m] <=x THEN L:=m+1 ELSE R:=m END

END;

FOR j=i TO R+1 BY -1 DO

a[j]:=a[j-1] (*desplazamiento*)

END;

a[R]:=x(*insercion*)

END

END InserciónBinaria

X a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8]

Carácteristicas fundamentales:

1.- La secuencia destino donde debe insertarse el nuevo elemento ya esta ordenada.

2.-Búsqueda Binaria para localizar el lugar de inserción.

3.-Desplazar elementos.

4.-Insertar.

Análisis:

Al realizar la búsqueda binaria se divide una longitud L por la mitad un número determinado de veces.