/**
* Podemos usar la búsqueda binaria para reducir el número de comparaciones
* en la ordenación por inserción normal. La ordenación por inserción binaria
* utiliza la búsqueda binaria para encontrar la ubicación adecuada para
* insertar el elemento seleccionado en cada iteración.
* En la ordenación por inserción normal, se usan O(n) comparaciones
* (en la iteración n-ésima) en el peor de los casos.
* Podemos reducir las comparaciones a O(log n) usando la búsqueda binaria.
*/
// Programa en C++ para la implementación de
// clasificación por inserción binaria
#include <iostream>
using namespace std;
// Una función basada en búsqueda binaria
// para encontrar la posición
// donde se debe insertar el elemento
// en a[low..high]
int binarySearch(int a[], int item, int low, int high)
{
if (high <= low)
return (item > a[low]) ? (low+1) : low;
int mid = (low + high)/2;
if (item == a[mid])
return mid+1;
if (item > a[mid])
return binarySearch(a, item, mid+1, high);
return binarySearch(a, item, low, mid-s1);
}
// Función para ordenar una matriz a[] de tamaño 'n'
void insertionSort(int a[], int n)
{
int loc, j, k, selected;
for(int i=1; i<n; ++i){
j = i-1;
selected = a[i];
// encontrar la ubicación donde se debe insertar selected
loc = binarySearch(a, selected, 0, j);
// Mueve todos los elementos después de la ubicación para crear espacio
while(j >= loc){
a[j+1] = a[j];
j--;
}
a[j+1] = selected;
}
}
// Pruebas
int main()
{
int a[] = {37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54};
int n = sizeof(a)/sizeof(a[0]);
insertionSort(a, n);
cout<<"Arreglo Ordenado: \n";
for (int i=0; i<n; i++)
cout<<a[i]<<" ";
return 0;
}
