Sorting using Trivial Hash Function

In this tutorial, we will learn about the sorting using the trivial hash function. We have familiar about the various sorting algorithm like heap sort, bubble sort, and merge sort and others. Here we will sort the given array of elements using a Hash array. However, this algorithm is not suitable for the large value of elements (not more than 10^6). This algorithm states that we are given an array of negating and positive number asked to sort the array using Trivial hash function.

Sorting Using hash

Following are the steps to implement the sorting algorithm using the hash.

1. In the first step, we initialize a hash array of size (max_element), we need the maximum.
2. We traverse the array and keep the count of number of occurrence of a particular element.
3. After the second step, we simply iterate from 0 to max_element in the hash array.
4. While iterating in the hash array, if we find the value stored at any hash position is more than 0, which indicated that the element is present at least once in the original list of elements.
5. Hash[i] store the count of the number of times an element is present in the list, so when its>0, we print those number of times elements.

Let's understand the following code.

Example -

Output:

Sorted Arry: [1, 1, 1, 2, 3, 3, 5, 5, 9] 

Explanation -

In this program, we use the trivial hash function to sort the array. We find the maximum value in the array and then create a hash table with a number of buckets equal to max_val + 1. Each element in the array is inserted into the hash table based on its value. Finally, we traverse the hash table and reconstruct the sorted array.

The time complexity of the above code is O(N + K), where N is the number of elements in the input array and K is the range of the values in the array (i.e., the difference between the maximum and minimum values).

Here's a breakdown of the time complexity:

1. Finding the maximum value in the array: O(N)

The process of finding the maximum value in the array requires iterating through all elements once, resulting in a time complexity of O(N).

2. Creating the hash table and inserting elements: O(N)

In the worst case, if all elements in the array have the same value, they will be inserted into the same bucket in the hash table. As a result, the time complexity for creating the hash table and inserting elements is O(N).

3. Traversing the hash table to reconstruct the sorted array: O(N + K)

In the worst case, if all elements in the array are unique, the hash table will have K buckets, each containing one element. Traversing the hash table and reconstructing the sorted array will require visiting all N elements plus the K buckets, resulting in a time complexity of O(N + K).

Since K represents the range of values in the array, it is typically smaller than N in most practical cases. Therefore, the overall time complexity of the algorithm is dominated by the O(N) term, and we can approximate the time complexity as O(N).

How to handle Negative Number

What if we have negative numbers along with the positive number in the array? Using the trivial hash algorithm, we handle negative numbers efficiently.

To sort an array using a hash-based approach, follow these steps:

Step 1: Create two hash arrays, one for positive elements and the other for negative elements.

Step 2: Determine the maximum and minimum values in the array to set the sizes of the positive and negative hash arrays, respectively.

Step 3: Traverse from the minimum value to 0 in the negative hash array and print the elements in the same order as they appear in the array.

Step 4: Traverse from 0 to the maximum value in the positive hash array and print the elements in the same order as they appear in the array.

By using this method, you can efficiently sort the array using the hash-based technique. The positive and negative hash arrays ensure that the elements are sorted correctly, regardless of their original order in the input array.

Let's implement the above steps into code -

Example -

Output:

Original Array: [5, -3, 2, -7, 1, -4, 6, 0, -1, 3]
Sorted Array: -7 -4 -3 -1 0 1 2 3 5 6

Explanation -

Sure! Let's go through the provided code step by step and explain each part:

1. The hash_based_sort() function is defined to implement the hash-based sorting approach.
2. The function takes one argument, arr, which represents the input array that needs to be sorted.
3. In the function, we first find the maximum and minimum values in the input array using the max and min functions, respectively. These values will be used to set the sizes of the positive and negative hash arrays.
4. We created two arrays - `positive_hash` and `negative_hash`. The `positive_hash` array is initialized with zeros and has a size of `(max_val + 1)`, where `max_val` is the maximum value in the input array. Similarly, the `negative_hash` array is initialized with zeros and has a size of `(abs(min_val) + 1)`, where `min_val` is the minimum value in the input array. Note that we use `abs(min_val)` to ensure a non-negative size for the `negative_hash` array.
5. Next, we traverse the input array `arr` and populate the `positive_hash` and `negative_hash` arrays based on the values of the elements in the input array. For each positive element in `arr`, we increment the corresponding position in `positive_hash` by 1, and for each negative element, we increment the corresponding position in `negative_hash` by 1.
6. After populating the hash arrays, we proceed to print the sorted array. We first print the negative elements in ascending order by traversing the `negative_hash` array in reverse order (from the highest negative value to 1). For each non-zero count in the `negative_hash` array, we print the corresponding negative value and decrease the count by 1.
7. Next, we print the non-negative elements in ascending order by traversing the `positive_hash` array from 0 to `max_val`. For each non-zero count in the `positive_hash` array, we print the corresponding non-negative value and decrease the count by 1.
8. The program completes, and the sorted array is printed in ascending order, where negative elements appear first, followed by non-negative elements.

Time Complexity

The time complexity of the above code is O (N + K), where N is the number of elements in the input array and K is the range of the values in the array (i.e., the difference between the maximum and minimum values).

Space Complexity

The space complexity of the above code is O (N + K), where N is the number of elements in the input array and K is the range of the values in the array (i.e., the difference between the maximum and minimum values).