X hits on this document

Powerpoint document

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

77 views

0 shares

0 downloads

0 comments

16 / 28

Comp 122

linsort - 16

Lin / Devi

Comp 122

Radix-Sort(A, d)

Correctness of Radix Sort

By induction on the number of digits sorted.

Assume that radix sort works for d – 1 digits.

Show that it works for d digits.  

Radix sort of d digits radix sort of the low-order d 1 digits followed by a sort on digit d .  

RadixSort(A, d)

1.  for i 1 to d

2.      do use a stable sort to sort array A on digit i

Document info
Document views77
Page views77
Page last viewedFri Dec 09 10:35:41 UTC 2016
Pages28
Paragraphs427
Words1924

Comments