##1. Search

####INPUT FORMAT

1st line: one integer which we should search for.
2nd line: the amount of the integer array.
3rd line: the integer array’s content.

####Input File

22
14
1 4 5 7 8 9 10 12 15 22 23 27 32 35

####OUTPUT FORMAT

1st line: the position of the integer we search for. 0 if NO EXIST.

####Output File

9

###(1) LinearSearch

算法1.1 LINEARSEARCH
输入:n个元素的数组A[1…n]和元素x。
输出:如果x=A[j],1<=j<=n,则输出j,否则输出0.

	1. j<-1
	2. while (j<n) and (x!=A[j])
	3. 	j<-j+1
	4. end while
	5. if x=A[j] then return k else return 0

####C++ code

#include<iostream>
#include<fstream>
using namespace std;

int LinearSearch(int *arr, int size, int x);

int main() {
	ifstream fin("LinearSearch.in");
	ofstream fout("LinearSearch.out");
	int n, x;
	fin >> x >> n;
	int *arr = new int[n];
	for(int i=0; i<n; i++)
		fin >> arr[i];
	fout << LinearSearch(arr, n, x) << endl;
	return 0;
}

int LinearSearch(int *arr, int size, int x) {
	for(int j=0; j<size; j++)
		if(arr[j]==x) return (j+1);
	return 0;
}

###(2) BinarySearch

算法1.2 BINARYSEARCH
输入:n个元素的数组A[1…n]和元素x。
输出:如果x=A[j],1<=j<=n,则输出j,否则输出0.

	1. low <- 1; high <- n; j <- 0
	2. while (low<=high) and (j=0)
	3.     mid <- (low+high)/2
	4.     if x = A[mid] then j <- mid
	5.     else if x < A[mid] then high <- mid-1
	6.     else low <- mid+1
	7. end while
	8. return j

####C++ code

#include<iostream>
#include<fstream>
using namespace std;

int BinarySearch(int *arr, int size, int x);

int main() {
	ifstream fin("BinarySearch.in");
	ofstream fout("BinarySearch.out");
	int x, n;
	fin >> x >> n;
	int *arr = new int[n];
	for(int i=0; i<n; i++)
		fin >> arr[i];
	fout << BinarySearch(arr, n, x) << endl;
	return 0;
}

int BinarySearch(int *arr, int size, int x) {
	int low = 0, high = size-1, j=-1;
	while(low<=high && j==-1) {
		int mid = (low+high)/2;
		if(x==arr[mid])
			j = mid;
		else if(x<arr[mid])
			high = mid-1;
		else
			low = mid +1;
	}
	return j;
}

##2. Merge

####INPUT FORMAT

1st line: two integer, first for the first array’s length, and second for the second array’s length.
2nd line: the integers of the first array.
3rd line: the integers of the second array.
Both array are sorted already.

####Input File

5 8
2 3 32 66 80
7 11 13 45 57 60 78 90

####OUTPUT FORMAT

1st line: the sorted array.

####Output File

2 3 7 11 13 32 45 57 60 66 78 80 90

###Merge

算法1.3 Merge
输入:数组A[1…m]和它的三个索引p, q, r, 1<=p<=q<=r<=m, 两个子数组A[p…q]和A[q+1…r]各自按升序排列。
输出:合并两个子数组A[p…q]和A[q+1…r]的数组A[p…r]。

	 1. comment: B[p...r]是个辅助数组
	 2. s <- p; t <- q+1; k <- p
	 3. while s<=q and t <= r
	 4.     if A[s] <= A[t] then
	 5.         B[k] <- A[s]
	 6.         s <- s+1
	 7.     else
	 8.         B[k] <- A[t]
	 9.         t <- t+1
	10.     end if
	11.     k <- k+1
	12. end while
	13. if s=q+1 then B[k...r] <- A[t...r]
	14. else B[k...r] <- A[s...q]
	15. end if
	16. A[p...r] <- B[p...r]

####C++ code

#include<iostream>
#include<fstream>
using namespace std;

void Merge(int *arr, int p, int q, int r);

int main() {
	ifstream fin("Merge.in");
	ofstream fout("Merge.out");
	int n1, n2;
	fin >> n1 >> n2;
	int *arr = new int[n1+n2+1];
	for(int i=1; i<=(n1+n2); i++)
		fin >> arr[i];
	Merge(arr, 1, n1, n1+n2);
	for(int i=1; i<(n1+n2); i++)
		fout << arr[i] << " ";
	fout << arr[n1+n2] << endl;
	delete[] arr;
	return 0;
}

void Merge(int *arr, int p, int q, int r) {
	int *temp = new int[r+1];
	int s = p, t = q+1, k = p;
	while(s<=q && t<=r) {
		if(arr[s] <= arr[t]) {
			temp[k] = arr[s];
			s++;
		}
		else {
			temp[k] = arr[t];
			t++;
		}
		k++;
	}
	if(s==q+1)
		for(int i=k; i<=r; i++)
			temp[i] = arr[i];
	else
		for(int i=0; i<=r-k; i++)
			temp[k+i] = arr[s+i];
	for(int i=p; i<=r; i++)
		arr[i] = temp[i];
	delete[] temp;
}

##3. Sort

####INPUT FORMAT

1st line: one integer, the amount of the array’s size.
2nd line: the content of the array.

####Input File

11
6 10 9 5 3 11 4 8 1 2 7

####OUTPUT FORMAT

1st line: the sorted elements.

####Output File

1 2 3 4 5 6 7 8 9 10 11

###(1) SelectionSort

算法1.4 SELECTIONSORT
输入:n个元素的数组A[1…n]。
输出:按非降序排列的数组A[1…n]。

	1. for i <- 1 to n-1
	2.     k <- i
	3.     for j <- i+1 to n    {查找第i小的元素}
	4.         if A[j] < A[k] then k <- j
	5.     end for
	6.     if k != i then 交换A[i]A[k]
	7. end for

####C++ code

#include<iostream>
#include<fstream>
using namespace std;

void SelectionSort(int *arr, int size);

int main() {
	ifstream fin("SelectionSort.in");
	ofstream fout("SelectionSort.out");
	int n;
	fin >> n;
	int *arr = new int[n];
	for(int i=0; i<n; i++)
		fin >> arr[i];
	SelectionSort(arr, n);
	for(int i=0; i<n-1; i++)
		fout << arr[i] << " ";
	fout << arr[n-1] << endl;
	delete[] arr;
	return 0;
}

void SelectionSort(int *arr, int size) {
	for(int i=0; i<size-1; i++) {
		int k=i;
		for(int j=i+1; j<size; j++) {
			if(arr[j]<arr[k]) k=j;
		}
		if (k!=i) {
			int temp = arr[i];
			arr[i] = arr[k];
			arr[k] = temp;
		}
	}
}

###(2) InsertionSort

算法1.5 INSERTIONSORT
输入:n个元素的数组A[1…n]。
输出:按非降序排列的数组A[1…n]。

	1. for i <- 2 to n
	2.     x <- A[i]
	3.     j <- i-1
	4.     while ( j > 0 ) and ( A[j] > x )
	5.         A[j+1] <- A[j]
	6.         j <- j-1
	7.     end while
	8.     A[j+1] <- x
	9. end for

####C++ code

#include<iostream>
#include<fstream>
using namespace std;

void InsertionSort(int *arr, int size);

int main() {
	ifstream fin("InsertionSort.in");
	ofstream fout("InsertionSort.out");
	int n;
	fin >> n;
	int *arr = new int[n];
	for(int i=0; i<n; i++)
		fin >> arr[i];
	InsertionSort(arr, n);
	for(int i=0; i<n-1; i++)
		fout << arr[i] << " ";
	fout << arr[n-1] << endl;
	delete[] arr;
	return 0;
}

void InsertionSort(int *arr, int size) {
	for(int i=1; i<size; i++) {
		int temp = arr[i];
		int j = i-1;
		while( j>=0 && arr[j]>temp ) {
			arr[j+1] = arr[j];
			j = j-1;
		}
		arr[j+1] = temp;
	}
}

###(3) BottomUpSort

算法1.6 BOTTOMUPSORT
输入:n个元素的数组A[1…n]。
输出:按非降序排列的数组A[1…n]。

	1. t <- 1
	2. while t < n
	3.     s <- t; t <- 2s; i <- 0
	4.     while i+t <= n
	5.         MERGE(A, i+1, i+s, i+t)
	6.         i <- i+t
	7.     end while
	8.     if i+s < n then MERGE(A, i+1, i+s, n)
	9. end while

####C++ code

#include<iostream>
#include<fstream>
using namespace std;

void BottomUpSort(int *arr, int size);
void Merge(int *arr, int p, int q, int r);

int main() {
	ifstream fin("BottomUpSort.in");
	ofstream fout("BottomUpSort.out");
	int n;
	fin >> n;
	int *arr = new int[n+1];
	for(int i=1; i<n+1; i++)
		fin >> arr[i];
	BottomUpSort(arr, n);
	for(int i=1; i<n; i++)
		fout << arr[i] << " ";
	fout << arr[n] << endl;
	delete[] arr;
	return 0;
}

void BottomUpSort(int *arr, int n) {
	int t=1;
	while(t<n) {
		int s = t;
		t = 2*s;
		int i=0;
		while((i+t)<=n) {
			Merge(arr, i+1, i+s, i+t);
			i = i+t;
		}
		if( (i+s)<n )
			Merge(arr, i+1, i+s, n);
	}
}

void Merge(int *arr, int p, int q, int r) {
	int *temp = new int[r+1];
	int s = p, t = q+1, k = p;
	while(s<=q && t<=r) {
		if(arr[s] <= arr[t]) {
			temp[k] = arr[s];
			s++;
		}
		else {
			temp[k] = arr[t];
			t++;
		}
		k++;
	}
	if(s==q+1)
		for(int i=k; i<=r; i++)
			temp[i] = arr[i];
	else
		for(int i=0; i<=r-k; i++)
			temp[k+i] = arr[s+i];
	for(int i=p; i<=r; i++)
		arr[i] = temp[i];
	delete[] temp;
}