Ex 57 381 92 55 Rewrite as 3-digit numbers and sort on the digits, going from left to right. The list is broken into sublists, which are separated by the lines below. 057 057 057 055 381 092 055 057 092 055 092 092 055 381 381 381 We can also sort on the least significant digit (right to left). 057 381 055 055 381 092 057 057 092 055 381 092 055 057 092 381 When implementing Radix sort, we usually assume the numbers are represented in binary, and we write the code in assembly language. In this situation we can pick the k-th most bit from the left (assume 8 bit nos.) by the following two steps: Shift right k bits A := X mod 2^(k - 1) Take right-most bit KTH-BIT:=A mod 2 Radix Exchange Sort (left to right) One way to perform left-to-right Radix Sort is to have two pointers, I and J, which behave like the pointers in the PARTITION algorithm in QUICKSORT. The I starts at the front of the list and moves forward until it encounters 1; the J starts at the end of the list and moves backward until it encounters 0. The numbers are then exchanged.One pass is performed for each digit in the numbers. Ex This is the first pass. 0 1 0 0 1 0 1 0 0 1 I 1 0 1 1 1 0 0 1 1 0 0 1 0 1 0 J 0 1 0 1 0 J 0 0 1 1 0 I 1 0 1 1 1 1 0 1 1 0 1 0 1 1 0 etc. Straight Radix Sort (right-to-left) Set up two queues, one labeled 0 and the other labeled 1. Numbers are sent to the appropriate queue depending on the value of the digit being examined. After each pass, the elements of queue 0 and the elements of queue 1 are concatenated. 0 1 0 0 1 0 0 1 1 0 0 1 0 1 0 1 0 1 1 1 1 0 1 1 0 Say that these numbers are of the form b4 b3 b2 b1 b0. Pass 1 Examine b0 and send numbers to the appropriate queue. The queues are 0 0 0 1 1 0 0 1 0 1 0 1 0 1 1 0 1 0 1 0 0 1 1 0 1 1 1 The list is 0 0 1 1 0 0 1 0 1 0 1 0 1 1 0 0 1 0 0 1 1 0 1 1 1 Pass 1 complete Pass 2 Examine b1. The queues are 0 0 1 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 1 0 1 0 1 1 1 The list is 0 1 0 0 1 0 0 1 1 0 0 1 0 1 0 1 0 1 1 0 1 0 1 1 1 Pass 2 complete. Pass 3 Examine b2. The queues are 0 0 1 0 0 1 0 1 0 1 0 1 0 0 1 1 0 1 0 1 1 0 1 0 1 1 1 The list is 0 1 0 0 1 0 1 0 1 0 0 0 1 1 0 1 0 1 1 0 1 0 1 1 1 Pass 3 complete. Pass 4 Examine b3. The queues are 0 0 0 1 1 0 1 0 1 1 0 1 0 1 1 1 1 0 1 0 0 1 0 1 0 1 0 The list is 0 0 1 1 0 1 0 1 1 0 1 0 1 1 1 0 1 0 0 1 0 1 0 1 0 Pass 4 complete. Pass 5 Examine b4. The queues are 0 0 1 1 1 0 0 1 0 0 1 0 1 0 1 0 1 1 0 1 1 0 1 0 1 1 1 The list is 0 1 1 1 0 0 1 0 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 1 1 which is sorted. Pass 5 complete.