Bucket Sort distributes the elements into a number of buckets,
then sorts the buckets individually. Here it is used insertion sort algorithm
to sort the buckets.
The time complexity of the Bucket Sort algorithm depends on various factors,
including the distribution of the input data, the number of buckets,
and the sorting algorithm used to sort individual buckets.
Time Complexity
Best Case: O(n+k) - If the input is uniformly distributed such that each
bucket contains approximately the same number of keys,
and if the keys are distributed uniformly in the buckets, the algorithm runs
linearly, where n is the number of elements and k is the number of buckets.
Average Case: O(n) - In most real-world scenarios, when the elements are
distributed fairly uniformly and when the number of buckets k is O(n),
the time complexity is approximately linear:O(n+n^2/k+k). If k = O(n), this
becomes O(n).
Worst Case: O(n^2) - If all the input elements are placed in a single bucket,
and if we use a comparison sort (like insertion sort) for
the individual buckets, the time complexity will be O(n^2). This is because
all the elements are in one bucket, and we have to sort n elements using
O(n^2) sorting algorithm. This worst case occurs when the elements are
not uniformly distributed.
Space Complexity: O(n+k), where n is the number of elements in input array
and k is the number of buckets. This is because we need space for the original
array and additional space for the k buckets.
It's essential to note that the efficiency of Bucket Sort depends
significantly on the distribution of the input data. It works best when the
data are uniformly distributed over a range, allowing the data to be
distributed evenly among the buckets.
Parameters
arr: number[]
unsorted array of numbers
bucketSize: number = 5
number, set how many elements should bucket contain
Bucket Sort distributes the elements into a number of buckets, then sorts the buckets individually. Here it is used insertion sort algorithm to sort the buckets.
The time complexity of the Bucket Sort algorithm depends on various factors, including the distribution of the input data, the number of buckets, and the sorting algorithm used to sort individual buckets.
Time Complexity
Best Case: O(n+k) - If the input is uniformly distributed such that each bucket contains approximately the same number of keys, and if the keys are distributed uniformly in the buckets, the algorithm runs linearly, where n is the number of elements and k is the number of buckets.
Average Case: O(n) - In most real-world scenarios, when the elements are distributed fairly uniformly and when the number of buckets k is O(n), the time complexity is approximately linear:O(n+n^2/k+k). If k = O(n), this becomes O(n).
Worst Case: O(n^2) - If all the input elements are placed in a single bucket, and if we use a comparison sort (like insertion sort) for the individual buckets, the time complexity will be O(n^2). This is because all the elements are in one bucket, and we have to sort n elements using O(n^2) sorting algorithm. This worst case occurs when the elements are not uniformly distributed.
Space Complexity: O(n+k), where n is the number of elements in input array and k is the number of buckets. This is because we need space for the original array and additional space for the k buckets.
It's essential to note that the efficiency of Bucket Sort depends significantly on the distribution of the input data. It works best when the data are uniformly distributed over a range, allowing the data to be distributed evenly among the buckets.