public class RadixSort
1: import java.util.ArrayDeque;
2: import java.util.ArrayList;
3: import java.util.Collections;
4: import java.util.List;
5: import java.util.Queue;
6: import java.util.Random;
7: import java.util.Scanner;
9: /**
10: * A program to demonstrate Radix sort.
11: *
12: * @author Mark Young (A00000000)
13: */
14: public class RadixSort {
15:
16: private static final Scanner KBD = new Scanner(System.in);
17: private static final Random rand = new Random();
18: private static final boolean TRACING = true;
19: private static final int LIST_SIZE = 12;
21: /**
22: * @param args the command line arguments
23: */
24: public static void main(String[] args) {
25: List<Integer> numbers = makeList(LIST_SIZE);
26:
27: System.out.println("Before sorting: " + numbers);
28: radixSort(numbers);
29: System.out.println("After sorting: " + numbers);
30: }
31:
32: /**
33: * Apply radix sort to the given list.
34: *
35: * @param list the list of integers to sort
36: */
37: private static void radixSort(List<Integer> list) {
38: // create the ten queues
39: List<Queue<Integer>> queues = makeQueues();
41: // find the maximum value in the list
42: int max = Collections.max(list);
44: // go thru each power of 10 till we reach/pass the maximum
45: for (int place = 1; place <= max; place *= 10) {
46: // move each number into the queue for its current digit
47: for (int number: list) {
48: int digit = (number / place) % 10;
49: queues.get(digit).add(number);
50: }
51: if (TRACING) showQueues(place, queues);
53: // clear the list in prep for refilling it
54: list.clear(); // !!!
56: // refill the list from the queues
57: for (int i = 0; i < queues.size(); i++) {
58: Queue<Integer> queue = queues.get(i);
59: while (!queue.isEmpty()) {
60: list.add(queue.remove());
61: }
62: }
63: if (TRACING) System.out.println("list is now: " + list);
64: }
65: }
67: /**
68: * Make an array of ten queues to hold integers.
69: *
70: * @return an array of ten queues of integers
71: */
72: private static List<Queue<Integer>> makeQueues() {
73: List<Queue<Integer>> queues = new ArrayList<>();
74: for (int i = 0; i < 10; i++) {
75: queues.add(new ArrayDeque<>());
76: }
77: return queues;
78: }
79:
80: /**
81: * Make a list of integers of the given size.
82: *
83: * @param size the number of elements in the list
84: * @return a list of {@code size} integers in the range [0, 10000)
85: */
86: private static List<Integer> makeList(int size) {
87: List<Integer> result = new ArrayList<>();
88: for (int i = 0; i < size; ++i) {
89: result.add(rand.nextInt(10000));
90: }
91: return result;
92: }
93:
94: /**
95: * Show the contents of the queues.
96: *
97: * @param digit the value of the digit we're looking at
98: * @param queues the array of ten queues holding the numbers
99: */
100: private static void showQueues(int digit, List<Queue<Integer>> queues) {
101: // report the digit we're sorting on
102: System.out.println("Sorting on " + digit + "'s digit:");
104: // for each of the ten queues
105: for (int i = 0; i < queues.size(); ++i) {
106: Queue<Integer> queue = queues.get(i);
108: // print the contents of that queue
109: // NOTE: uses an iterator on the queue
110: // -- avoid this sort of thing in submissions
111: // unless I specifically ask for it
112: System.out.printf(" - queues[%d]:", i);
113: for (int number: queue) {
114: System.out.printf(" %04d", number);
115: }
116: System.out.println();
117: }
118: pause();
119: }
120:
121: /**
122: * Prompt the user and wait for them to press the enter key.
123: */
124: private static void pause() {
125: System.out.print("\n...press enter...");
126: KBD.nextLine();
127: System.out.println();
128: }
130: }