Question

1. Given an array A[1..n] of integers such that A[j] ≥ A[i] − d for every j > i. That means any inversion pair in A differs in value by at most d. Give an O(n + d) algorithm to sort this array.

Answer 1

So here is O(n + d) solution.

Inversion Count for an array means how far or close the array is from being sorted. If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is the maximum.

Here, two elements a[i] and a[j] form an inversion A[j] ≥ A[i] − d for every j > i

Let A[] ={4, 8, 10, 2, 16, 14}

Algorithm for counting number of inversion:

 Start

step 1: Declare an array A[] 
Step 2: initialize the array A[] = {4, 8, 10, 2, 16, 14}
Step 3: Declare a variable n such that n = sizeof(arr) / sizeof(arr[0])
Step 4: now print the total number of inversion by calling the function getCount(A, n)
Step 5: stop
step 6: declaring the function getCount(A, n)
Step 7: inside getCount(A, n) initialize a InvCounter = 0
         and declare a variable d as (maximum difference between inversion pair)
step 8: Check FOR condition for i (counter) = 0, i < n - 1, i++

step 9 : if above FOR condition is true go to step 10 otherwie go to step 14.

step 10: check FOR condition for j (another counter) = i + 1, j < n , j++

step 11 : if above condition is true go to step 12 otherwise go to step 14.

step 12 : if (arr[i] - d =< arr[j]) is true go to step 13 otherwise go to step 14.

step 13: increament the invCounter to plus one.

step 14: return to the step 5 and total number of invCounter will be printed.

step 12: stop

Algorithm for sorting:

1. Like merge sort, divide the array into two equal or almost equal halves in each step until the base case is reached.
2. Create a function merge that counts the number of inversions when two halves of the array are merged, create two indices i and j, i is the index for first half and j is an index of the second half. if a[j] is greater than equals to a[i] - d where d is maximum difference between inversion pair, then there are (mid – i) inversions. because left and right subarrays are sorted, so all the remaining elements in left-subarray (a[i+1], a[i+2] … a[mid]) with the maximum diference between inversion pair will be less than equals to a[j].
3. Create a recursive function to divide the array into halves and find the answer by summing the number of inversions is the first half, number of inversion in the second half and the number of inversions by merging the two.
4. The base case of recursion is when there is only one element in the given half.
5. Print the answer