

**I already have counting the number of elements programmed, which was fairly easy, but now I am confused with the comparisons. how exactly would I program this exactly?**



please help me understand what exactly to do bc the wording is really confusing me.  

Problem Statement



In order to compute the average number of key comparisons made in a sort, all n! permutations must be taken into account. For a treesort, this means counting the number of comparisons made for each insertion in a particular permutation. The text file permutations.txt contains 153 lines, comprising all permutations of n! elements for n = 1 to 5. (The first line is the one permutation for n = 1, the next two lines are the two permutations for n = 2, and so forth.)



You are to write a main program named program3.cpp which for n = 1 to 5, computes the total number of key comparisons for all insertions (by building the binary search tree for each permutation) and also the total comparisons divided by n*log2n. (You may approximate log2n as 3.32193*log10n.) It should then output the results in the three columns to the screen; all except the last two lines of output (for n = 4 and n = 5) should look like:



n = Number of elements  

c = Total number of comparisons  

k = c/(n*log2(n)), output to two decimal places



n c k  

- ----- -----  

1 0 0.00  

2 2 1.00  

3 16 3.36 **<-- why 16?**



(Be sure to wait for a dummy character to be input at the end, as usual.) Even though the program will be tested by the grader using the permutations.txt just as it has been given to you, the main program should be able to be easily modified to work for up to n = 9. The following files may be used (and modified where necessary):



BST.h  

BST.cpp  

TreeNode.h  

KeyedItem.h



**here are the permutations**  

1  

12  

21  

123  

132  

213  

231  

312  

321  

1234  

1243  

1324  

1342  

1423  

1432  

2134  

2143  

2314  

2341  

2413  

2431  

3124  

3142  

3214  

3241  

3412  

3421  

4123  

4132  

4213  

4231  

4312  

4321  

12345  

12354  

12435  

12453  

12534  

12543  

13245  

13254  

13425  

13452  

13524  

13542  

14235  

14253  

14325  

14352  

14523  

14532  

15234  

15243  

15324  

15342  

15423  

15432  

21345  

21354  

21435  

21453  

21534  

21543  

23145  

23154  

23415  

23451  

23514  

23541  

24135  

24153  

24315  

24351  

24513  

24531  

25134  

25143  

25314  

25341  

25413  

25431  

31245  

31254  

31425  

31452  

31524  

31542  

32145  

32154  

32415  

32451  

32514  

32541  

34125  

34152  

34215  

34251  

34512  

34521  

35124  

35142  

35214  

35241  

35412  

35421  

41235  

41325  

41352  

41523  

41523  

41532  

42135  

42153  

42315  

42351  

42513  

42531  

43125  

43152  

43215  

43251  

43512  

43521  

45123  

45132  

45213  

45231  

45312  

45321  

51234  

51243  

51324  

51342  

51423  

51432  

52134  

52143  

52314  

52341  

52413  

52431  

53124  

53142  

53214  

53241  

53412  

53421  

54123  

54132  

54213  

54231  

54312  

54321




need help with binary tree node comparisons


can someone please atleast tell me why 3 elements gives me 16 comparisons



