**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

*Edited 4 Years Ago by jigglymig*: n/a