Sorting using trivial hash function

The problem “Sorting using trivial hash function” states that you are given an integer array. An array can be containing both negative and positive numbers. The problem statement asks to sort the array using Trivial Hash Function.

Example

arr[] = {5,2,1,3,6}

{1, 2, 3, 5, 6}

arr[] = {-3, -1, 4, 3, -2, 1, 2, 0}

{-3, -2,-1, 0, 1, 2, 3, 4}

Explanation

All the elements are sorted in both the outputs. thus the outputs are correct.

Algorithm

1. Find out the maximum and minimum element of an array (minimum element but with the absolute value).
2. Create arrays of size maximum element and minimum element.
3. Increase the count of both the arrays by 1 for each element accordingly if it is greater than 0 or less than 0 and store it in both of the arrays respectively.
4. Print the array which has a negative element count, as no of times as it occurs. Do the same thing with the positive element.
5. We will have the sorted array.

Explanation

We are given an array, it can contain positive and negative integers. Our task is to sort the array using the Trivial Hash function. To solve this we will use hashing and initialize two arrays. Find the maximum and minimum element (the minimum element with the absolute value). One is for negative elements and the other one is for the positive elements. Size of both of the arrays should be equal to maximum element of input and negative elements of the input but with the absolute value.

We will be traversing the given array, and checking a condition if an array element is greater than 0, we will be increasing its occurrence by 1 in a positive element array and if it is less than 0, it means the number is negative, we will be increasing its occurrence by 1 in a negative element array. After the traversal, we have the count of each given array element in both of the arrays we created.

Now, we need to print those elements in a sorted manner. So we will take first the negative element array, we need to start from the minimum element but with the negative sign and print as the number of times as it occurs and decreasing the value until we finished printing all the negative values.

Now starting from 0, we will print all the positive elements of the array, as no of times as it occurs up to the maximum element in the array. But we have to make sure we found the correct value as maximum and minimum in an array and print negative element array value with the negative sign or after multiplying it with -1. After the completion, we had printed a sorted array.

C++ code to perform Sorting using trivial hash function

#include<iostream>
#include<unordered_map>
#include<algorithm>

using namespace std;

void sortUsingHash(int arr[], int n)
{
    int max = *std::max_element(arr, arr + n);
    int min = abs(*std::min_element(arr, arr + n));

    int positiveNum[max + 1] = { 0 };
    int negativeNum[min + 1] = { 0 };

    for (int i = 0; i < n; i++)
    {
        if (arr[i] >= 0)
            positiveNum[arr[i]] += 1;
        else
            negativeNum[abs(arr[i])] += 1;
    }
    for (int i = min; i > 0; i--)
    {
        if (negativeNum[i])
        {
            for (int j = 0; j < negativeNum[i]; j++)
            {
                cout << (-1) * i << " ";
            }
        }
    }
    for (int i = 0; i <= max; i++)
    {
        if (positiveNum[i])
        {
            for (int j = 0; j < positiveNum[i]; j++)
            {
                cout << i << " ";
            }
        }
    }
}
int main()
{
    int a[] = {7, 5, -4, -3, 2, 4, 1, -2, -1, 0, 6, 3 };

    int n = sizeof(a) / sizeof(a[0]);
    sortUsingHash(a, n);
    return 0;
}

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

Java code to perform Sorting using trivial hash function

import java.util.Arrays;
class HashingSorting
{
    public static void sortUsingHash(int arr[], int n)
    {
        int max = Arrays.stream(arr).max().getAsInt();
        int min = Math.abs(Arrays.stream(arr).min().getAsInt());

        int positiveNum[] = new int[max + 1];
        int negativeNum[] = new int[min + 1];

        for (int i = 0; i < n; i++)
        {
            if (arr[i] >= 0)
                positiveNum[arr[i]] += 1;
            else
                negativeNum[Math.abs(arr[i])] += 1;
        }
        for (int i = min; i > 0; i--)
        {
            if (negativeNum[i] > 0)
            {
                for (int j = 0; j < negativeNum[i]; j++)
                {
                    System.out.print((-1)*i+" ");
                }
            }
        }
        for (int i = 0; i <= max; i++)
        {
            if (positiveNum[i] > 0)
            {
                for (int j = 0; j < positiveNum[i]; j++)
                {
                    System.out.print(i+" ");
                }
            }
        }
    }
    public static void main(String[] args)
    {
        int a[] = { 7, 5, -4, -3, 2, 4, 1, -2, -1, 0, 6, 3 };
        int n = a.length;
        sortUsingHash(a, n);
    }
}

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

Complexity Analysis

Time Complexity

O(max+min), here max is the maximum and minimum element in the input. Thus the time complexity is not dependent on the size of the input but on its elements.

Space Complexity

O(max+min), here max is the maximum and minimum element in the input. The space complexity is also same as that of the time complexity, it is also not dependent on the size of the input. It is dependent on the magnitude of the elements.