Siempre ha habido argumentos sobre cómo se puede lograr un algoritmo de clasificación de complejidad de tiempo lineal, ya que todos los algoritmos de clasificación tradicionales son al menos del orden de O (N * log (N)) en el peor de los casos.
La razón de la dificultad para lograr una complejidad de tiempo linealmente proporcional en un algoritmo de clasificación es que la mayoría de estos algoritmos de clasificación tradicionales se basan en la comparación, lo que no puede producir una salida ordenada de un conjunto de datos en tiempo lineal en el peor de los casos. Para resolver este problema, el algoritmo de clasificación hash entró en escena y es incluso más rápido que el algoritmo de clasificación tradicional más rápido, es decir, clasificación rápida .
Supuestos de Hash Sort:
Las suposiciones tomadas al implementar la ordenación Hash son:
- Los valores de los datos están dentro de un rango conocido.
- Los valores son de naturaleza numérica.
Funcionamiento del algoritmo:
Como su nombre lo dice, el algoritmo combina el concepto de hash con la clasificación.
Pero, ¿cómo se puede usar hash para clasificar? La respuesta a esto es mediante el uso de una función super-hash .
La función super-hash es una función compuesta de 2 subfunciones:
- Función hash
- Función Mash, que ayuda a la función super-hash a asignar los valores de los datos a direcciones únicas (es decir, no se producen colisiones) de manera coherente (es decir, sin dispersión de los datos).
Ahora, estos mapeos de valores de datos obtenidos de funciones súper hash son utilizados por los principales métodos de clasificación hash. Las estructuras de datos utilizadas para almacenar y clasificar los datos son arrays. Hay algunas versiones de métodos de clasificación hash, principalmente hay dos:
- Clasificación hash in situ : en este método, tanto el almacenamiento como la clasificación de los valores se producen en la misma estructura de datos.
- Clasificación hash directa : en este método, se usa una lista de datos separada para almacenar los datos y luego se realiza el mapeo en la estructura de datos multidimensional de esa lista.
Función Super-Hash:
La función Super-Hash es una combinación de dos subfunciones denominadas función hash y función mash . Estas 2 funciones se usan juntas para lograr la distinción de los valores de datos entre sí, ya que una función hash simple no puede hacer esto debido al problema de la colisión. Las dos subfunciones funcionan de las siguientes maneras para lograr el objetivo de la función super-hash:
Considere una forma genérica para un número: cx + r , donde c es un valor de magnitud, x es la base (generalmente 10) y r es el resto obtenido.
- Función Hash: Esto funciona sobre la distinción basada en el resto de los valores para el mapeo, es decir, el operador mod se aplica a los valores de los datos para obtener los restos y esos restos se utilizan para asignar los datos a una ubicación particular en el mapeo. Entonces, la función hash básica es: ( X mod N ). Pero usar este método solo causaría colisiones porque para un valor de resto dado puede haber múltiples valores de datos, por lo que no se pueden distinguir.
Ejemplo: Tomando N=10 y r=1, un conjunto equivalente de valores puede ser { 1, 11, 21, 31, 41, 51, 61, 71, 81, 91. . . . . . . c n x + 1 }, que se asignarían todos a la misma ubicación.
- Función Mash: La función Mash se llama así porque es una función hash de magnitud, lo que significa que calcula las magnitudes para mapear los valores del conjunto de datos.
Para un número cx + r , donde c es la magnitud y x es la base (generalmente se toma 10), c se calcula usando el operador div ( X div N ) en el puré en lugar del operador mod como se usa en la función hash . Pero nuevamente, los valores no se distinguen completamente entre sí usando solo la función mash y múltiples valores se asignan a una ubicación particular.
Ejemplo: Tomando N=10, c=5, obtenemos el siguiente conjunto: { 50, 51, 52, 53, 54, 55, 56, 57, 58, 59 }. Este conjunto contiene todos los valores de cx + r donde c es constante para todos los valores (c=5) y r es variable. Es por eso que para un solo valor de c obtenemos múltiples valores asignados a la misma ranura.
Ahora, para resolver esto, usamos las funciones hash y mash juntas para obtener un par ordinal único (c, r) , donde c es la magnitud obtenida usando el operador div en la función mash y r es el valor restante obtenido por el mod operador en la función hash .
Construcción de la función Super-Hash:
Consideremos el rango de valores [i, j], donde i es el límite inferior y j es el límite superior del rango. Ahora,
- Calcule la longitud del rango,
L = (j – i) + 1. - Determine el entero cuadrado más cercano ( θ ) a L por :
θ = ceil( √L ) - Ahora los valores del par ordinal se pueden calcular usando:
value(dx, mx) = dxθ + mx
Ejemplo:
Considere el rango de valores en el intervalo [ 20, 144 ], aplicando los pasos de construcción de la función super-hash:
- Calculando el valor de L ⇒ (144 – 20) + 1 = 125
- Cálculo del valor cuadrado más cercano a L ⇒ θ = techo ( √L ) = techo ( √125 ) = 12
- Ahora, para el mapeo, también restamos el límite inferior (aquí 20), de modo que todos los valores se mapeen en el rango 0. . . .(Ji).
La función súper hash resultante: F(x) = { d = (x – 20) div 12 , m = (x – 20) mod 12 }- De la función super-hash anterior, podemos encontrar que para x = 20, obtenemos el par ordinal (0, 0) y para x = 144, obtenemos (10, 4).
Clasificación hash in situ :
In-situ significa “en el sitio”, llamado así debido al funcionamiento en el lugar de esta variación. En la ordenación hash in situ, la función super-hash se usa iterativamente sobre los valores de datos para ordenar los datos. Pero antes de esto, se produce un paso de inicialización en el que se toma un valor de origen y la función super-hash lo utiliza para asignarlo a otra ubicación, donde el valor de origen se intercambia con el valor presente en esa ubicación de destino y, por lo tanto, crea un nuevo valor de origen (después del intercambio). Este proceso sigue repitiéndose hasta que no se ordenan todos los datos o al final de la lista de datos.
Pseudo-código del Algoritmo:
(v1, v2, v3, . . . . . .vn) <– inicializar // inicialización para recuperar el código fuente
While Not(End of List) Do
Temp <– get(v1, v2, v3. . . . vn) ; // intercambio de valor de origen y destino
Valor –> put(v1, v2, v3. . . ..vn);
Valor = temperatura;
(v1, v2, v3. . . . . .vn) –> super_Hash_Function(temp); // usando la función super-hash para recuperar el siguiente valor de origen
End of Loop
Siga la siguiente ilustración para una mejor comprensión del algoritmo:
Ilustración:
Consideremos una array bidimensional de 3 x 3 con valores que van del 1 al 9 para ilustrar la ordenación hash in situ:
Encontrar la longitud del rango, L = (9 – 1) + 1 = 9
Calculando el entero cuadrado más cercano a L = 9 ⇒ θ = ceil ( √9 ) = 3 , Límite inferior, i = 1
Por lo tanto, la función super-hash resultante resulta ser: d = (x – 1) / 3, m = (x – 1) % 3
Sea la configuración matricial inicial así:
Maryland 0 1 2 0 5 8 1 1 9 7 2 2 4 6 3
- Comenzando inicialmente en value(0, 0) = 5 ,
- Calcule el valor de d y m para el valor 5: d = (5- 1) div 3 = 1, m = (5 -1 ) mod 3 = 1.
- Por lo tanto, el nuevo destino está en (1, 1) con valor = 7 .
- Ahora, 5 y 7 intercambiarán sus respectivas posiciones. La array resultante será:
Maryland 0 1 2 0 7 8 1 1 9 5 2 2 4 6 3
- Nuevamente usando la posición (0, 0) con valor = 7.
- Encuentre los valores de d y m: d = (7 – 1) div 3 = 2 , m = (7 – 1) mod 3 = 0.
- Por lo tanto, la ubicación obtenida está en (2, 0) donde está presente el valor 4 .
- Entonces, 4 y 7 se intercambiarán.
Maryland 0 1 2 0 4 8 1 1 9 5 2 2 7 6 3
- En posición (0, 0) valor = 4 .
- Cálculo de d y m para x = 4: d = (4 – 1) div 3 = 1 , m = (4 – 1) mod 3 = 0.
- La posición obtenida es (1, 0) con valor de destino = 9 .
- Por lo tanto, 9 y 4 intercambiarán sus posiciones.
Maryland 0 2 2 0 9 8 1 1 4 5 2 2 7 6 3
- Ahora, en la posición (0, 0) , tenemos valor = 9 .
- Entonces, d = (9 – 1) div 3 = 2 , m = (9 – 1) mod 3 = 2
- La posición obtenida es (2, 2) con valor = 3.
- Por lo tanto, 9 y 3 intercambiarán sus posiciones.
Maryland 0 1 2 0 3 8 1 1 4 5 2 2 7 6 9
- En la posición (0, 0) valor = 3 .
- Calcule d y m, d = (3 – 1) div 3 = 0 , m = (3 – 1) mod 3 = 2.
- La posición resultante es (0, 2) con valor = 1 .
- Por lo tanto, 1 y 3 intercambiarán sus posiciones.
Maryland 0 1 2 0 1 8 3 1 4 5 2 2 7 6 9
- En la posición (0, 0) , valor = 1.
- d = (1 – 1) div 3 = 0, m = (1 – 1) módulo 3 = 0.
- La posición obtenida: (0, 0) . Este es el caso de la histéresis , donde el valor de origen se asigna a su propia ubicación. Esto causará un bucle infinito ya que 1 en (0, 0) seguirá mapeando la posición (0, 0) en sí misma.
- Entonces, para resolver esto, incrementamos la posición en 1 y obtenemos (0, 1) como nuestra nueva ubicación de origen.
- Ahora, calculando los valores de d y m para el valor = 8 en la posición (0, 1) : d = (8 – 1) div 3 = 2 , m = (8 -1) mod 3 = 1.
- La nueva ubicación obtenida es (2, 1) con valor = 6 .
- Por lo tanto, intercambiamos las posiciones de 8 y 6 .
Maryland 0 1 2 0 1 6 3 1 4 5 2 2 7 8 9
- En la posición (0, 1) valor = 6 .
- d = (6 – 1) div 3 = 1 , m = (6 – 1) mod 3 = 2.
- La nueva ubicación obtenida está en (1, 2) con valor = 2.
- Por lo tanto, 6 y 2 intercambiarán sus posiciones. La array resultante es:
Maryland 0 1 2 0 1 2 3 1 4 5 6 2 7 8 9 La array está completamente ordenada ahora, por lo que detenemos nuestra implementación aquí.
A continuación se muestra el código para implementar la ordenación hash in situ.
Java
// Java code to implement Hash Sort Algorithm
public class GFG {
// dimension values variable, i.e. 3x3 matrix
static int Dim = 3;
// function implementing Hash Sort
static void HashSort(int[][] data, int N, int low)
{
int swapCount = 0, hysteresisCount = 0;
int position = 0;
int value;
// condition to check if the end of data list is
// reached
while ((swapCount < N) && (hysteresisCount < N)) {
value = data[(position) / Dim][(position) % Dim];
int d = (value - low) / Dim;
int m = (value - low) % Dim;
// if hysteresis occurs
if (data[d][m] == value) {
// force push the position by 1 to avoid
// hysteresis
position++;
hysteresisCount++;
}
// if no hysteresis, then swap the positions
else {
int temp = data[(position) / Dim][(position) % Dim];
data[(position) / Dim][(position) % Dim] = data[d][m];
data[d][m] = temp;
swapCount++;
}
}
}
// Driver Code
public static void main(String[] args)
{
// lower range of data
int N = 1;
int[][] arr = { { 5, 8, 1 }, { 9, 7, 2 }, { 4, 6, 3 } };
HashSort(arr, 9, N);
System.out.println(
"The resultant sorted array is: ");
// printing the resultant sorted array
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
System.out.print(arr[i][j] + " ");
}
System.out.println();
}
}
}
The resultant sorted array is: 1 2 3 4 5 6 7 8 9
Análisis de Complejidad de Tiempo y Espacio:
Complejidad de tiempo: O(N)
- Las funciones de mapeo de ordenación hash tienen múltiples posibles implementaciones debido a la naturaleza extensible de la ordenación hash, por lo que podemos tomar una constante c, donde c >=1, lo que indica que se requiere al menos una asignación.
- Ahora, como la función super-hash es una función compuesta de 2 subfunciones, el tiempo total para las asignaciones será el doble de la cantidad de sub-asignaciones (indicado por c), así que multiplicamos c por 2 para obtener el tiempo necesario. para la función de mapeo para un valor de datos.
- La función de mapeo se aplicará iterativamente en cada elemento de los datos, que es n en este caso, por lo que la complejidad temporal total resulta ser: T(n) = 2.cN
Por lo tanto, T(N) = O(N)
Espacio Auxiliar: O(N)
El espacio auxiliar depende de la variación del tipo de hash utilizado.
- Para la ordenación hash in situ, la ordenación ocurre en la propia estructura de datos.
- Por lo tanto, necesitamos (N + 1) espacio para implementar el algoritmo in situ, donde N es el número de elementos en la estructura de datos y se requiere un espacio adicional para contener los valores temporales mientras se realiza el proceso de intercambio.
Por lo tanto, S(N) = O(N)
Aplicaciones de Hash Sort:
- Minería de datos: la clasificación hash puede ser útil para organizar y buscar datos en la minería de datos donde hay grandes cantidades de datos.
- Sistemas de Base de Datos: Para una recuperación eficiente de los datos.
- Sistemas Operativos: Organización de archivos.
Publicación traducida automáticamente
Artículo escrito por panwarharshit0602 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA