::::|| VU ||:::: idea solution of cs502

Use induction to prove that radix sort works. Where does your proof need the assumption that the intermediate sort is stable?
solution:
Basis: If , sorting on that digit sorts the array correctly.
Inductive step: Assume that RADIX-SORT sorts digits correctly. Consider two elements and , with their th digit and respectively.
(1) and : RADIX-SORT works correctly, because of most significant bit dominates regardless of the lower digits.
(2) : RADIX-SORT leaves and in the same order because it is stable sort. The order is correct since lower digits sorts correctly. That's why we need that the intermediate sort must be stable.

--
For study materials, past papers and assignments,
Join VU School at www.vuscool.com
 
Facebook Group link
http://www.facebook.com/groups/vuCoooL
 
CoooL Virtual University Students Google Group.
To post to this group, send email to coool_vu_students@googlegroups.com
 
home page
http://groups.google.com/group/coool_vu_students?hl=en