Answer the following question: Implement the radix sort of an array by using a queue for each group. The radix sort is discussed in Section 11.2.3 of Chapter 11 of your textbook. You can get more information in Radix sort.

RADIX SORT OF CHAPTER 11:

// Sorts n d-digit integers in the array theArray. radixSort(theArray: ItemArray, n: integer, d: integer): void for (j = d down to 1) { Initialize 10 groups to empty Initialize a counter for each group to 0 for (i = 0 through n - 1) Group the strings by their middle letter

{ k = jth digit of theArray[i] Place theArray[i] at the end of group k Increase kth counter by 1 } Replace the items in theArray with all the items in group 0, followed by all the items in group 1, and so on.

328 CHAPTER 11 Sorting Algorithms and Their Efficiency (AAC) (ABC, JBX) (RDT (AEO) (TLJ, RLT, KLT) (BWz) (XYz) Group the strings by their middle letter Now the strings in each group have the same middle letter, and the groups are ordered by that letter. As before, the strings within each group retain their relative order from the previous group of all strings. Combine these groups into one group, again preserving the relative order of the items within each group Combine the groups AAC,ABC, JBX, RDT, AEO, TLJ, RLT, KLT, BWZ, XYZ Now form new groups according to the first letter of each string Group the strings by their first letter (AAC, ABC, AEO) (BWZ) (JBX) (KLT) (RDT, RLT) (TLJ) (XYZ) Finally, combine the groups, again maintaining the relative order within each group AAC, ABC, AEO, BWZ, JBX, KLT, RDT, RLT, TLJ, XYZ Sorted strings The strings are now in sorted order. In the previous example, all character strings had the same length. If the character strings have varying lengths, you can treat them as if they were the same length by padding them on the right with blanks as necessary To sort numeric data, the radix sort treats a number as a character string. You can treat numbers as if they were padded on the left with zeros, making them all appear to be the same length. You then form groups according to the right-most digits, combine the groups, form groups according to the next-to-last digits, combine them, and so on, just as you did in the previous example. Figure 11-14 shows a radix sort of eight integers. FIGURE 11-14 Aradix sort of eight integers Original integers 0123, 2154, 0222, 0004, 0283, 1560, 1061, 2150 (1560, 2150) (1061 02) (0123, 0283) (2154, 0004) Grped by fourth digit 1560, 2150, 1061, 0222, 0123, 0283, 2154, 0004 (0004) (0222, 0123) (2150, 2154) (1560, 1061) (0283) 0004, 0222, 0123, 2150, 2154, 1560, 1061, 0283 (0004, 1061) (0123, 2150, 2154) (0222, 0283) (1560) 0004, 1061, 0123, 2150, 2154, 0222, 0283, 1560 (0004, 0123, 0222, 0283) (1061, 1560 (2150, 2154) 0004, o123, o222, 0283, 1061, 1560, 21 50, 2154 Grouped by third digit Grouped by second digit Combined Grouped by first digit Combined (sorted) The following pseudocode describes the algorithm for a radix sort of n decimal integers of d dig- its each: /1 Sorts n d-digit integers in the array theArray radixSort (theArray: ItemArray, n: integer, d: integer): void for (j d down to 1) Initialize 10 groups to empty Initialize a counter for each group to 0 for i 0 through n 1)