Posted by Sleepless Snowman on August 05, 1999 at 23:40:27:
In Reply to: HW 17 posted by Nelson Simpkins on August 05, 1999 at 22:30:53:
The way to count is this...
suppose a list has elements "0 1 2 3 4 5 6 7". And the order of access is 4 2 4 7, and it's using the method suppose "count".
Iteration 0, seek nothing
Frequency: 0 0 0 0 0 0 0 0
List: 0 1 2 3 4 5 6 7
Comparisons: 0
Iteration 1, seek 4
Frequency: 1 0 0 0 0 0 0 0
List: 4 0 1 2 3 5 6 7
Comparisons: 5
Explanation: The number of times it had to compare to reach "4" was 5. Thus, we mark frequency of 4 to 1, and 4 is moved to the front of the list because everything else has frequency less than 1.
Iteration 2, seek 2
Frequency: 1 1 0 0 0 0 0 0
List: 4 2 0 1 3 5 6 7
Comparisons: 4+4=8
Explanation: This time, it took 4 times to get to where "2" was, thus we added it to the current comparison count. and because its frequency count is not greater than 4's, it will just remain in second place.
Iteration 3, seek 4
Frequency: 2 1 0 0 0 0 0 0
List: 4 2 0 1 3 5 6 7
Comparisons: 8+1=9
Explanation: Here, we are seeking for "4." However, because 4 is in the first place, it only gets 1 compare. And we also increase its frequency by 1 to 2.
Iteration 4, seek 7
Frequency: 2 1 1 0 0 0 0 0
List: 4 2 7 0 1 3 5 6
Comparisons: 9+8=17
Explanation: Here we move 7 behind to 2 because it's not greater than 2's frequency. But we increment 7's frequency count, and also because it took us 8 steps to traverse to 7's previous position, we increment the current comparison counter with 8, leaving us with a total of 17.
Hope that helps :)
Sleepless