Algorithms Summary Points – Part 6: Decision Tree, Bucket Sort, Radix Sort

This note has some summary points from my study of algorithms and algorithmic analysis. If you have little or no idea of the concepts I will talk about, this note may not be so helpful to you. I only post these here to serve as a quick note or as a refresher about these concepts should the need arise. In that case, I suggest you take an advanced course on algorithms and data structures first.  Nevertheless, if you are interested in discussing any of the concepts here I will be glad to be of help.

Decision Tree, Bucket Sort, Radix Sort

The number of comparisons performed in order to arrive at an arrangement found in a leaf node equals the depth of that leaf node in the decision tree. 

Number of comparisons performed in the worst case = the depth of the deepest node = height of the decision tree 

For input size n, leaves L, height h, number of comparisons c, 

  • C = h (in the worst case) – this is for the longest path in the tree 
  • L = n! 
  • L ≤ 2h 
  • So, h >= ceil (log L) 
  • Which also means C >= ceil (log L) 
  • So, >= ceil (log n!)   
  • Which means C = Ω (log n!) 
  • And we know that log n! is in Ω (n log n) 
  • So, C = Ω (n log n) 

Bucket Sort 

  • Works using 1 bucket. The bucket is an array whose length m is the upper bound of the range of elements in the original array.  
  • Then it traverses the original array and increment the value in the bucket at the index equal to the value of the current element – Just like counting. 
  • When done, we traverse through the bucket and if the current element is >0, we insert into our output array, the index of the current element, the number of times it occurs. 
  • Running time: O(m + n). Where m is the size of the bucket and n is the size of the input 

Radix Sort 

  • Uses buckets just like bucket sort. 
  • However, we have a remainder bucket and quotient bucket both of which have the length of the radix. 
  • It gets a radix which is the nearest integer to the square root of the perfect square nearest to the highest number in the sequence. 
  • Then it traverses through the main array, if the remainder when the current element is divided by the radix is I, it inserts the current element into position I of the remainder bucket. 
  • Then it traverses the remainder bucket and checks for the quotient when the current element is divided by the radix and inserts in the index in the quotient array that fits the result. 
  • At the end we copy from the quotient into our result 
  • Running time is O(d(n + r)). Where d is the number of buckets, r is the radix. 

Comparison-based sorting algorithms can achieve a worst-case running time of Ω (n log n) but can do no better. 

Leave a Reply

Your email address will not be published. Required fields are marked *