X hits on this document

Powerpoint document

Lower Bounds & Sorting in Linear Time - page 17 / 28

96 views

0 shares

0 downloads

0 comments

17 / 28

Comp 122

linsort - 17

Lin / Devi

Comp 122

Correctness of Radix Sort

By induction hypothesis, the sort of the low-order d – 1 digits works, so just before the sort on digit d , the elements are in order according to their low-order d – 1 digits.  The sort on digit d will order the elements by their dth digit.

Consider two elements, a and b, with dth digits ad and bd:

If ad < bd , the sort will place a before b, since a < b regardless of the low-order digits.

If ad > bd , the sort will place a after b, since a > b regardless of the low-order digits.

If ad = bd , the sort will leave a and b in the same order, since the sort is stable.  But that order is already correct, since the correct order of  is determined by the low-order digits when their dth digits are equal.

Document info
Document views96
Page views96
Page last viewedFri Jan 20 06:55:18 UTC 2017
Pages28
Paragraphs427
Words1924

Comments