I REALLY NEED HELP WITH THIS ASAP!! THANK YOU.
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,j≥0) 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 five sorting algorithms for solving this
problem: Two O(n log n) algorithms (merge sort and quick
sort),
and the others selection, insertion, and buble sort. please follow
these steps throughout the program, step 1: summation,
step2:sorting,step3: adjusting and step 4: modify sorting using all
of the sorts
please include the iteration weight in the program whose formula is w= 1/ (1 + #w)
and please use C++ only no other languages
and please use the following sources and add comments on each
line.
source 1:
20
8631
7506
3470
8335
8273
5887
8591
107
8821
2463
8901
2440
4048
8309
4794
8343
915
2997
4707
5666
6997
8326
3572
4067
320
1380
8760
4058
8204
4835
2589
9605
6737
8770
822
5955
4908
5457
7722
6416
674
5688
source 2:
6918
5841
1800
3006
5978
4789
9629
6580
2447
1031
1285
2677
4164
8818
5188
6865
8358
334
8810
836
3551
2314
8614
4591
1099
2504
5324
1639
376
9614
219
1883
9581
5385
7482
3014
2358
976
1332
8553
3290
7081
5370
source 3:
2699
9754
6950
9294
6453
9368
6560
379
30
3800
9890
9638
8516
6124
982
7697
107
6567
55
8552
660
6093
4757
1656
9760
3466
9225
6068
3755
3828
7154
9124
8568
8633
1187
2745
8873
8064
5460
3013
352
8251
4794
source 4:
8921
9948
3937
5338
6914
4891
2144
9648
701
4596
3513
2960
62
3031
4922
6258
9365
5680
1659
7304
4492
1513
8084
541
17
8440
6966
7976
7018
5907
9763
5786
9838
1023
5548
93
894
1435
2617
7658
4962
2139
3890
Given an array :We can use following java code to count number of inversions.
class inversion
{
static int mergeSort(int arr[], int array_size) //sort the input array and return number of inversions
{
int temp[] = new int[array_size];
return _mergeSort(arr, temp, 0, array_size - 1);
}
/* An auxiliary recursive which sorts the input array and return number of inversions in the array*/
static int _mergeSort(int arr[], int temp[], int left, int right)
{
int mid, inv = 0;
if (right > left)
{
/* Divide the array into two parts and call _mergeSort and CountInv()
for each of the parts */
mid = (right + left)/2; //get the middle element
inv =inv + _mergeSort(arr, temp, mid+1, right); ////get the inversin count in right part
inv = _mergeSort(arr, temp, left, mid); //get the inversin count in left part
inv =inv + merge(arr, temp, left, mid+1, right); //get the inversion count in merging the left and right part
}
return inv;
}
//It will merge two sorted array and count the inversion
static int merge(int arr[], int temp[], int left, int mid, int right)
{
int i, j, k;
int inv = 0;
i = left; /* i is index for left subarray*/
j = mid; /* j is index for right subarray*/
k = left; /* k is index for resultant merged subarray*/
while ((i <= mid - 1) && (j <= right))
{
if (arr[i] <= arr[j])
{
temp[k++] = arr[i++];
}
else
{
temp[k++] = arr[j++];
inv+= (mid - i);
}
}
/* Copy the remaining elements of right subarray
(if there are any) to temp*/
while (j <= right)
temp[k++] = arr[j++];
/* Copy the remaining elements of left subarray
(if there are any) to temp*/
while (i <= mid - 1)
temp[k++] = arr[i++];
/*Copy back the merged elements to original array*/
for (i=left; i <= right; i++)
arr[i] = temp[i];
return inv;
}
public static void main(String[] args)
{
int arr[] = new int[]{1, 20, 6, 4, 5};
System.out.println("Number of inversions are " + mergeSort(arr, 5));
}
}
IF YOU HAVE ANY DOUBTS COMMENT BELOW
HOPE THIS HELPS YOU
I REALLY NEED HELP WITH THIS ASAP!! THANK YOU. In the context of the Web, the...