CODEWITHSUNDEEP
algorithmsorting
Cauthon
Cauthon

Reputation: 520

Bucket Sort with k unique elements

Using Bucket Sort, sort n elements among which k elements are unique. Runtime should be O(kn). k is based on the input and isn't known in advance. You cannot assume the elements are in a specific range, and the runtime cannot be based on the maximum element (it can be larger than k).

There are more efficient algorithms, but a O(kn) one is requested.

I think only very basic data structures are should be used (i.e. not hash maps etc.).

I'm not sure how to use the uniqueness in relation to buckets...

Upvotes: 0

Views: 216

Answers (1)

MBo
MBo

Reputation: 80232

Runtime O(kn) assumes that time for appropriate bucket searching is O(k).

Such time together with O(1) per inserting of new bucket is provided with linked list.

how to use the uniqueness in relation to buckets

k unique elements form k buckets (with single value per bucket)

Upvotes: 2

Related Questions