Ordenar usando la función hash trivial

Hemos leído acerca de varios algoritmos de clasificación, como la clasificación de montones , la clasificación de burbujas, la clasificación de combinación y otros. 
Aquí veremos cómo podemos ordenar N elementos usando una array hash. Pero este algoritmo tiene una limitación. Podemos ordenar solo esos N elementos, donde el valor de los elementos no es grande (típicamente no más de 10 ^ 6).

Ejemplos:  

Entrada: 9 4 3 5 8 
Salida: 3 4 5 8 9

Explicación de la clasificación usando hash:

  • Paso 1: Cree una array hash de tamaño (max_element), ya que ese es el máximo que necesitaremos 
  • Paso 2: recorrer todos los elementos y mantener un recuento del número de ocurrencias de un elemento en particular. 
  • Paso 3: después de llevar un recuento de la ocurrencia de todos los elementos en la tabla hash, simplemente itere de 0 a max_element en la array hash 
  • Paso 4: mientras iteramos en la array hash, si encontramos que el valor almacenado en cualquier posición hash es mayor que 0, lo que indica que el elemento está presente al menos una vez en la lista original de elementos. 
  • Paso 5: Hash[i] tiene el conteo de la cantidad de veces que un elemento está presente en la lista, por lo que cuando es> 0, imprimimos esa cantidad de veces que el elemento. 
     
  • Si desea almacenar los elementos, use otra array para almacenarlos de forma ordenada. 
  • Si queremos ordenarlo en orden descendente, simplemente pasamos de max a 0 y repetimos el mismo procedimiento.

A continuación se muestra la implementación del enfoque anterior: 

C++

// C++ program to sort an array using hash
// function
#include <bits/stdc++.h>
using namespace std;
 
void sortUsingHash(int a[], int n)
{
    // find the maximum element
    int max = *std::max_element(a, a + n);
 
    // create a hash function upto the max size
    int hash[max + 1] = { 0 };
 
    // traverse through all the elements and
    // keep a count
    for (int i = 0; i < n; i++)
        hash[a[i]] += 1;
 
    // Traverse upto all elements and check if
    // it is present or not. If it is present,
    // then print the element the number of times
    // it's present. Once we have printed n times,
    // that means we have printed n elements
    // so break out of the loop
    for (int i = 0; i <= max; i++) {
 
        // if present
        if (hash[i]) {
 
            // print the element that number of
            // times it's present
            for (int j = 0; j < hash[i]; j++) {
                cout << i << " ";
            }
        }
    }
}
 
// driver program
int main()
{
    int a[] = { 9, 4, 3,  2,  5,  2,  1,  0, 4,
                3, 5, 10, 15, 12, 18, 20, 19 };
    int n = sizeof(a) / sizeof(a[0]);
 
    sortUsingHash(a, n);
    return 0;
}

Java

// Java program to sort an array using hash
// function
import java.util.*;
 
class GFG {
 
    static void sortUsingHash(int a[], int n)
    {
        // find the maximum element
        int max = Arrays.stream(a).max().getAsInt();
 
        // create a hash function upto the max size
        int hash[] = new int[max + 1];
 
        // traverse through all the elements and
        // keep a count
        for (int i = 0; i < n; i++)
            hash[a[i]] += 1;
 
        // Traverse upto all elements and check if
        // it is present or not. If it is present,
        // then print the element the number of times
        // it's present. Once we have printed n times,
        // that means we have printed n elements
        // so break out of the loop
        for (int i = 0; i <= max; i++) {
 
            // if present
            if (hash[i] != 0) {
 
                // print the element that number of
                // times it's present
                for (int j = 0; j < hash[i]; j++) {
                    System.out.print(i + " ");
                }
            }
        }
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int a[] = { 9, 4, 3,  2,  5,  2,  1,  0, 4,
                    3, 5, 10, 15, 12, 18, 20, 19 };
        int n = a.length;
 
        sortUsingHash(a, n);
    }
}
 
// This code contributed by Rajput-Ji

Python3

# Python3 program to sort an array
# using hash function
 
 
def sortUsingHash(a, n):
 
    # find the maximum element
    Max = max(a)
 
    # create a hash function upto
    # the max size
    Hash = [0] * (Max + 1)
 
    # traverse through all the elements
    # and keep a count
    for i in range(0, n):
        Hash[a[i]] += 1
 
    # Traverse upto all elements and check
    # if it is present or not. If it is
    # present, then print the element the
    # number of times it's present. Once we
    # have printed n times, that means we
    # have printed n elements so break out
    # of the loop
    for i in range(0, Max + 1):
 
        # if present
        if Hash[i] != 0:
 
            # print the element that number
            # of times it's present
            for j in range(0, Hash[i]):
                print(i, end=" ")
 
 
# Driver Code
if __name__ == "__main__":
 
    a = [9, 4, 3, 2, 5, 2, 1, 0, 4,
         3, 5, 10, 15, 12, 18, 20, 19]
    n = len(a)
 
    sortUsingHash(a, n)
 
# This code is contributed by Rituraj Jain

C#

// C# program to sort an array using hash
// function
using System;
using System.Linq;
 
class GFG {
 
    static void sortUsingHash(int[] a, int n)
    {
        // find the maximum element
        int max = a.Max();
 
        // create a hash function upto the max size
        int[] hash = new int[max + 1];
 
        // traverse through all the elements and
        // keep a count
        for (int i = 0; i < n; i++)
            hash[a[i]] += 1;
 
        // Traverse upto all elements and check if
        // it is present or not. If it is present,
        // then print the element the number of times
        // it's present. Once we have printed n times,
        // that means we have printed n elements
        // so break out of the loop
        for (int i = 0; i <= max; i++) {
 
            // if present
            if (hash[i] != 0) {
 
                // print the element that number of
                // times it's present
                for (int j = 0; j < hash[i]; j++) {
                    Console.Write(i + " ");
                }
            }
        }
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        int[] a = { 9, 4, 3,  2,  5,  2,  1,  0, 4,
                    3, 5, 10, 15, 12, 18, 20, 19 };
        int n = a.Length;
 
        sortUsingHash(a, n);
    }
}
 
/* This code contributed by PrinciRaj1992 */

Javascript

<script>
// javascript program to sort an array using hash
// function
 
    function sortUsingHash(a, n) {
        // find the maximum element
        var max = Math.max.apply(Math, a);
 
        // create a hash function upto the max size
        var hash = Array(max + 1).fill(0);
 
        // traverse through all the elements and
        // keep a count
        for (i = 0; i < n; i++)
            hash[a[i]] += 1;
 
        // Traverse upto all elements and check if
        // it is present or not. If it is present,
        // then print the element the number of times
        // it's present. Once we have printed n times,
        // that means we have printed n elements
        // so break out of the loop
        for (i = 0; i <= max; i++) {
 
            // if present
            if (hash[i] != 0) {
 
                // print the element that number of
                // times it's present
                for (j = 0; j < hash[i]; j++) {
                    document.write(i + " ");
                }
            }
        }
    }
 
    // Driver code
     
        var a = [ 9, 4, 3, 2, 5, 2, 1, 0, 4, 3, 5, 10, 15, 12, 18, 20, 19 ];
        var n = a.length;
 
        sortUsingHash(a, n);
 
// This code contributed by Rajput-Ji
</script>
Producción

0 1 2 2 3 3 4 4 5 5 9 10 12 15 18 19 20 

¿Cómo manejar los números negativos? 

En caso de que la array tenga números negativos y números positivos , mantenemos dos arrays hash para realizar un seguimiento de los elementos positivos y negativos.

Explicación de la clasificación mediante hashing si la array tiene números negativos y positivos: 

  • Paso 1 : cree dos arrays hash, una para positivo y la otra para negativo 
  • Paso 2: la array hash positiva tendrá un tamaño máximo y la array negativa tendrá un tamaño mínimo 
  • Paso 3: recorra de min a 0 en la array hash negativa e imprima los elementos de la misma manera que lo hicimos para los positivos. 
  • Paso 4: Recorra de 0 a max para elementos positivos e imprímalos de la misma manera que se explicó anteriormente. 

A continuación se muestra la implementación del enfoque anterior: 

C++

// C++ program to sort an array using hash
// function with negative values allowed.
#include <bits/stdc++.h>
using namespace std;
 
void sortUsingHash(int a[], int n)
{
    // find the maximum element
    int max = *std::max_element(a, a + n);
    int min = abs(*std::min_element(a, a + n));
 
    // create a hash function upto the max size
    int hashpos[max + 1] = { 0 };
    int hashneg[min + 1] = { 0 };
 
    // traverse through all the elements and
    // keep a count
    for (int i = 0; i < n; i++) {
        if (a[i] >= 0)
            hashpos[a[i]] += 1;
        else
            hashneg[abs(a[i])] += 1;
    }
 
    // Traverse up to all negative elements and
    // check if it is present or not. If it is
    // present, then print the element the number
    // of times it's present. Once we have printed
    // n times, that means we have printed n elements
    // so break out of the loop
    for (int i = min; i > 0; i--) {
        if (hashneg[i]) {
 
            // print the element that number of times
            // it's present. Print the negative element
            for (int j = 0; j < hashneg[i]; j++) {
                cout << (-1) * i << " ";
            }
        }
    }
 
    // Traverse upto all elements and check if it is
    // present or not. If it is present, then print
    // the element the number of times it's present
    // once we have printed n times, that means we
    // have printed n elements, so break out of the
    // loop
    for (int i = 0; i <= max; i++) {
 
        // if present
        if (hashpos[i]) {
 
            // print the element that number of times
            // it's present
            for (int j = 0; j < hashpos[i]; j++) {
                cout << i << " ";
            }
        }
    }
}
 
// driver program to test the above function
int main()
{
    int a[] = { -1, -2, -3, -4, -5, -6, 8,
                7,  5,  4,  3,  2,  1,  0 };
    int n = sizeof(a) / sizeof(a[0]);
    sortUsingHash(a, n);
    return 0;
}

Java

// Java program to sort an array using hash
// function with negative values allowed.
import java.util.Arrays;
class GFG {
 
    static int absolute(int x)
    {
        if (x < 0)
            return (-1 * x);
        return x;
    }
 
    static void sortUsingHash(int a[], int n)
    {
        // find the maximum element
        int max = Arrays.stream(a).max().getAsInt();
        int min
            = absolute(Arrays.stream(a).min().getAsInt());
 
        // create a hash function upto the max size
        int hashpos[] = new int[max + 1];
        int hashneg[] = new int[min + 1];
 
        // traverse through all the elements and
        // keep a count
        for (int i = 0; i < n; i++) {
            if (a[i] >= 0)
                hashpos[a[i]] += 1;
            else
                hashneg[absolute(a[i])] += 1;
        }
 
        // Traverse up to all negative elements and
        // check if it is present or not. If it is
        // present, then print the element the number
        // of times it's present. Once we have printed
        // n times, that means we have printed n elements
        // so break out of the loop
        for (int i = min; i > 0; i--) {
            if (hashneg[i] > 0) {
 
                // print the element that number of times
                // it's present. Print the negative element
                for (int j = 0; j < hashneg[i]; j++) {
                    System.out.print((-1) * i + " ");
                }
            }
        }
 
        // Traverse upto all elements and check if it is
        // present or not. If it is present, then print
        // the element the number of times it's present
        // once we have printed n times, that means we
        // have printed n elements, so break out of the
        // loop
        for (int i = 0; i <= max; i++) {
 
            // if present
            if (hashpos[i] > 0) {
 
                // print the element that number of times
                // it's present
                for (int j = 0; j < hashpos[i]; j++) {
                    System.out.print(i + " ");
                }
            }
        }
    }
 
    // Driver program to test the above function
    public static void main(String[] args)
    {
        int a[] = { -1, -2, -3, -4, -5, -6, 8,
                    7,  5,  4,  3,  2,  1,  0 };
        int n = a.length;
        sortUsingHash(a, n);
    }
}
 
// This code has been contributed by 29AjayKumar

Python3

# Python3 program to sort an array using hash
# function with negative values allowed.
 
 
def sortUsingHash(a, n):
 
    # find the maximum element
    Max = max(a)
    Min = abs(min(a))
 
    # create a hash function upto the max size
    hashpos = [0] * (Max + 1)
    hashneg = [0] * (Min + 1)
 
    # traverse through all the elements and
    # keep a count
    for i in range(0, n):
        if a[i] >= 0:
            hashpos[a[i]] += 1
        else:
            hashneg[abs(a[i])] += 1
 
    # Traverse up to all negative elements
    # and check if it is present or not.
    # If it is present, then print the
    # element the number of times it's present.
    # Once we have printed n times, that means
    # we have printed n elements so break out
    # of the loop
    for i in range(Min, 0, -1):
        if hashneg[i] != 0:
 
            # print the element that number of times
            # it's present. Print the negative element
            for j in range(0, hashneg[i]):
                print((-1) * i, end=" ")
 
    # Traverse upto all elements and check if
    # it is present or not. If it is present,
    # then print the element the number of
    # times it's present once we have printed
    # n times, that means we have printed n
    # elements, so break out of the loop
    for i in range(0, Max + 1):
 
        # if present
        if hashpos[i] != 0:
 
            # print the element that number
            # of times it's present
            for j in range(0, hashpos[i]):
                print(i, end=" ")
 
 
# Driver Code
if __name__ == "__main__":
 
    a = [-1, -2, -3, -4, -5, -6,
         8, 7, 5, 4, 3, 2, 1, 0]
 
    n = len(a)
    sortUsingHash(a, n)
 
# This code is contributed by Rituraj Jain

C#

// C# program to sort an array using hash
// function with negative values allowed.
using System;
using System.Linq;
 
class GFG {
 
    static int absolute(int x)
    {
        if (x < 0)
            return (-1 * x);
        return x;
    }
 
    static void sortUsingHash(int[] a, int n)
    {
        // find the maximum element
        int max = a.Max();
        int min = absolute(a.Min());
 
        // create a hash function upto the max size
        int[] hashpos = new int[max + 1];
        int[] hashneg = new int[min + 1];
 
        // traverse through all the elements and
        // keep a count
        for (int i = 0; i < n; i++) {
            if (a[i] >= 0)
                hashpos[a[i]] += 1;
            else
                hashneg[absolute(a[i])] += 1;
        }
 
        // Traverse up to all negative elements and
        // check if it is present or not. If it is
        // present, then print the element the number
        // of times it's present. Once we have printed
        // n times, that means we have printed n elements
        // so break out of the loop
        for (int i = min; i > 0; i--) {
            if (hashneg[i] > 0) {
 
                // print the element that number of times
                // it's present. Print the negative element
                for (int j = 0; j < hashneg[i]; j++) {
                    Console.Write((-1) * i + " ");
                }
            }
        }
 
        // Traverse upto all elements and check if it is
        // present or not. If it is present, then print
        // the element the number of times it's present
        // once we have printed n times, that means we
        // have printed n elements, so break out of the
        // loop
        for (int i = 0; i <= max; i++) {
 
            // if present
            if (hashpos[i] > 0) {
 
                // print the element that number of times
                // it's present
                for (int j = 0; j < hashpos[i]; j++) {
                    Console.Write(i + " ");
                }
            }
        }
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        int[] a = { -1, -2, -3, -4, -5, -6, 8,
                    7,  5,  4,  3,  2,  1,  0 };
        int n = a.Length;
        sortUsingHash(a, n);
    }
}
 
/* This code contributed by PrinciRaj1992 */

Javascript

<script>
// javascript program to sort an array using hash
// function with negative values allowed.
 
 
function absolute(int x){
    if(x<0)    return (-1*x);
    return x;
}
 
    function sortUsingHash(a, n) {
        // find the maximum element
        var max = Math.max.apply(Math, a);
        var min = absolute(Math.min.apply(Math, a));
 
        // create a hash function upto the max size
        var hashpos =  Array(max).fill(0);
        var hashneg = Array(min + 1).fill(0);
 
        // traverse through all the elements and
        // keep a count
        for (i = 0; i < n; i++) {
            if (a[i] >= 0)
                hashpos[a[i]] += 1;
            else
                hashneg[absolute(a[i])] += 1;
        }
 
        // Traverse up to all negative elements and
        // check if it is present or not. If it is
        // present, then print the element the number
        // of times it's present. Once we have printed
        // n times, that means we have printed n elements
        // so break out of the loop
        for (i = min; i > 0; i--) {
            if (hashneg[i] > 0) {
 
                // print the element that number of times
                // it's present. Print the negative element
                for (j = 0; j < hashneg[i]; j++) {
                    document.write((-1) * i + " ");
                }
            }
        }
 
        // Traverse upto all elements and check if it is
        // present or not. If it is present, then print
        // the element the number of times it's present
        // once we have printed n times, that means we
        // have printed n elements, so break out of the
        // loop
        for (i = 0; i <= max; i++) {
 
            // if present
            if (hashpos[i] > 0) {
 
                // print the element that number of times
                // it's present
                for (j = 0; j < hashpos[i]; j++) {
                    document.write(i + " ");
                }
            }
        }
    }
 
    // Driver program to test the above function
     
        var a = [ -1, -2, -3, -4, -5, -6, 8, 7, 5, 4, 3, 2, 1, 0 ];
        var n = a.length;
        sortUsingHash(a, n);
 
// This code contributed by Rajput-Ji
</script>
Producción

-6 -5 -4 -3 -2 -1 0 1 2 3 4 5 7 8 

Complejidad: 
esta función de clasificación puede tener una complejidad O (max_element). Entonces, el rendimiento depende de ese conjunto de datos proporcionado.

Limitaciones: 

  1. Solo puede ordenar elementos de array de rango limitado (generalmente de -10 ^ 6 a +10 ^ 6) 
  2. El espacio auxiliar en el peor de los casos es O(max_element) + O(min_element)

Publicación traducida automáticamente

Artículo escrito por Striver y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *