Kevin Kihlstrom

Dr. Kihlstrom

CS 005

11 September 2007

Chapter 3 Assignment 2

3) A) 171 + 85 + 43 + 21 + 11 + 5 + 3 + 1 + 1

B) 342 – 1 =341

C) A is clearer, but B is more efficient

9) Because at the first pass you do almost N total (N-1) comparison and then one less each time. It is a summation and will always be closer to N squared.

10) Bubble sort would do fewer exchanges because selection sort would make unnecessary moves, where Bubble sort would analyze if it is in order and wouldn’t make that extra move.

24) 1 = 3 comparisons

2 = 2 comparisons

3 = 3 comparisons

4 = 1 comparison

5 = 3 comparisons

6 = 2 comparisons

7 = 3 comparisons

on average 2.43 comparisons, compared to the worst case which was 3 comparisons

27) When N = 23