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.
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. --
Please visit www.vuzs.net For Current & Old Papers, Quizzes, Assignments and study material.
To post a new message on this group, send email to vuZs@googlegroups.com
Message Posting Rules: http://vuzs.net/faq/4795-vuzs-google-groups-basic-rules-for-posting-messages.html
--
To unsubscribe from this group, send email to vuZs+unsubscribe@googlegroups.com
--
To join this group Send blank email to vuZs+subscribe@googlegroups.com
or visit
http://groups.google.com/group/vuZs/subscribe
No comments:
Post a Comment