Subarray problem

help
22

Maybe you didn’t notice the range n?
and the time complexity of the bucket sorting algorithm I learned is O (max-min+n). Maybe you don’t call it that way?

23

Isn’t range the size of array given to us?

24

The difference between the maximum and minimum values of the numbers in this array is O (n) level.

25

I saw this on hackerearth, it says O(n) time to sort using the bucket sort, but on other websites, worst case is O(n^2).

26

I really can’t understand what the worst case is because I said that the time complexity of bucket sorting depends on the range of numbers. Is there any mistake in my statement?

27

<copy - paste>

Worst-case analysis[edit]

Bucket sort is mainly useful when input is uniformly distributed over a range. When the input contains several keys that are close to each other (clustering), those elements are likely to be placed in the same bucket, which results in some buckets containing more elements than average. The worst-case scenario occurs when all the elements are placed in a single bucket. The overall performance would then be dominated by the algorithm used to sort each bucket, which is typically O(n^{2}) insertion sort, making bucket sort less optimal than O(nog (n)) comparison sort algorithms like Quicksort.

28

Maybe my algorithm is different from what you think. This is my code：

# include <bits/stdc++.h>
using namespace std;

const int N = whatever + 1;
int a[N], vis[N];

int main ()
{
    int n = whatever;
    for (int i = 1; i <= n; ++i) a[i] = rand() % n + 1; // Initialization
    for (int i = 1; i <= n; ++i) ++vis[a[i]];
    for (int i = 1; i <= n; ++i) while (vis[i]) cout << i << " ", --vis[i];
    return 0;
}

Now do you understand what I mean?

29

This is called counting sort imo.
And it is O(n+r) where n is number of elements and r= b-a+1 where a<=arr[i]<=b .

30

Well, now I understand why these guys don’t understand what I’m talking about. In China we call it bucket sorting.

31

I mentioned this in my reply above.

1 Like
32

@l_returns to the rescue :grinning:
Honestly saying I have never used bucket sort before but had a good debate

1 Like
33

Yup we can call it as a bucket sort as well maybe but this seems to be a special case and we call it counting sort.

34

This is a useful sorting method for some very disgusting problems.

35

Seems like there is one when range of numbers is small :smiley:

1 Like
36

Ikr. \hspace{0mm} \hspace{0mm}

37

I believe you know, after all, you are a five-star player. :smiling_imp:

38

:joy::+1: \hspace{0mm} \hspace{0mm}

1 Like