Last Updated: 15 Apr, 2022

Bucket Sort

Moderate

Asked in company

Solve now

Problem statement

Ninja recently came to know about sorting and searching in an array and he wants to learn the trick to sorting an array.

So he has been provided with an array ‘ARR’ of size ‘N’ with values that are uniformly distributed across the range [0, 1] and you have to sort them in an optimal manner. Please set the precision to 2 decimal digits.

Example:

Input: 'N' = 4, 'ARR' = [0.79, 0.66, 0.65, 0.12]

Output: [0.12, 0.65, 0.66, 0.79]

The given array, after sorting in a non-decreasing manner looks like the output given.

Input Format :

The first line will contain the integer 'T', denoting the number of test cases.

The first line for each test case contains a single integer 'N', the size of the array ‘ARR’.
The second line will contain ‘N’ integers representing the array elements.

Output format :

For each test case, print the minimum sum of elements.

Note :

You don't need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= 'T' <= 10
1 <= 'N' <= 10^5
0 <= ‘ARR[i]’ <= 1, ARR[i] is of exactly 2 decimal places.

Time Limit: 1 sec

Solve now

Approaches

01 Approach

In most languages, we have an inbuilt sort function that we can use to sort our array ‘ARR’.

The steps are as followed :

Let ‘ARR’ be our array of size ‘N’.
For using the inbuilt sort function in python we can use something like this:-
- ARR.sort();
Return ARR.

Solve now

02 Approach

We know that counting sort takes O( N ) time to sort an array whose elements are less than <10^6 if we talk about c++, We can not make an array greater than that, also we use array elements as indices there, but here numbers are floating-point so we can not use an array here now what if we take the map for storing the number than we know a general map uses a hash table( not talking about map in c++ STL ) and if two keys have the same hash function we can do a linear search from there to an empty space in the hash table and in the worst case this searching can take O(N) time and total time complexity can go up to O(N^2) in the worst case just for storing so we can not use the map as well. We are trying to solve it in linear time for that we can use bucket sort where we make a few buckets and insert the numbers in those buckets and then we sort those buckets using insertion sort.

The Steps are as follows:

InsertionSort( ARR)

‘ARR’ is our bucket array.
for ‘i’ in the range [1,’N’-1], where ‘N’ is the size of ‘ARR’:
- Declare variable ‘up’ = ‘ARR[i]’, we have to move the current element to its correct position.
- Declare ‘j’ = ‘i’-1.
- while j >= 0 and arr[j] > up, we are going to put up at its correct position in sorted array.
  - Put arr[j + 1] = arr[j].
  - j -= 1.
- Now replace arr[j+1] = up.
Now Return ‘ARR’.

sortArray( ARR )

‘ARR’ is our array of size ‘N’.
Let's create another 2D array named ‘BUCKET’ of size 10 as numbers are uniformly distributed between 0 to 1, so all the numbers in the range 0 to 0.99 go in the bucket 0 and 0.10 to 0.19 goes to bucket 1 and so on and, we can uniformly insert them in 10 buckets.
For each element of ‘ARR[i]’ we do the following:-
- Insert the number ‘ARR[i]’ into the bucket (n*ARR[i]) where n is the number of buckets.
Now sort individual buckets using Insertion sort.
Now merge all the buckets to the array ‘ARR’.
Return ‘ARR’

Solve now