# Homework : Inversions(algorithms-sorting)

Write C++ code to implement the algorithm for counting the number of inversions in a list of numbers.

The algorithm should determine the number of inversions in any permutation on n elements in Theta(N*logN) worst-case time.

To explain what the inversion is, let A[1..n] be an array of n distinct numbers. If i < j and A[i] > A[j], then the pair ( i , j ) is called an inversion of A.

For example, input array of <2,3,8,6,1> has 5 inversions, and they are (2,1),(3,1),(8,6),(8,1),(6,1).

Test the program on your own and provided test data (test files 1 through 4).

You may use linked lists or (dynamic) arrays to represent

lists, but you have to make sure that your program will work for lists of any length (up to a certain limit).

**HINT** for this program is to modify the _merge sort_.

I have attached test files 1 through 4, sample outputs, and codes for input files.

Important Requirements:

1. Your program MUST compile and be executable on the Red Hat Linux 9.

3. You MUST use a 'makefile' to compile and link your C++ code, and all C++ source code files are '*.cc' or '*.h' files.

4. You MUST add README file as I explained in the deliverables.

**NOTICE** : Please try to avoid using complicated coding techniques since this is a homework for algorithms class.

Try to use basic data structures, and please add detailed comments! If you can fully satisfy all of my requirements, and finish the coding and turn in the program by October 22nd, 11P.M. western pacific time, I am willing to pay \$100!

## Deliverables

Implement the algorithm for counting the number of inversions in a list of numbers.

The algorithm should determine the number of inversions in any permutation on n elements in Theta(N*logN) worst-case time.

To explain what the inversion is, let A[1..n] be an array of n distinct numbers. If i < j and A[i] > A[j], then the pair ( i , j ) is called an inversion of A.

For example, input array of <2,3,8,6,1> has 5 inversions, and they are (2,1),(3,1),(8,6),(8,1),(6,1).

Test the program on your own and provided test data (test files 1 through 4).

You may use linked lists or (dynamic) arrays to represent

lists, but you have to make sure that your program will work for lists of any length (up to a certain limit).

**HINT** for this program is to modify the _merge sort_.

I have attached test files 1 through 4.

(i) The program will accept the input from a text file in the following format:

(all the ki, ni and mi's are positive integers).

k1

n1 n2 n3 n4 n5

n6 n7 n8 n9 n10 n11 n12

......

k2

m1 m2 m3 m4 m5 m6 m7

m8 m9 m10

......

This file contains a number of sequences of integers, for each of which inversions are to be counted separately. Each sequence begins with a ki, which is the number of integers in the ith sequence, all by itself on a separate line. From next line onwards will begin a sequence of integers.

These numbers could be separated by white spaces or linebreaks. The next sequence information follows after a single blank line. Inversions are counted for each sequence using the algorithm of counting the number of inversions. Your program should process all the sequences in the input file and write the results into the console.

A concrete sample input file is provided below. However your program should work with all files in the format given above. A sample code for reading the input file will also be provided in the labs.

(ii) Your program should be named "as1". The input file name should be taken by your program as a command line parameter. For example, if an input file is named as "test1", program should be run typing "as1 test1".

(iii) The program should print the numbers of inversions in each sequence of integers and the number of comparisons of the input integers performed by your algorithm. For example, if the input file contains:

5

1 2 3 5 4

8

9 12 11 10 21 22

23 38

Your program should print (the actual number of comparisons

1 7

3 13

Other important requirements:

1. Your program should compile and be executable on the Red Hat Linux 9.

2. Make sure you use a 'makefile' to compile and link your C++ code, and all C++ source code files are '*.cc' or '*.h' files.

3. The executable name of your program MUST be 'as1'.

4. Your program should have separate files (whenever appropriate) for the main program, prototypes of your functions, classes and their definitions.

5. You should turn in the following files:

C++ source files, makefile and README file.

The README file should explain how your program works and other details like the algorithm, data structures, and the time complexity of your algorithm. It should also contain the output obtained by your program on the provided test data (tests 1 through 4). I also provided codes for input files, and sample outputs. See attachments.

6. Do not forget to provide a makefile so that the reader only needs to type 'make' in the command line to compile your program. WITH NO FUNCTIONAL MAKEFILE,

YOU WILL GET ZERO POINTS.

## Platform

Red Hat Linux 9

( 16 comentários ) United States

ID do Projeto: #2993780

## Concedido a:

See private message.

\$59.5 USD em 2 dias
(36 Comentários)
4.6

## 7 freelancers estão ofertando em média \$48 para esse trabalho

mihaiscortaru

See private message.

\$20.88 USD in 2 dias
(159 Comentários)
6.0
senzaciosnegyes

See private message.

\$42.5 USD in 2 dias
(104 Comentários)
4.9
lalesculiviu

See private message.

\$85 USD in 2 dias
(18 Comentários)
4.2
teamvw

See private message.

\$85 USD in 2 dias
(36 Comentários)
3.8
jinri

See private message.

\$25.5 USD in 2 dias
(13 Comentários)
3.8
vw472664vw

See private message.

\$17 USD in 2 dias
(37 Comentários)
3.0