Linear Sorting In Java

In this lab assignment, we will implement a common linear sorting method: Radix sort. This is one of the few techniques for sorting numbers which operate in linear time.

Instructions

To make things simple, we will use only binary numbers. To make them even simpler, we will represent our binary numbers in string form, which will make it easier to collect individual digits at an arbitrary index d (number.charAt(d)). Provided is a class to assist in implementing a binary bucket sort. This class has two buckets: one for the binary digit 0, and one for the binary digit 1. the getAllInOrder() method returns the values in the 1 bucket (the higher values), followed by the values in the 0 bucket (the lower values). This will facilitate sorting in descending order.

import java.util.*; public class Buckets { private List zeroBucket; private List oneBucket; public Buckets() { zeroBucket = new ArrayList<>(); oneBucket = new ArrayList<>(); } public void addZero(String newValue) { zeroBucket.add(newValue); } public void addOne(String newValue) { oneBucket.add(newValue); } public List getAllInOrder() { List result = new ArrayList<>(); for (String val: oneBucket) { result.add(val); } for (String val: zeroBucket) { 2 result.add(val); } return result; } }

Write the code to perform the radix sort. It is recommended that you write a function to print the status of the sorted list of numbers after each (digit-based) iteration. This will make it easier to debug your program.

String[] origNumbers = {"0011", "1001", "1000", "0111", "0101"}; List numbers = new ArrayList<>(); for (String num: origNumbers) { numbers.add(num); } int numDigits = 4;

The program should produce output similar to the following, which includes the list before any changes, and one-line print of the list after each iteration. The last line is the final sorted (in descending order) list:

[ 0011 1001 1000 0111 0101 ]

[ 0011 1001 0111 0101 1000 ]

[ 0011 0111 1001 0101 1000 ]

[ 0111 0101 0011 1001 1000 ]

[ 1001 1000 0111 0101 0011 ]