Counting Comparisons in a Sorting Algorithm 
Author Message
 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



Wed, 18 Jun 1902 08:00:00 GMT  
 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



Wed, 18 Jun 1902 08:00:00 GMT  
 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.

Why not post the code?

Osmo



Wed, 18 Jun 1902 08:00:00 GMT  
 
 [ 3 post ] 

 Relevant Pages 

1. Most efficient sort text file routine, sort algorithms

2. comparison algorithm

3. Comparison of Month-Length Algorithms

4. Sorting linked lists, a comparison

5. Counting compares in Sorts??

6. Help! sorting algorithm

7. Quick Sort Algorithm or Source Code

8. Independent Type Algorithm (Eg: Sorting)

9. sort algorithm trouble...

10. algorithm to calculate the median using a sorted array

11. algorithm to calculate the median for a sorted array

12. Help me searching a sorting algorithm

 

 
Powered by phpBB® Forum Software