Sorting using trivial hash function
Last Updated :
19 Apr, 2023
We have read about various sorting algorithms such as heap sort, bubble sort, merge sort and others.
Here we will see how can we sort N elements using a hash array. But this algorithm has a limitation. We can sort only those N elements, where the value of elements is not large (typically not above 10^6).
Examples:
Input : 9 4 3 5 8
Output : 3 4 5 8 9
Explanation of sorting using hash:
- Step 1: Create a hash array of size(max_element), since that is the maximum we will need
- Step 2: Traverse through all the elements and keep a count of number of occurrence of a particular element.
- Step 3: After keeping a count of occurrence of all elements in the hash table, simply iterate from 0 to max_element in the hash array
- Step 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.
- Step 5: Hash[i] has the count of the number of times an element is present in the list, so when its >0, we print those number of times the element.
- If you want to store the elements, use another array to store them in a sorted way.
- If we want to sort it in descending order, we simply traverse from max to 0 and repeat the same procedure.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
void sortUsingHash(int a[], int n)
{
int max = *std::max_element(a, a + n);
int hash[max + 1] = { 0 };
for (int i = 0; i < n; i++)
hash[a[i]] += 1;
for (int i = 0; i <= max; i++) {
if (hash[i]) {
for (int j = 0; j < hash[i]; j++) {
cout << i << " ";
}
}
}
}
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
import java.util.*;
class GFG {
static void sortUsingHash(int a[], int n)
{
int max = Arrays.stream(a).max().getAsInt();
int hash[] = new int[max + 1];
for (int i = 0; i < n; i++)
hash[a[i]] += 1;
for (int i = 0; i <= max; i++) {
if (hash[i] != 0) {
for (int j = 0; j < hash[i]; j++) {
System.out.print(i + " ");
}
}
}
}
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);
}
}
|
Python3
def sortUsingHash(a, n):
Max = max(a)
Hash = [0] * (Max + 1)
for i in range(0, n):
Hash[a[i]] += 1
for i in range(0, Max + 1):
if Hash[i] != 0:
for j in range(0, Hash[i]):
print(i, end=" ")
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)
|
C#
using System;
using System.Linq;
class GFG {
static void sortUsingHash(int[] a, int n)
{
int max = a.Max();
int[] hash = new int[max + 1];
for (int i = 0; i < n; i++)
hash[a[i]] += 1;
for (int i = 0; i <= max; i++) {
if (hash[i] != 0) {
for (int j = 0; j < hash[i]; j++) {
Console.Write(i + " ");
}
}
}
}
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);
}
}
|
Javascript
<script>
function sortUsingHash(a, n) {
var max = Math.max.apply(Math, a);
var hash = Array(max + 1).fill(0);
for (i = 0; i < n; i++)
hash[a[i]] += 1;
for (i = 0; i <= max; i++) {
if (hash[i] != 0) {
for (j = 0; j < hash[i]; j++) {
document.write(i + " ");
}
}
}
}
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);
</script>
|
Output
0 1 2 2 3 3 4 4 5 5 9 10 12 15 18 19 20
Time Complexity: O(max*n), where max is maximum element and n is the length of given array
Auxiliary Space: O(max)
How to handle negative numbers?
In case the array has negative numbers and positive numbers, we keep two hash arrays to keep a track of positive and negative elements.
Explanation of sorting using hashing if the array has negative and positive numbers:
- Step 1: Create two hash arrays, one for positive and the other for negative
- Step 2: the positive hash array will have a size of max and the negative array will have a size of min
- Step 3: traverse from min to 0 in the negative hash array, and print the elements in the same way we did for positives.
- Step 4: Traverse from 0 to max for positive elements and print them in the same manner as explained above.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
void sortUsingHash(int a[], int n)
{
int max = *std::max_element(a, a + n);
int min = abs(*std::min_element(a, a + n));
int hashpos[max + 1] = { 0 };
int hashneg[min + 1] = { 0 };
for (int i = 0; i < n; i++) {
if (a[i] >= 0)
hashpos[a[i]] += 1;
else
hashneg[abs(a[i])] += 1;
}
for (int i = min; i > 0; i--) {
if (hashneg[i]) {
for (int j = 0; j < hashneg[i]; j++) {
cout << (-1) * i << " ";
}
}
}
for (int i = 0; i <= max; i++) {
if (hashpos[i]) {
for (int j = 0; j < hashpos[i]; j++) {
cout << i << " ";
}
}
}
}
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
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)
{
int max = Arrays.stream(a).max().getAsInt();
int min
= absolute(Arrays.stream(a).min().getAsInt());
int hashpos[] = new int[max + 1];
int hashneg[] = new int[min + 1];
for (int i = 0; i < n; i++) {
if (a[i] >= 0)
hashpos[a[i]] += 1;
else
hashneg[absolute(a[i])] += 1;
}
for (int i = min; i > 0; i--) {
if (hashneg[i] > 0) {
for (int j = 0; j < hashneg[i]; j++) {
System.out.print((-1) * i + " ");
}
}
}
for (int i = 0; i <= max; i++) {
if (hashpos[i] > 0) {
for (int j = 0; j < hashpos[i]; j++) {
System.out.print(i + " ");
}
}
}
}
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);
}
}
|
Python3
def sortUsingHash(a, n):
Max = max(a)
Min = abs(min(a))
hashpos = [0] * (Max + 1)
hashneg = [0] * (Min + 1)
for i in range(0, n):
if a[i] >= 0:
hashpos[a[i]] += 1
else:
hashneg[abs(a[i])] += 1
for i in range(Min, 0, -1):
if hashneg[i] != 0:
for j in range(0, hashneg[i]):
print((-1) * i, end=" ")
for i in range(0, Max + 1):
if hashpos[i] != 0:
for j in range(0, hashpos[i]):
print(i, end=" ")
if __name__ == "__main__":
a = [-1, -2, -3, -4, -5, -6,
8, 7, 5, 4, 3, 2, 1, 0]
n = len(a)
sortUsingHash(a, n)
|
C#
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)
{
int max = a.Max();
int min = absolute(a.Min());
int[] hashpos = new int[max + 1];
int[] hashneg = new int[min + 1];
for (int i = 0; i < n; i++) {
if (a[i] >= 0)
hashpos[a[i]] += 1;
else
hashneg[absolute(a[i])] += 1;
}
for (int i = min; i > 0; i--) {
if (hashneg[i] > 0) {
for (int j = 0; j < hashneg[i]; j++) {
Console.Write((-1) * i + " ");
}
}
}
for (int i = 0; i <= max; i++) {
if (hashpos[i] > 0) {
for (int j = 0; j < hashpos[i]; j++) {
Console.Write(i + " ");
}
}
}
}
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);
}
}
|
Javascript
<script>
function absolute(int x){
if(x<0) return (-1*x);
return x;
}
function sortUsingHash(a, n) {
var max = Math.max.apply(Math, a);
var min = absolute(Math.min.apply(Math, a));
var hashpos = Array(max).fill(0);
var hashneg = Array(min + 1).fill(0);
for (i = 0; i < n; i++) {
if (a[i] >= 0)
hashpos[a[i]] += 1;
else
hashneg[absolute(a[i])] += 1;
}
for (i = min; i > 0; i--) {
if (hashneg[i] > 0) {
for (j = 0; j < hashneg[i]; j++) {
document.write((-1) * i + " ");
}
}
}
for (i = 0; i <= max; i++) {
if (hashpos[i] > 0) {
for (j = 0; j < hashpos[i]; j++) {
document.write(i + " ");
}
}
}
}
var a = [ -1, -2, -3, -4, -5, -6, 8, 7, 5, 4, 3, 2, 1, 0 ];
var n = a.length;
sortUsingHash(a, n);
</script>
|
Output
-6 -5 -4 -3 -2 -1 0 1 2 3 4 5 7 8
Complexity:
Time complexity- The time complexity of this program is O(n + max), where n is the size of the input array and max is the maximum element in the array. This is because the program first finds the maximum element in the array using std::max_element, which takes O(n) time. It then creates two hash arrays of size max+1 and min+1, where min is the absolute value of the minimum element in the array. This takes O(max+min) time, but since min is always less than or equal to max, we can simplify this to O(max). The program then traverses through the input array once to fill in the hash arrays, which takes O(n) time. Finally, the program traverses through the two hash arrays, printing out the elements in sorted order. This takes O(max) time, since max is the size of the hash arrays. Therefore, the total time complexity of the program is O(n + max).
Space complexity –The space complexity of this program is O(max), since the program creates two hash arrays of size max+1 and min+1, where min is the absolute value of the minimum element in the array. However, since min is always less than or equal to max, we can simplify this to O(max). Therefore, the space complexity of the program is O(max).
Limitations:
- Can only sort array elements of limited range (typically from -10^6 to +10^6)
- Auxiliary space in worst cases is O(max_element) + O(min_element)
Please Login to comment...