Question

Present an O(n) algorithm that sorts n positive integer numbers a1, a2, . . . , an which are known to be bounded by n 2 (so ai ≤ n 2 , for every i = 1, . . . , n. Use the idea of Radix Sort (discussed in class and presented in Section 8.3 in the textbook). Illustrate your algorithm by showing on paper similar to Fig. 8.3, page 198 in the textbook (make sure you indicate clearly the columns) how the algorithm sorts the following sequence of 12 positive integers: 45, 98, 3, 82, 132, 71, 72, 143, 91, 28, 7, 45. In this example n = 12, because there are 12 positive numbers in the sequence bounded by 144 = 12^2 .

Note that in order to obtain O(n) you have to adapt the Radix Sort algorithm (explain what are the “digits”, how can the “digits” of each number be calculated, and so on. Note that you cannot use the base 10 representation, because n^2 requires log10 n^2 digits, which is obviously not constant and therefore you would not obtain an O(n)-time algorithm.).

Answer 1

The time complexity of radix sort is, O(d*(n+b)) where,

d is the number of digits,

n is the number of integers,

b is the base example 10 for decimal numbers,

The total number of digit for n^2 integer will be, log10 n^2 and for base b. It will be logb n^2

Hence the total time complexity for using radiz sort for n integer (where number of integers are less than n^2) is, O((n+b)*O(log_b(n^2)) ie O((n+b)*O(log_b(n))

If we set the base b to n, then the number of digits become, logn n^2 ie 2 so the total time complexity becomes, O((n + n) * O(2)) ie O(n)

Hence, if we change the base b to n then the time complexity of radix sort becomes linear.

Let's consider the example given in the question, for the following12 integers: 45, 98, 3, 82, 132, 71, 72, 143, 91, 28, 7, 45

Let's change the base to 12, the integers becomes: 39, 82, 03, 6a, b0, 5b, 60, bb, 77, 24, 07, 39.

Now let's stably sort them on the basis of the least significant digit; after first iteration we get:

b0, 60, 82, 03, 24, 77, 07, 39, 39, 6a, 5b, bb

Stably sorting them based on the next significant digit, we get:

03, 07, 24, 39, 39, 5b, 60, 6a, 77, 82, b0, bb

Let's convert the numbers back to base 10:

03, 07, 28, 45, 45, 71, 72, 82, 91, 98, 132, 143

The above example illustrates the proposed algorithm to sort positive integers, n in number such that they are less than n^2 in linear time using radix sort.