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