Posted: September 9th, 2022

Comparison Between The Bucket and Radix Sorting Algorithms

Comparison Between The Bucket and Radix Sorting Algorithms

The Bucket and Radix Sorting Algorithms
Sorting algorithms have extensively been applied in databases that constantly need to sort countless items. The algorithm will sort a particular array or list of elements as per a comparison operator on the elements. Over time, numerous algorithms would be devised with different projects encompassing the use of a particular sorting algorithm that has been deemed feasible for the project in terms of the time use, use of memory and simplicity of usage. Two of these algorithms are the radix and bucket sorting algorithms. These two algorithms are considered non-comparison sorting algorithms which encompass the data elements being placed in a specific order without performing any comparison.
In the article ‘Novel Hash-Based Radix Sorting Algorithm’, Mandal & Verma (2019) asserted that sorting has remained a quintessential challenge in computer science. There has been a need for further research that could optimize the runtime efficiency for the sorting algorithms. Counting sort and radix sort have demonstrated better performance in regards to their time efficiency. However, the arrays used in counting sort have not lent themselves properly to sorting objects. Conversely, even when the radix sort can sort objects in linear time, it still needs the use of an auxiliary array. Thus, this research focussed on the Radix sort algorithm because even though it can sort objects in linear time with the corresponding array index requiring a hash for the object, the Radix sort still needs an auxiliary array. Thus, this research proposed replacing this auxiliary array with a hash table to avoid the calculations for the array and be better suited in handling objects. Similar to the array-based Radix sort, the hash-bashed approach still maintains the linearity hence the sorting becomes more efficient. The researchers noted that in this novel sorting algorithm, with the number of elements increasing, the runtime progresses linearly and also as the number of digits increases, the sorting runtime will lengthen linearly. Therefore, the hash-based radix sort was deemed feasible uin overcoming the numerous issues affiliated with the present algorithms sorting algorithms.
In the article, An Innovative Bucket Sorting Algorithm Based on Probability Distribution, Zhao & Min (2009) noted that the bucket sorting algorithm distributes a group of records with similar keys into the right “bucket”. Then, another sorting algorithm is applied to the records contained in the different buckets. Thus, with bucket sorting, the records’ partitioning into m buckets is less time consuming with only a few records being contained in every bucket so that “cleanup sorting ” algorithm is applicable fast. However, while the bucket sorting has the potential of asymptotically saving time compared to the Ω (nlogn) algorithms, there is a need to have a strategy that will allow uniform distribution of all the records into buckets. The study proposed a new method of constructing a hash function as per the data distribution, for the uniform distribution of n records into n buckets relying on the key of each record. This ensures the sorting time for the proposed bucket sorting algorithm to reach under any circumstance. This innovative bucket sorting algorithm that was based on the probability distribution was referred to as PBSORT. A performance analysis of this algorithm demonstrated that it was efficient in sorting the large data sets. The efficiency was evident when the proportion of its running time to n was almost constant, while the running time for the QUICKSORT algorithm increased rapidly with nonlinearity with the increase of data n. Additionally, the QUICKSORT algorithm needed the records to be moved in array a[n] which required a lot of memory space during sorting. Conversely, with PBSORT, the records remained unmoved showing its advantage hence sorting large amounts of data.
Comparison of the Article’s Perspectives
Comparison of Assumptions
Considering the assumptions taken up in the Mandal & Verma (2019)’s study, their research took up the assumption that objects will be sorted starting from the least significant digit followed by the next least significant digit and the process continues. Nevertheless, with the Hash Sort algorithm then the objects get to be stored in a hash instead of an array as in the normal Radix sort. Also, with the object being sorted by one of its parameters, the number of indices in the hash will only need a match of the radi with the specified parameter. The four parameters used for this approach included the “Arr[]” representing the sequence to be sorted, the “size” specifying the length of Arr[], “dim” specifying the number of digits in every number, and “Radix” that specified the radix of the numbers to be sorted. The outer loop simply traverses vuia every digit moving from the least to the most significant digits. The hash is created in which the values were temporarily stored. Since the hash sort will not run the counting sorting the inner loops similarly to how the radix sort does, there will be no need for arithmetic being used in the auxiliary array. The proper management of pointers will lead to the efficient sorting of objects in linear time.
Zhao & Min (2009) took up the assumption that if there is a particular distribution for the keys of n records in a particular interval then the probability density function could be used in uniformly distributing n records into n buckets. To prove the assumption, the study considered the density function for probability distribution within a closed interval [c,d] is . Using special cutting points c1,,,cn-1, interval [c,d] could be divided into n subintervals in such a manner that the area of the curvilinear trapezoid formed under in any of the n subintervals is equal. Evidently, the curvilinear trapezoid are for every interval could be expressed as .. Since the n small areas obtained after dividing the interval [c,d] are equivalent, the probability of every subinterval is also equal. Letting a subinterval to correspond to a bucket, then the probability for any record in the array a[n] being inserted to every bucket is equal such that the n records can be uniformly distributed to n buckets. Considering that c1,,,,cn-1, may not be equidistant to the interval [c,d], it may be challenging to locate them. Rather, the subinterval could be located directly where the record is distributed, which is the bucket number; this bucket number was established by the proportion of two integral areas. For instance, the number for the bucket having a record a[i] has been denoted as s(a[i].key), then the bucket
number could be calculated be the formula, where the int[] denotes illustrating the integral part. Additionally, since the relation held almost everywhere, then the relationship was derived. Undoubtedly, from the which was a[i].key < a[j].key. This relationship evidently denoted that for a smaller key, the respective bucket number would also be smaller.

Comparison of Approaches
In assessing the effectiveness of these approaches, Manda & Vera (2019) provided key details of how the hash-based radix algorithm would be implemented. The algorithm was tested in a Virtual Machine that uses the VMWare Workstation. The machine’s specifics were 8GB RAM, 4 cores from an Intel6700K and would be connected by the 7200RPM hard drive that is connected to the USB Host. The machine ran Linux Mint 18.1 with the Mate GUI since it was less graphically intensive. Hash sort was then written and compiled using the C++. For carrying out the experiment, the algorithm had two main parameters with an impact on its runtime, specifically the number of elements and the number of digits in each number. Testing how the number of elements affected the runtime, random sets of five-digit numbers were generated. Then, the Hash sort was run on every set for five times each and the results would be outlined.
On the other hand, Zhao & Min (2009) compared the effectiveness of the probability based bucket sort algorithm with another algorithm to establish the differences. The comparison of algorithms in regards to their performance was supported by Kwiatkowski (20001) who noted that the efficiency and speedup results calculated by using the parallel comparison method are higher than those obtained by the classical method. For the parallel performance analysis of the two algorithms, the initial step constituted one loop whereby the sorting time was proportional to the data n. Hence the time taken is O(n). The second and third steps also involved one loop thus the sorting time remained O(n). The fourth step was the comparison done by inserting keys in the corresponding bucket arrays. Since the keys have been distributed uniformly in the buckets, on average, the probability for a bucket conflict surpassing 0.5n was less than 0.5. This means that there will be no greater than 50% of all buckets with no records. For the comparisons done, it was evident that the total time needed for the probability based bucket sort algorithm was O(n)+O(n)+O(3n)+O(n)=O(n).
Comparison of Results
One similarity that was evident between these two studies was that both the radix and bucket sorting algorithms are not as effective on their own. Rather, their implementation needs to incorporate a particular strategy that is able to improve their efficiency. The results were depicted in various tables hence which was a feasible approach of ensuring that the better efficiency is captured.
In the study by Manda & Vera (2019) focussed on the Radix sort, it was evident that a radix sort that uses a hash instead of the typical auxiliary array, this algorithm would be in a better position of handling objects and dynamic structures compared to the array. The harsh sort scaled linearly as the number of elements and digits changes to make the O(w*n) where w denoted the number of digits and n represented the number of elements. Also, the study found that if returning the array was not needed, one could return the final hash rather than a sorted array in the final step of the hash sort considering that the hash has an O(1) search time. The effectiveness of this algorithm was based on the better performance exuded by the Radix sort when it is hash based compared to the use of the auxiliary array.
Conversely, Zhao & Min (2009) study’s results which were explained through the different tables demonstrated that the PBSORT algorithm was the best for handling large data sets, the initial table was a comparison of the running times for PBSORT and QUICKSORT it was evident that the running time for PBSORT remained almost at a constant while the running times for QUICKSORT increased rapidly with the increase in the datasets’ sizes. Similar outcomes were evident when the comparison considered the time in seconds. The two algorithms were very similar when the data sets were small. However, an increase in the size of the data set showed that PBSORT proposed in the study increased linearly while QUICKSORT increases nonlinearly and very fast.
The two studies conclusively showed that the efficiency fo these two algorithms was improved by applying better strategies during implementation. This discussion noted that the performance of the two sorting algorithm bucket and radix sort depended on how each is able to improve its runtime efficiency.
Individual Contributions
These two sorting algorithms could be analyzed hypothetically with the use of diverse use cases characterized by three different data sizes, extending three requests of greatness. The principal information was the uniform appropriation of arbitrary numbers. The second information was sorted, which tried how well the calculations perform with completely sorted data arrangements. The third information had 95% of numbers sorted, which tried for almost sorted data exhibits. It was evident that RADIX sort used the slightest huge digit variant and the numbering sort. Time utilization and memory use were experimentally measured. The sorting took up to a hundred seconds with the biggest info. It was evident that the bucket sort was quicker in all cases. The execution of the RADIX sort was moderate when the scope of the numbers was somewhat vast. RADIX sort was brisk for the unsorted inputs and sorted inputs. RADIX sort’s memory use was marginally superior to the bucket sort when sorting a little number of whole numbers. The bucket sort used a lot of memory when sorting numbers with a vast reach.

References
Kwiatkowski, J. (2001, September). Evaluation of parallel programs by measurement of its granularity. In International Conference on Parallel Processing and Applied Mathematics (pp. 145-153). Springer, Berlin, Heidelberg.
Mandal, P. K., & Verma, A. (2019, October). Novel Hash-Based Radix Sorting Algorithm. In 2019 IEEE 10th Annual Ubiquitous Computing, Electronics & Mobile Communication Conference (UEMCON) (pp. 0149-0153). IEEE.
Zhao, Z., & Min, C. (2009, March). An Innovative Bucket Sorting Algorithm Based on Probability Distribution. In 2009 WRI World Congress on Computer Science and Information Engineering (Vol. 7, pp. 846-850). IEEE.

Order | Check Discount

Tags: Comparison Between The Bucket and Radix Sorting Algorithms