Let A = A[1], , A[n] be an array of n distinct positive integers (the value of t
ID: 3883952 • Letter: L
Question
Let A = A[1], , A[n] be an array of n distinct positive integers (the value of these integers could be very large). An inversion is a pair of indices i and j such that i A [j]. For example in the array [30000, 80000, 20000, 40000, 10000], the pair i = 1 and j = 3 is an inversion because A[1] = 30000 is greater than A[3] = 20000. On the other hand, the pair i = 1 and j = 2 is not an inversion because A[1] = 30000 is smaller than A [2] = 80000. In this array there are 7 inversions and 3 non-inversions. (a) Describe in one sentence the natural brute-force algorithm. (b) What is the complexity of the natural brute-force algorithm? (No explanation.) (c) Now give an O(n log n)-time algorithm.Explanation / Answer
a) Brite-Force algorithm:
Brute-force is a approach which means we will have to go through all the possible solutions of that problem extensively.
b) Complexity for the mentioned problem using brute-force approach is
O(n2)
c) O(n log n) algorithm:
/*We can achieve this task by sorting the array first and then returning the number of inversions in the array. */
int mergeSort(int array[], int maxsize)
{
int *temp = (int *)malloc(sizeof(int)* maxsize);
return sortMerge(array, temp, 0, maxsize - 1);
}
/* A recursive function that sorts an array and returns the number of in versions*/
int sortMerge(int array[], int temp[], int left, int right)
{
int middle, inverse_count = 0;
if (right > left)
{
//Divide the array into two parts
middle = (right + left)/2;
/* the value of inversion count will be sum of inversions in left-part, right-part and number of inversions in merging */
inverse_count = sortMerge(array, temp, left, middle);
inverse_count += sortMerge(array, temp, middle+1, right);
/*Merge the two parts*/
inverse_count += conquer(array, temp, left, middle+1, right);
}
return inverse_count;
}
/* Function to merge two sorted arrays and returns inverse count in the arrays.*/
int conquer(int array[], int temp[], int left, int middle, int right)
{
int i, j, k;
int inverse_count = 0;
i = left; /* i points index for left subarray*/
j = middle; /* j points index for right subarray*/
k = left; /* k points index for resultant merged subarray*/
while ((i <= middle - 1) && (j <= right))
{
if (array[i] <= array[j])
{
temp[k++] = array[i++];
}
else
{
temp[k++] = array[j++];
inverse_count = inverse_count + (middle - i);
}
}
/* Copy the remaining elements of left subarray to temp*/
while (i <= middle - 1)
temp[k++] = array[i++];
Copy the remaining elements of right subarray to temp*/
while (j <= right)
temp[k++] = array[j++];
/*Copy back the merged elements to original array*/
for (i=left; i <= right; i++)
array[i] = temp[i];
return inverse_count;
}
/* main function to test above functions */
int main(int argv, char** args)
{
int array[] = {300, 800, 200, 100, 400};
printf(" Total number of inversions are %d ", mergeSort(array, 5));
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.