Podemos utilizar la búsqueda binaria para reducir el número de comparaciones en la ordenación por inserción normal . Búsqueda de ordenación por inserción binaria Utilice la búsqueda binaria para encontrar la ubicación adecuada para insertar el elemento seleccionado en cada iteración. En la inserción normal, la ordenación toma O(i) (en la i-ésima iteración) en el peor de los casos. podemos reducirlo a O(logi) usando la búsqueda binaria .
Java
Java
// Java Program implementing
// binary insertion sort
import java.util.Arrays;
class GFG
{
public static void main(String[] args)
{
final int[] arr = {37, 23, 0, 17, 12, 72, 31,
46, 100, 88, 54 };
new GFG().sort(arr);
for(int i=0; i<arr.length; i++)
System.out.print(arr[i]+" ");
}
public void sort(int array[])
{
for (int i = 1; i < array.length; i++)
{
int x = array[i];
// Find location to insert using binary search
int j = Math.abs(Arrays.binarySearch(array, 0, i, x) + 1);
//Shifting array to one location right
System.arraycopy(array, j, array, j+1, i-j);
//Placing element at its correct location
array[j] = x;
}
}
}
// Code contributed by Mohit Gupta_OMG
Complejidad de tiempo : O(n 2 ) El algoritmo en su conjunto todavía tiene un tiempo de ejecución en el peor de los casos de O(n 2 ) debido a la serie de intercambios necesarios para cada inserción.
Espacio Auxiliar : O(1)
Consulte el artículo completo sobre ordenación por inserción binaria para obtener más detalles.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA