PDF de programación - Ordenamiento por Inserción Binaria

Andrés Felipe Ojeda

Luijy Fernando Ceballos

Generalmente, se considera ordenar (clasificar)
el proceso de reorganización de un conjunto
dado de objetos en una secuencia especificada.
El objetivo de este proceso es facilitar la
los elementos del
búsqueda posterior de
conjunto ordenado.

Hay dos diferentes tipos de Ordenamiento:
1.Ordenamiento Interno:

* Inserción directa.
* Inserción binaria.
* Intercambio directo.
* Burbuja.
* Inserción disminución incremental.
* Shell.
* Ordenamiento de árbol.
* Heap.
* Tournament.
* Sort particionado.
* Quick sort.
* Merge sort.
* Radix sort.
* Cálculo de dirección.

2. Ordenamiento Externo:

* Straight merging.

* Natural merging.

* Balanced multiway merging.

* Polyphase sort.

* Distribution of initial runs.

ORDENAMIENTO POR INSERCIÓN:

Este método toma cada elemento del arreglo para ser
ordenado y lo compara con los que se encuentran en
posiciones anteriores a la de él dentro del arreglo.

Existen 2 tipos de algoritmos:

* inserción directa.

* inserción binaria.

El ordenamiento por inserción, aunque sea un método
ineficiente y recomendable solo cuando n es pequeña, el
método de inserción binaria se comporta mejor que el
método por inserción directa.

Análisis del algoritmo:
• En el mejor de los casos, el array estará inicialmente ordenado.

F(N) = Ω(N)

• En el peor de los casos, el array está inversamente ordenado .

F(N) = O(N2)

• En el caso medio, tanto en el número de comparaciones como
en el número de asignaciones es de orden cuadrático.

F(N) = θ (N2)

• Ejemplo de ejecución: ordenación del array.
{40,21,4,9,10,35}

{40, 21, 4, 9, 10, 35}

{ 21, 40, 4, 9, 10, 35} <- el 21 ocupa su lugar

{ 4, 21, 40, 9, 10, 35} <- el 4 ocupa su lugar

{ 4, 9, 21, 40, 10, 35} <- el 9 ocupa su lugar

{ 4, 9, 10, 21, 40, 35} <- el 10 ocupa su lugar

{ 4, 9, 10, 21, 35, 40} <- el 35 ocupa su lugar

La siguiente grafica muestra la comparación
entre burbuja y la inserción de tiempo/datos y
nos muestra la ventaja que hay entre la inserción
con respecto al método de burbuja.