Analysis of Algorithms : An Active Learning Approach

270 APPENDIX C

Radix Sort

Chapter 4

Original Polynomial

x^3 + 4x^2 
 3 x + 2

Horner’s Method

[(x + 4) *x
 3] *x + 2

Preprocessed Coefficients

Original Polynomial

x^7 
 8 x^6 + 3x^5 + 2x^4 
 4 x^3 + 5x
 7

Horner’s Method

{[({[(x
 8) *x + 3] *x + 2} *x
 4) *x + 0] *x + 5} *x
 7

The Original:

List: 1113 2231 3232 1211 3133 2123 2321 1312 3223 2332 1121 3312

After pass 1: 2231 1211 2321 1121 3232 1312 2332 3312 1113 3133 2123 3223

After pass 2: 1211 1312 3312 1113 2321 1121 2123 3223 2231 3232 2332 3133

After pass 3: 1113 1121 2123 3133 1211 3223 2231 3232 1312 3312 2321 2332

After pass 4: 1113 1121 1211 1312 2123 2231 2321 2332 3133 3223 3232 3312

)

x 24

x^3  4 x^2 
 3 x 22


x^3 
 4 x^2  4 x 16

x 18

x
 4

[]()x^2 – (^4) *()x+ 4 +()x+ 18