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.
# Python program to implement Pigeonhole Sort */ # source code : "https://en.wikibooks.org/wiki/ # Algorithm_Implementation/Sorting/Pigeonhole_sort" def pigeonhole_sort(a): # size of range of values in the list # (ie, number of pigeonholes we need) my_min = min(a) my_max = max(a) size = my_max - my_min + 1 # our list of pigeonholes holes = [0] * size # Populate the pigeonholes. for x in a: assert type(x) is int, "integers only please" holes[x - my_min] += 1 # Put the elements back into the array in order. i = 0 for count in range(size): while holes[count] > 0: holes[count] -= 1 a[i] = count + my_min i += 1 a = [8, 3, 2, 7, 4, 6, 8] print("Sorted order is : ", end =" ") pigeonhole_sort(a) for i in range(0, len(a)): print(a[i], end =" ")
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