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

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 include the iteration weight in the program and use c++ and please use the following data 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