La clasificación por casilleros es un algoritmo de clasificación que es adecuado para clasificar listas de elementos donde el número de elementos y el número de valores clave posibles son aproximadamente los mismos.
Requiere tiempo O ( n + Rango ), donde n es el número de elementos en la array de entrada y ‘Rango’ es el número de valores posibles en la array.
Funcionamiento del algoritmo:
- Encuentre valores mínimos y máximos en la array. Deje que los valores mínimo y máximo sean ‘min’ y ‘max’ respectivamente. También encuentre el rango como ‘max-min-1’.
- Configure una array de «casilleros» inicialmente vacíos del mismo tamaño que el rango.
- Visite cada elemento de la array y luego coloque cada elemento en su casillero. Un elemento arr[i] se coloca en el agujero en el índice arr[i] – min.
- Inicie el bucle en todo el conjunto de casilleros en orden y vuelva a colocar los elementos de los agujeros no vacíos en el conjunto original.
/* Java program to implement Pigeonhole Sort */
import java.lang.*;
import java.util.*;
public class GFG {
public static void pigeonhole_sort(int arr[],
int n)
{
int min = arr[0];
int max = arr[0];
int range, i, j, index;
for (int a = 0; a < n; a++) {
if (arr[a] > max)
max = arr[a];
if (arr[a] < min)
min = arr[a];
}
range = max - min + 1;
int[] phole = new int[range];
Arrays.fill(phole, 0);
for (i = 0; i < n; i++)
phole[arr[i] - min]++;
index = 0;
for (j = 0; j < range; j++)
while (phole[j]-- > 0)
arr[index++] = j + min;
}
public static void main(String[] args)
{
GFG sort = new GFG();
int[] arr = { 8, 3, 2, 7, 4, 6, 8 };
System.out.print("Sorted order is : ");
sort.pigeonhole_sort(arr, arr.length);
for (int i = 0; i < arr.length; i++)
System.out.print(arr[i] + " ");
}
}
// Code contributed by Mohit Gupta_OMG <(0_o)>
Producción:
Sorted order is : 2 3 4 6 7 8 8
¡ Consulte el artículo completo sobre la clasificación Pigeonhole 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