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.
/* C program to implement Pigeonhole Sort */
#include <bits/stdc++.h>
using namespace std;
/* Sorts the array using pigeonhole algorithm */
void pigeonholeSort(int arr[], int n)
{
// Find minimum and maximum values in arr[]
int min = arr[0], max = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] < min)
min = arr[i];
if (arr[i] > max)
max = arr[i];
}
int range = max - min + 1; // Find range
// Create an array of vectors. Size of array
// range. Each vector represents a hole that
// is going to contain matching elements.
vector<int> holes[range];
// Traverse through input array and put every
// element in its respective hole
for (int i = 0; i < n; i++)
holes[arr[i] - min].push_back(arr[i]);
// Traverse through all holes one by one. For
// every hole, take its elements and put in
// array.
int index = 0; // index in sorted array
for (int i = 0; i < range; i++) {
vector<int>::iterator it;
for (it = holes[i].begin(); it != holes[i].end(); ++it)
arr[index++] = *it;
}
}
// Driver program to test the above function
int main()
{
int arr[] = { 8, 3, 2, 7, 4, 6, 8 };
int n = sizeof(arr) / sizeof(arr[0]);
pigeonholeSort(arr, n);
printf("Sorted order is : ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
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