Ordenación por Inserción Binaria

Informática. Estructuras de Datos. Métodos clásicos de Ordenación. Inserción Directa

  • Enviado por: El remitente no desea revelar su nombre
  • Idioma: castellano
  • País: España España
  • 5 páginas
publicidad

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]

i=2

55

44

55

12

42

94

18

06

67

i=3

12

12

44

55

42

94

18

06

67

i=4

42

12

42

44

55

94

18

06

67

i=5

94

12

42

44

55

94

18

06

67

i=6

18

12

18

42

44

55

94

06

67

i=7

06

06

12

18

42

44

55

94

67

i=8

67

06

12

18

42

44

55

67

94

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.