2. (25 Points) Let A[0..n - 1] be an array of real numbers (or any ordered...

 

Transcribed Image Text:

2. (25 Points) Let A[0..n - 1] be an array of real numbers (or any ordered set). A pair (A[i], A[j]) is said to be an inversion if these numbers (elements) are out of order, i.e., i < j but A[i] > A[j]. Note that this pair need not be adjacent. The array/sequence (3, 2, 1) contains three inversions: (3,2), (2,1), and (3,1). (10 Points) Write a program with a nave O(n) [sorting] algorithm that counts the number of inversions in such an array A. Call your program/project 'easyinversioncount'. (15 Points) Write a program with a O(n log n) [sorting] algorithm that counts the number of inversions in such an array A. Call your program/project 'fastinversioncount'. (Hints to follow...) 2. (25 Points) Let A[0..n - 1] be an array of real numbers (or any ordered set). A pair (A[i], A[j]) is said to be an inversion if these numbers (elements) are out of order, i.e., i < j but A[i] > A[j]. Note that this pair need not be adjacent. The array/sequence (3, 2, 1) contains three inversions: (3,2), (2,1), and (3,1). (10 Points) Write a program with a nave O(n) [sorting] algorithm that counts the number of inversions in such an array A. Call your program/project 'easyinversioncount'. (15 Points) Write a program with a O(n log n) [sorting] algorithm that counts the number of inversions in such an array A. Call your program/project 'fastinversioncount'. (Hints to follow...)