Homework 17

Questions 10.4 from the course text.

Solution

# = element being searched for
c = number of comparisons

(a)

# c 0    1    2    3    4    5    6    7
3 4 3(1) 0    1    2    4    5    6    7
7 8 3(1) 7(1) 0    1    2    4    5    6
7 2 7(2) 3(1) 0    1    2    4    5    6
6 8 7(2) 3(1) 6(1) 0    1    2    4    5
7 1 7(3) 3(1) 6(1) 0    1    2    4    5
4 7 7(3) 3(1) 6(1) 4(1) 0    1    2    5
6 3 7(3) 6(2) 3(1) 4(1) 0    1    2    5
7 1 7(4) 6(2) 3(1) 4(1) 0    1    2    5
6 2 7(4) 6(3) 3(1) 4(1) 0    1    2    5
7 1 7(5) 6(3) 3(1) 4(1) 0    1    2    5
4 4 7(5) 6(3) 4(2) 3(1) 0    1    2    5
2 7 7(5) 6(3) 4(2) 3(1) 2(1) 0    1    5
4 3 7(5) 6(3) 4(3) 3(1) 2(1) 0    1    5
7 1 7(6) 6(3) 4(3) 3(1) 2(1) 0    1    5
6 2 7(6) 6(4) 4(3) 3(1) 2(1) 0    1    5

Solution : 7 6 4 3 2 0 1 5
Number of comparisons : 54

(b)

# c 0 1 2 3 4 5 6 7
3 4 3 0 1 2 4 5 6 7
7 8 7 3 0 1 2 4 5 6
7 1 7 3 0 1 2 4 5 6
6 8 6 7 3 0 1 2 4 5
7 2 7 6 3 0 1 2 4 5
4 7 4 7 6 3 0 1 2 5
6 3 6 4 7 3 0 1 2 5
7 3 7 6 4 3 0 1 2 5
6 2 6 7 4 3 0 1 2 5
7 2 7 6 4 3 0 1 2 5
4 3 4 7 6 3 0 1 2 5
2 7 2 4 7 6 3 0 1 5
4 2 4 2 7 6 3 0 1 5
7 3 7 4 2 6 3 0 1 5
6 4 6 7 4 2 3 0 1 5

Solution : 6 7 4 2 3 0 1 5
Number of comparisons : 59

(c)

# c 0 1 2 3 4 5 6 7
3 4 0 1 3 2 4 5 6 7
7 8 0 1 3 2 4 5 7 6
7 7 0 1 3 2 4 7 5 6
6 8 0 1 3 2 4 7 6 5
7 6 0 1 3 2 7 4 6 5
4 6 0 1 3 2 4 7 6 5
6 7 0 1 3 2 4 6 7 5
7 7 0 1 3 2 4 7 6 5
6 7 0 1 3 2 4 6 7 5
7 7 0 1 3 2 4 7 6 5
4 5 0 1 3 4 2 7 6 5
2 5 0 1 3 2 4 7 6 5
4 5 0 1 3 4 2 7 6 5
7 6 0 1 3 4 7 2 6 5
6 7 0 1 3 4 7 6 2 5

Solution : 0 1 3 4 7 6 2 5
Number of com parisons : 95