Monday, July 5, 2010

CLRS 2e: Exercise 2.1-1

Using Figure 2.2 as a model, illustrate the operation of INSERTION-SORT on the array A = [ 31, 41, 59, 26, 41, 58] .
 I'm not going to draw pictures so I'll just show each step (with comment) starting with the original array:
  1. [ 31, 41, 59, 26, 41, 58] (original array)
  2. [ 31, 41, 59, 26, 41, 58] (31 < 41 so keep 41 there)
  3. [ 31, 41, 59, 26, 41, 58] (41 < 59 so keep 59 there)
  4. [ 31, 41, 59, 26, 41, 58] (59 > 26 so swap them)
  5. [ 31, 41, 26, 59, 41, 58] (41 > 26 so swap them)
  6. [ 31, 26, 41, 59, 41, 58] (31 > 26 so swap them)
  7. [ 26, 31, 41, 59, 41, 58] (26 is now the first element so keep it there)
  8. [ 26, 31, 41, 59, 41, 58] (59 > 41 so swap them)
  9. [ 26, 31, 41, 41, 59, 58] (41 = 41 so keep 41 there)
  10. [ 26, 31, 41, 41, 59, 58] (59 > 58 so swap them)
  11. [ 26, 31, 41, 41, 58, 59] (previous step looked at last element so done)

No comments:

Post a Comment