Question

1. Prove by induction on the column being sorted that RADIX-SORT correctly sorts its input. The Induction should include the following steps: Loop Invariant, Initialization, Maintenance, and Termination.

Answer 1

ANS:-

Radix sort is a fast algorithm which can be used
to sort k-digit integers base r (the radix).
radixSort(L). Input: linked list L.
Action: the cells on L are rearranged so that the
list is sorted.
The digits of the integer x are numbered as
x= dk-1, dk-2, ... , d2, d1, d0

*PSEUDO CODE*

for (i=0; i < k; i++)
for (j=0; j < r; j++)
Set Lj
to be an empty list.
while (L is not empty) do
Take the first cell off the front of L.
Let d be digit i of the key value x stored
in this cell. Add this cell to the end of
the list Ld
.
endwhile
Set L to be an empty list.
for (j=0; j < r; j++) Append Lj
to the end of L.

PROOF:-( BY INDUCTION)

LOOP INVARIANT:-

At the beginning of the for loop, the array is sorted on the last i-1 digits.

INITIALIZATION:-

The array is trivially sorted on the last 0 digits.

MAINTENANCE:-

Let's assum that the array is sorted on the last i-1 digits.After we sort on the ith digit, the array will be sorted on the last i digits.It is obvious that elements with different digit in the ith position are ordered accordingly; in the case of the same ith digit,we still get a corrct order, because we're using a stable sort and the elements were already sorted on the last i-1 digits.

TERMINATION:-

The loop terminates when i=d+1. Since the invariant holds, we have the numbers sorted on d digits.