I am learning about bucket sort and it seems a lot of the material insist that it is efficient when the key values are "uniformly distributed and when used to sort integers from a known range". I understand the uniformly distributed part, but do you have to know the range too? If the range is not provided, when creating the auxiliary array during bucket sort, could you instead simply create a dynamic array (ArrayList) which can expand by itself?
Does Bucket Sort require you to know the range of the values beforehand?
157 views Asked by diagoot At
2
There are 2 answers
Related Questions in ALGORITHM
- MCNP 6 - Doubts about cells
- Given partially sorted array of type x<y => first apperance of x comes before first of y, sort in average O(n)
- What is the algorithm behind math.gcd and why it is faster Euclidean algorithm?
- Purpose of last 2 while loops in the merge algorithm of merge sort sorting technique
- Dots and Boxes with apha-beta pruning
- What is the average and worst-case time complexity of my string searching algorithm?
- Building a School Schedule Generator
- TC problem 5-2:how to calculate the probability of the indicator random variable?
- LCA of a binary tree implemented in Python
- Identify the checksum algorithm
- Algorithm for finding a subset of nodes in a weighted connected graph such that the distance between any pair nodes are under a postive number?
- Creating an efficent and time-saving algorithm to find difference between greater than and lesser than combination
- Algorithm to find neighbours of point by distance with no repeats
- Asking code suggestions about data structure and algorithm
- Heap sort with multithreading
Related Questions in SORTING
- Sorting a List by its property renames all the objects in the List
- Does Sort() method in C# use recursion?
- ARM Assembly code is not executing in Vitis IDE
- Creating an efficent and time-saving algorithm to find difference between greater than and lesser than combination
- Heap sort with multithreading
- Laravel Livewire data table sorting livewire update payload
- basic MergeSort exercise
- How to import a range into a variant array in Excel VBA and sort using the sort method?
- Looker Studio | pivot chart - sorting by metric and last month
- how to create an array of multiples of 5 and display it in reverse
- matplotlib sort barh by values
- Custom Sorting Javascript with A-Z set
- Mainframe Programming Sorting, OUTFIL REMOVECC,NODETAIL
- Soft list based on another list
- SQL query : creating table with distinct values on selected columns
Related Questions in BUCKET-SORT
- elasticsearch - get top n records group by sort by value
- Iteration failure in radixsort aka bucket sort algorithm,Radix sort inefficient because it assigns wrong size for bucket 0 according to the unit test
- Bucket Sort for normal distribution
- Bucket Sort Better Bucket Range
- How to pass arguments in pthread_create() in c
- How can I make this version of Bucket Sort using recursion?
- How can I evenly divide records into N groups based on the values?
- Bucket sort: Why all values end up in the first bucket?
- Bucket sort or merge sort?
- I can't seem to to find the time complexity of Histogram sort anywhere? I am aware it is type of bucket sort but what is the exact time complexity?
- Merging 1000s of files into one sorted file with memory constraints - heap vs bucket sort
- How to use bucket sort with strings in Python?
- Sorting an array using Bucket Sort
- Why is Time Complexity of Bucket Sort is O(n^2) and not O(log(n) * n^2)?
- Top K Frequent Elements - time complexity: Bucket Sort vs Heap
Popular Questions
- How do I undo the most recent local commits in Git?
- How can I remove a specific item from an array in JavaScript?
- How do I delete a Git branch locally and remotely?
- Find all files containing a specific text (string) on Linux?
- How do I revert a Git repository to a previous commit?
- How do I create an HTML button that acts like a link?
- How do I check out a remote Git branch?
- How do I force "git pull" to overwrite local files?
- How do I list all files of a directory?
- How to check whether a string contains a substring in JavaScript?
- How do I redirect to another webpage?
- How can I iterate over rows in a Pandas DataFrame?
- How do I convert a String to an int in Java?
- Does Python have a string 'contains' substring method?
- How do I check if a string contains a specific word?
Popular Tags
Trending Questions
- UIImageView Frame Doesn't Reflect Constraints
- Is it possible to use adb commands to click on a view by finding its ID?
- How to create a new web character symbol recognizable by html/javascript?
- Why isn't my CSS3 animation smooth in Google Chrome (but very smooth on other browsers)?
- Heap Gives Page Fault
- Connect ffmpeg to Visual Studio 2008
- Both Object- and ValueAnimator jumps when Duration is set above API LvL 24
- How to avoid default initialization of objects in std::vector?
- second argument of the command line arguments in a format other than char** argv or char* argv[]
- How to improve efficiency of algorithm which generates next lexicographic permutation?
- Navigating to the another actvity app getting crash in android
- How to read the particular message format in android and store in sqlite database?
- Resetting inventory status after order is cancelled
- Efficiently compute powers of X in SSE/AVX
- Insert into an external database using ajax and php : POST 500 (Internal Server Error)
If you don't know range and meet value 1000000 - does it belong to the first bucket? to the 10-th bucket? to the 1000th bucket?
Say you believe it belongs to the 10-th bucket (every bucket refers to 100000 values). But next value is 10 000 000 and you need to make 100 buckets. Next one is 1 000 000 000 and now you need 10000 buckets (most of them are empty!)...
Knowing value range and distribution helps to organize right bucket structure to provide the best sorting time.