Problem
You are given an array of non-negative integers, where different integers may have different numbers
of digits, but the total number of digits over all the integers in the array is n. Show how to sort the
array in O(n) time1.
1 The algorithm you are expected to implement, strictly speaking, runs in O(b · n) time, where b is the base for counting
sort. However, since we set b = 128, b is a constant and the runtime is therefore O(n).
To implement this problem, we represent a single integer as array of bytes. Each byte represents a digit
(base 128). The byte with index 0 in the array represents the least significant byte. That is, if A has
length 3, A[0] = 6, A[1] = 7, and A[2] = 8, then A represents the number 6·1280+7·1281+8·1282.
Implementation
You are given a file Lab3.java. The file contains a class Lab3
with a function problem. Implement your solutions in this function. Do not make any changes
outside of that function (e. g. by adding helper functions); such changes will be undone. Do
not output anything to the terminal.
The program already implemented in the file Lab3.java randomly generates test cases. The seed of
the random number generator is set to ensure the same test cases whenever to program is executed.
Note that the purpose of the tests is for you to avoid major mistakes. Passing all given tests does
not imply that your algorithm is correct, especially that is has the expected runtime.
0 comments