Bucket Sort

Moderate

0/80

Average time to solve is 15m

Contributed by

7 upvotes

Asked in company

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

2 
3
0.22 0.12 0.32
4
0.55 0.23 0.83 0.93

Sample Output 1 :

0.12 0.22 0.32 
0.23 0.55 0.83 0.93

Explanation Of Sample Input 1 :

For the first case:
The array after sorting in non-decreasing order looks like the output.

For the second case:
The array after sorting in non-decreasing order looks like the output.

Sample Input 2 :

Sample Output 2 :

0.50 0.90
0.32

Hint 1

Hint 2

Think of some inbuilt function or something.

Approaches (2)

Approach 1

Approach 2

Inbuild Sort

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.

Time Complexity

O( N * log( N ) ), where ‘N’ is the number of elements in array ‘ARR’.

Default sort() takes O( N * log( N ) ) time.
Hence, the time complexity is O( N * log( N ) ).

Space Complexity

O( 1 ).

We are using no extra space.
Hence, the space complexity is O( 1 ).

(100% EXP penalty)

Bucket Sort

Console