In the context of the Web, the main applications include building meta-search en
ID: 3755244 • Letter: I
Question
In the context of the Web, the main applications include building meta-search engines, combining ranking functions, selecting documents based on multiple criteria. When we use Google search engine to search information, Google always show us a long list links one by one. Suppose Google considers combining ranking results from different sources. At beginning they treat each source equally. In other words, they just sum all ranks from various sources for each web page, and use the summation to generate the combined rank. However, they want to investigate the reliability of each source and assign high weight to the most reliable one in the future rank combination. Here we simply define the reliability is inversely proportional to the number of inversions between the rank from a source with the combined rank. That is, the source is more reliable if it has fewer inversions. Do you have the solution for Google? (Hint: this is a real world application of sorting)
How do we count inversions? For an array A, when i < j (i,j0) but A[i]>A[j], this is an inversion. The sorting process is to reduce the number of inversions. For a complete sorted array/list, the inversion is 0. Here is an example (refer to the table below). In this example, there are two inversions in the source A.
Page8
Page5
Page6
Page1
Page3
Combined Rank
25
27
39
40
45
Source A
4
5
8
9
6
Acquirement:
Sorting is one of the most broadly used fundamental operations in data processing. There are numerous sorting algorithms available. In this project, you are asked to modify the existing algorithms for the real-world applications. You are required to modify three sorting algorithms for solving this problem:
Requirements:
Using ARRAYS and INSERTION SORT Algorithm in C++
Page8
Page5
Page6
Page1
Page3
Combined Rank
25
27
39
40
45
Source A
4
5
8
9
6
Explanation / Answer
//Following is the function for insertion sort with modification to count no of inversions and return the
//inversion count
int insertionSort(int arr[], int n)
{
int i, key, j;
int inversion=0;
for (i = 1; i < n; i++)
{
key = arr[i];
j = i-1;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > key)
{
arr[j+1] = arr[j];
j = j-1;
inversion++; //Counting inversions
}
arr[j+1] = key;
}
return inversion; //returning the count
}