Merge sort

Merge sort

Merge sort is a strategy of divide and conquer , Divide a big problem into many small problems , First solve the small problem , Then solve big problems through small problems . Because the sorting problem is given an unordered sequence , The elements to be sorted can be decomposed into two subsequences with roughly the same scale . If it's not easy to solve , Then continue to decompose the obtained subsequence , Until the number of elements contained in the subsequence is 1. Because the sequence of individual elements itself is ordered , Now you can merge , So as to get a complete ordered sequence .

Algorithm design ：
Merge sort adopts divide and conquer strategy to sort n An algorithm for sorting elements , It is a typical application and perfect embodiment of divide and conquer . It's a balance , A simple dichotomy strategy , The process can be roughly divided into ：
1） decompose ----- Divide the elements to be sorted into two subsequences of roughly the same size
2） government ----- Merge and sort the two subsequences
3） Merge ----- Merge the ordered subsequences , Get the final ordered sequence

The core code of merge sorting ：

void Merge(int A[], int low, int mid, int high)
{
     // Complete merger procedure 
	int *B = new int[high - low + 1]; // Request an auxiliary array 
	int i = low, j = mid + 1, k = 0;
	while (i <= mid && j <= high){
    
		// Save in auxiliary array from small to large B[] in 
		if (A[i] <= A[j])
			B[k++] = A[i++];
		else
			B[k++] = A[j++];
	}
	// For the sequence A[low:middle] Deal with the rest in turn 
	while (i <= mid) B[k++] = A[i++];
	// For the sequence A[middle+1:high] Deal with the rest in turn  
	while (j <= high) B[k++] = A[j++];
	// Copy the merged sequence to the original A[] Sequence  
	for (i = low, k = 0; i <= high; i++)
		A[i] = B[k++];
	delete[]B; // Release space  
}
void MergeSort(int A[], int low, int high)
{
    
	if (low < high){
    
		int mid = (low + high) / 2; // Take the midpoint  
		MergeSort(A, low, mid); // Yes A[low:mid] Merge and sort elements in  
		MergeSort(A, mid + 1, high); // Yes A[mid+1:high] Merge and sort elements in  
		Merge(A, low, mid, high); // Merge operation  
	}
}

Algorithm analysis ：
（1） Time complexity

1. decompose ： This step is only to calculate the middle position in the sub sequence , Constant time is required O(1).
2. Solve the sub problem ： Recursively solve two scales of n/2 The sub problem of , The time required is 2T(n/2).
3. Merge ：Merge The algorithm can be used in O(n) In time to complete .
   So the total running time is ：
   

（2） Spatial complexity
Variables in the program take up some auxiliary space , These auxiliary Spaces are of constant order , Each call to Merge(), A buffer of appropriate size will be allocated , And release when exiting , The maximum allocated size is n, So the space complexity is zero O(n). The stack space used by recursive calls is O(logn) （ Every time it's split in half ）

Super quick sort

https://www.acwing.com/problem/content/109/

 In this case , You have to analyze specific sorting algorithms ---- Super quick sort .
 The algorithm processes by exchanging two adjacent sequence elements n A sequence of different integers , Until the sequence is sorted in ascending order .
 For input sequences 9 1 0 5 4, Super fast sorting produces output 0 1 4 5 9.
 Your task is to determine how many swap operations need to be performed to sort a given input sequence .

 Input format 
	 The input includes some test cases .
	 Enter an integer in the first line of each test case n, Represents the length of the input sequence in the use case .
	 Next n Line enter an integer for each line ai, Represents the specific data of the input sequence in the use case , The first i The data in the row represents the i Number .
	 When the length of the input sequence contained in the input case is 0 when , Input termination , The sequence does not need to be processed .

 Output format 
	 For each input sequence that needs to be processed , Output an integer op, Represents the minimum number of exchange operations required to sequence a given input sequence , Each integer takes up one line .

 sample input ：
	5
	9
	1
	0
	5
	4
	3
	1
	2
	3
	0

 sample output ：
	6
	0

 Data range 
	0 ≤ N < 500000
	0 ≤ ai ≤ 999999999

Merge sort is achieved by using an auxiliary array , In fact, the merging process can also be merged in the form of pairwise Exchange .
And there is no need to exchange two , Just know how many elements are in reverse order , How many exchanges are needed , The answer is as long as the number .
for example ： On the left is [2, 5,8], On the right is [1], that 1 Want to run 2,5,8 front , Need 3 Secondary exchange , Because merge sort is to merge two arrays that have been sorted , in other words , When you know 2 Greater than 1 when , that 2 The following numbers must be better than 1 Be big , Then we have to exchange mid - i + 1 Time .
The merge sorting method is still used when merging , There is no pairwise Exchange , Just add one more line of code when merging .

#include<iostream>
#include<vector>
#include<cstdio>
using namespace std;
long long int cnt;
void Merge(long long int *A, int low, int mid, int high)
{
    
	int *B = new int[high - low + 1];
	int i = low, j = mid + 1, k = 0;
	while (i <= mid && j <= high){
    
		if (A[i] <= A[j])
			B[k++] = A[i++];
		else{
    
			B[k++] = A[j++];
			cnt += mid - i + 1; //  Add this line of code on the basis of merging and sorting 
		}
	}
	while (i <= mid) B[k++] = A[i++];
	while (j <= high)B[k++] = A[j++];
	for (i = low, k = 0; i <= high; i++)
		A[i] = B[k++];
	delete[]B;
}
void MergeSort(long long int *A, int low, int high)
{
    
	if (low < high){
    
		int mid = low + (high - low) / 2;
		MergeSort(A, low, mid);
		MergeSort(A, mid + 1, high);
		Merge(A, low, mid, high);
	}
}
int main(){
    
	int n, i;
	while (1){
    
		scanf("%d", &n);
		if (!n)
			break;
		long long int *A = new long long int[n];
		cnt = 0;
		for (i = 0; i < n; i++)
			scanf("%lld", &A[i]);

		MergeSort(A, 0, n - 1);
		printf("%lld\n", cnt);
		delete[]A;
	}
	return 0;
}

Design T-Shirt

https://vjudge.net/problem/HDU-1031

Sample Input

3 6 4
2 2.5 5 1 3 4
5 1 3.5 2 2 2
1 1 1 1 1 10
3 3 2
1 2 3
2 3 1
3 1 2

Sample Output

6 5 3 1
2 1

The question ：N Personal to M Score elements , Each line means that everyone gives M Data scored by elements , from M Of the elements K Elements

For example 1 explain ：

2	2.5	5	1	3	4
5	1	3.5	2	2	2
1	1	1	1	1	10
8	4.5	9.5	4	6	16

The last line is the total score of each element , From big to small K（K=4） One element is [16,9.5,8,6], Just output their index value .

For example 2 explain ：
Because each element gets the same total score , So take the front K（K=2） Elements .

First, the total score of each element is sorted non incrementally , Then go ahead K The index values of elements are sorted non incrementally .

#include<iostream>
#include<vector>
#include<cstdio>
using namespace std;
struct data{
    
	int id;
	double value;
}a[10010];
void Merge(data *A, int low, int mid, int high, bool flag)
{
    
	data *B = new data[high - low + 1]; // Request an auxiliary array 
	int i = low, j = mid + 1, k = 0;
	double x, y;
	while (i <= mid && j <= high){
    
		if (!flag){
    
			x = A[i].value;
			y = A[j].value;
		}
		else{
    
			x = A[i].id;
			y = A[j].id;
		}
		if (x >= y) // If two values are equal ,i advanced 
			B[k++] = A[i++];
		else
			B[k++] = A[j++];
	}
	while (i <= mid) B[k++] = A[i++];
	while (j <= high)B[k++] = A[j++];
	for (i = low, k = 0; i <= high; i++)
		A[i] = B[k++];
	delete[]B;
}
void MergeSort(data *A, int low, int high, bool flag)
{
    
	if (low < high){
    
		int mid = low + (high - low) / 2;
		MergeSort(A, low, mid, flag);
		MergeSort(A, mid + 1, high, flag);
		Merge(A, low, mid, high, flag);
	}
}
int main(){
    
	int n, m, k; // n-- The number of  m-- Element number  k-- Select quantity 
	double x;
	while (scanf("%d%d%d", &n, &m, &k) != EOF){
    
		for (int i = 0; i < m; i++) // Recount 
			a[i].value = 0;
		for (int i = 0; i < m*n; i++){
    
			a[i%m].id = i % m + 1;
			scanf("%lf", &x);
			a[i%m].value += x;
		}
		MergeSort(a, 0, m - 1, 0); // Non incremental by value 
		MergeSort(a, 0, k - 1, 1); // Non incremental by serial number 
		for (int i = 0; i < k-1; i++)
			printf("%d ", a[i].id);
		printf("%d\n", a[k - 1].id);
	}
	return 0;
}

This question uses sort() Function will be much simpler ....