Hello, how could one show how to sort these values, 13, 41, 45, 23, 32, 67, 83,

Question

Hello, how could one show how to sort these values, 13, 41, 45, 23, 32, 67, 83, 10, 14, 22 using the radix sort. If possible can I see a demonstration showing the stacks (buckets) and intermediate steps? Also how efficent is it to sort the those values, still using the radix sort, but with the values converted to binary before beginning. In terms of speed, which version (just using the radix sort, or converting it to binary first) should be chosen? Thank you, I am curious to why one would be more efficent than the other.

Explanation / Answer

Original unsorted list:
   13,41,45,23,32,67,83,10,14,22

LSD Radix sort: Least Significant Digit First

Sorting by least Significant digit(1s place) gives:
   10,41,32,22,13,23,83,14,45,67

       Notice that we keep 32 before 22, because 32 occured before 22 in original list, and similarly 13,23 and 83.

Sorting by least Significant digit(10s place)
   10,13,14,22,23,32,41,45,67,83

The first counting pass starts on the least significant digit of each key, producing an array of bucket sizes:
   1(bucket size for digit 0: 10)
   1(bucket size for digit 1: 41)
   2(bucket size for digit 2: 32 and 22)
   3(bucket size for digit 3: 13,23 and 83)
   1(bucket size for digit 4: 14)
   1(bucket size for digit 5: 45)
   1(bucket size for digit 7: 67)

A second counting pass on the next more significant digit of each key will produce an array of bucket sizes:
   3(bucket size for digit 1: 10,13 and 14)
   2(bucket size for digit 2: 22 and 23)
   1(bucket size for digit 3: 32)
   2(bucket size for digit 4: 41 and 45)
   1(bucket size for digit 6: 67)
   1(bucket size for digit 8: 83)

Worst Case running time of Radix Sort is O(wN), where w is a length of intergers and N is the total number of intergers.

By converting decimal numbers to binary numbers we will get:
   00001101, 00101001, 00101101, 00010111, 00100000, 01000011, 010100011, 000001010, 00001110, 00010110

Sorting by least Significant digit(1s place) gives:
   00100000, 000001010, 00001110, 00010110, 00001101, 00101001, 00101101, 00010111, 01000011, 010100011

Sorting by least Significant digit(2nd place) gives:
   00100000, 00001101, 00101001, 00101101, 000001010, 00001110, 00010110, 00010111, 01000011, 010100011

an so on...

So we can see that binary radix sort will take more time as value of w is increased also it will take more space.

We can say that Radix sort depends on the length. So we will prefer radix sort on decimal number over binary numbers.

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.