domingo, 17 de mayo de 2009

Ordenacion Binaria

ORDENACION 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 Lm:=(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

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

No hay comentarios:

Publicar un comentario en la entrada