Reference no: EM131158985

Radix sorting-also known as digit, pocket, and bucket sorting-is a very efficient sort for large lists whose keys are relatively short. If fact, if we consider only its big-O notation, which is O(n), it is one of the best. Radix sorts were used extensively in the punched-card era to sort cards on electronic accounting machines (EAMs). In a radix sort, each pass through the list orders the data one digit at a time. The first pass orders the data on the units (least significant) digit. The second pass orders the data on the tens digit. The third pass orders the data on the hundreds digit, and so forth until the list is completely sorted by sorting the data on the most significant digit. In EAM sorts the punched cards were sorted into pockets. In today's systems we would sort them into a linked list, with a separate linked list for each digit. Using a pocket or bucket approach, we sort eight four-digit numbers in Figure 12-26.12 If you analyze this sort, you will see that there are k sort passes, where k is the number of digits in the key. For each sort pass, we have n operations, where n is the number of elements to be sorted. This gives us an efficiency of kn, which in big-O notation is O(n). Write a program that uses the radix sort to sort 1000 random digits. Print the data before and after the sort. Each sort bucket should be a linked list. At the end of the sort, the data should be in the original array.