Insercion binaria

METODO DE ORDENACION POR INSERCION BINARIA

RESUMEN
Mayormente este método se usa después de haber acomodado los números en un arreglo ordenado, se hace esto para el ahorro de tiempo ya que tomaría el doble de tiempo y lo que se busca en un algoritmo busca es que tenga rapidez y eficacia (pero también se podría usar en cualquier orden). Y como se podrán dar cuenta más adelante este método deinserción binaria es muy parecida al anterior (inserción directa), excepto que la búsqueda del orden de un elemento en la sublista ordenada se realiza mediante una búsqueda binaria, lo que en principio supone un ahorro de tiempo. No obstante, dado que para la inserción sigue siendo necesario un desplazamiento de los elementos, el ahorro, en la mayoría de los casos, no se produce, si bien haycompiladores que realizan optimizaciones que lo hacen ligeramente más rápido.
Voy a mostrarles en un ejemplo como trabaja el algoritmo de inserción binaria, este algoritmo es bastante sencillo. ¿Has jugado cartas? ¿Cómo las vas ordenando cuando las recibes? Yo lo hago de esta manera: tomo la primera y la coloco en mi mano. Luego tomo la segunda y la comparo con la que tengo: si es mayor, la pongo a laderecha, y si es menor a la izquierda (también me fijo en el color, pero omitiré esa parte para concentrarme en la idea principal). Después tomo la tercera y la comparo con las que tengo en la mano, desplazándola hasta que quede en su posición final. Continúo haciendo esto, insertando cada carta en la posición que le corresponde, hasta que las tengo todas en orden. ¿Lo haces así tú también?Bueno, pues si es así entonces comprenderás fácilmente este algoritmo, porque es el mismo concepto.
Para simular esto en un programa necesitamos tener en cuenta algo: no podemos desplazar los elementos así como así o se perderá un elemento. Lo que hacemos es guardar una copia del elemento actual (que sería como la carta que tomamos) y desplazar todos los elementos mayores hacia la derecha. Luegocopiamos el elemento guardado en la posición del último elemento que se desplazó.
En resumen, este algoritmo sigue estos pasos:
* Toma un elemento en la posición i.
* Búsqueda Binaria para localizar el lugar de inserción
* Mueve hacia la derecha los restantes.
* Lo inserta.
CONTENIDO:
1. ORIGEN :
Es el mismo método que la inserción directa, excepto que la búsqueda del orden deun elemento en la sublista ordenada se realiza mediante una búsqueda binaria (ver algoritmos de búsqueda), lo que en principio supone un ahorro de tiempo. No obstante, dado que para la inserción sigue siendo necesario un desplazamiento de los elementos, el ahorro, en la mayoría de los casos, no se produce, si bien hay compiladores que realizan optimizaciones que lo hacen ligeramente más rápido.2. DEFINICION
Este método se basa en considerar una parte de lista ordenada y situar cada uno de los elementos insertándolo en el lugar que le corresponda por su valor, todos los valores a la derecha se desplazan una posición para dejar espacio.

3. CLASIFICACION
El algoritmo de inserción directa se mejora fácilmente al notar que la secuencia destino aj...ai-1, donde debe insertarse elnuevo 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.

4. CARACTERISITCAS

1.- La secuencia destinodonde debe insertarse el nuevo elemento ya está 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.
para (i=2 hasta N) { aux = A[i]; izq=1; der=i-1; mientras (izq<=der) { m=[parte entera ((izq+der)/2)]; si (aux<A[m]) {...