#Day12 #100DaysOfCode
sort by distributing elements to within a range.
mostly use for sorting float type number.
scatter-gather approach
time complexity: O(n + k) in best, which is O(n) in average.
there are 4 cases needed to be solved with bucket sort: 
_float type number range .0 to 1.0 (just times the number with 10 and floor it),
_float type number has integer part i.e: 1.5, 2.75 (find max, min, calculate the range by taking the difference divided by the num_bucket, then took each a[i] minus min divided by the range), 
_integer (calculate the divider by taking max divided by num_bucket, ceil it, then took each a[i] divided by divider),
_negative number (distribute the negative to another array, take off the sign, bucketsort it, concatenate back to original)

create the buckets and put the elements from array to buckets take O(n) time. sorting the elements using linear time sorting algo took O(k) time. so, overall  O(n+k)

if used linked list as buckets, O(k) is possible.

time complexity depends on the uniform distribution of inputs and the type of sorting algo used to sort the buckets.