Counting Comparisons in a Sorting Algorithm

Quote:

>What I have done is write a simple program to sort numbers from a data

>file using a insertion algorithm. What I have to do now is to count the

>number of steps it took and then display. I'm a beginner but if any

>body could give me advice or where to look I would greatly appreciate

>it.

Hi Marc,

I would declare two counter variables, one to count the number of

comparisions, and one for the number of data moves. Integers will do

normally, they will hold values up to 32767, but you can also use

words (0..65536) or longints (up to 2147483647). So you declare these

variables like this:

var

Compares, Moves: word;

Then, at the start of the program, set these variables to 0:

Compares:= 0;

Moves:= 0;

In the sorting routine, increment the value of Compares each time you

do a data comparision (use Inc(Compares) or Compares:= Compares+1).

Same thing for Moves: add 1 for every data move. Wou will probably

have some place where you conditionally 'exchange' or 'swap' two data

values: this is normally done in three moves, so add 3 to Moves there.

Now, after the sorting is done, write the values of Compares and

Moves. That's all.

When you have included the counters in your program, it will be

interesting to see how the number of compares and moves depend on the

number of data items your program sorts. Start with for instance 10

items. Make a note of the counts. Then repeat with 20 items, then 40,

80, etc, doubling the number for each run. You can make a table of it

or plot the values in a graph.

Also interesting is to see if it makes any difference whether the

program has to sort random data or data that's already nearly in the

right order. So repeat the experiment, using sorted data for input,

and see what happens to the figures. You may or may not get the same

pattern, depending on the implementation of the sort algorithm.

Good luck,

Bob Ferguson.

--

J.R. Ferguson, Amsterdam, The Netherlands