850 views

2 Answers

0 votes
0 votes
a)I think its always stable because stable means maintaing the same order as the input

two vales that are similar arive in input

then first which arrived remains frirst and the next arrived will be next in order

In bucket sort a linked list is maintained and it maintains the same order as input

So i tink its always stable am not sure

b)Its not inplace because we create a separate array to link the lements in order
0 votes
0 votes

it is stable sort. stability of bucket sort not dependent on what we are using to sort bucket. but time complexity dependent

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(nlog(n) comparison sorting like quick sort.

it is not inplace sorting.

source

https://en.wikipedia.org/wiki/Bucket_sort

Related questions

1 votes
1 votes
1 answer
1
Sanjay Sharma asked May 7, 2016
982 views
Assuming there are n keys andeach key is in the range [0, m – 1].The run time of bucket sort is(A) O(n) (B) O(n lgn)(C) O(n lgm) (D) O(n + m)
1 votes
1 votes
0 answers
2
rahul sharma 5 asked Dec 11, 2016
1,098 views
Does Bucket sort input is always between 0 and 1?Or the input has to be distributed between [0,1) interval uniformly before applying bucket sort?
1 votes
1 votes
0 answers
3
vaishali jhalani asked Nov 7, 2016
333 views
What simple change to the bucket sort preserves its linear average-case running time and makes its worst-case running time O(nlgn)?
1 votes
1 votes
1 answer
4
iarnav asked May 4, 2019
834 views
I’ve seen this wikipedia article – https://en.wikipedia.org/wiki/Comparison_sortAlso see this link – https://gateoverflow.in/32948/minimum-number-of-comparisonshttp...