Board index » delphi » Counting Comparisons in a Sorting Algorithm

Counting Comparisons in a Sorting Algorithm

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.

Thanks

 

Re:Counting Comparisons in a Sorting Algorithm


On Mon, 20 Oct 1997 19:03:17 -0400, Marc Stevens <sag...@palmnet.net>
wrote:

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
e-mail: j.r.fergu...@iname.com

Re:Counting Comparisons in a Sorting Algorithm


In article <344BE334.FB9DB...@palmnet.net>,
Marc Stevens  <sag...@palmnet.net> wrote:

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.

Why not post the code?

Osmo

Other Threads