---
title: Algorithm homework II
---
# Problem 1
- Bubble sort:
基於 bubble sort 會前項比後項, 因此會直接比較兩個相等值的元素
- Insertion sort:
Insertion sort 會將比較的值與上一項的值作比較, 若大於比較值上一項的值會寫入到當前比較項的後項, 因此遇到相同值則可以直接 Insert 至相同值的後面
- Quick sort:
## bubble sort
穩定，基於 bubble sort 會前項比後項, 因此會直接比較兩個相等值的元素，這時候不會交換，如果兩個相等的元素沒有相鄰，也能通過前面的兩兩交換把兩個相鄰起來，所以氣泡排序是一種穩定的排序演算法。
in place，因為是兩個元素比較，不會用到額外的空間。
## insertion sort
穩定，將資料分成已排序、未排序兩部份，比較是從已排序序列的末尾開始，也就是想要插入的元素和已經已排序的最大者開始比起，如果比它大則直接插入在其後面，否則一直往前找直到找到它該插入的位置。如果碰見一個和插入元素相等的，那麼插入元素把想插入的元素放在相等元素的後面。所以，相等元素的前後順序沒有改變，所以插入排序是穩定的。
in place，將資料分成已排序、未排序兩部份，不會用到額外的空間
## quick sort
不穩定，假設第一個數為基準值，從將比基準值(Pivot)小的數值移到左邊，比基準值大的數值移到右邊, 如果序列為 7 4 5 4 8 9 ，將7和4交換便會將穩定性打亂。
not in place，因為遞迴需要額外的堆疊空間
## merge sort
穩定，merge sort會先不斷拆成1個或2個，2個元素如果大小相等也沒有人故意交換，之後合併過程中我們可以保證如果兩個當前元素相等時，我們把處在前面的序列的元素儲存在結果序列的前面，這樣就保證了穩定性。所以，歸併排序也是穩定的排序演算法。
not in place，需要暫時性的暫列存放每回合Merge後的結果
## heap-sort.
不穩定, 如果a序列為 7 4 5 4 8 9 4
第一步將a[2],a[5],a[6]比大小，變為 7 4 9 4 8 5 4
第二步將a[1],a[3],a[4]比大小，變為 7 8 9 4 4 5 4
這時相同的元素之間的穩定性就被破壞了。所以，堆排序不是穩定的排序演算法。
in place，不會用到額外的空間

# Problem 2 (solved)
只能算到92681,超過就會卡

#include <iostream>

using namespace std;

int main(){
  int n, l = 1, r, m;
  cin >> n;
  m = n/2;
  r = n/2;
  while(!(m*m < n && (m + 1)*(m + 1) > n)){
    if(m*m == n){
      cout << m << ' ' << m*m << endl;
      return 0;
    }
    else if(m*m > n)
      r = m;
    else
      l = m;
    m = (l + r)/2;
  }
  cout << m << ' ' << m*m << endl;
}

# Problem 3
如何將Merge Sort在額外空間的占用優化至僅使用n/2
(以下方式使用遞迴)

第一步:先將原本n個元素組成的數列切割成左右對半，先取左半邊
第二步:繼續切割至數列僅剩一個元素
第三步:開始合併直到取的半邊完全排序好 (在此步驟裡合併好的數列暫存在額外空間中，假設為temp，而它的尺寸為n/2)
第四步:將temp中排序好的數列直接覆蓋原本數列的左半邊
第五步:接著取右半邊，重複執行第二步與第三步
第六步:用排好的原數列左半邊與temp做最後的排序，再將排序好的temp覆蓋原數列的右半邊

# Problem 4 (solved)
Data structure

#include <iostream>
#include <unordered_set>
#include <vector>
#include <sstream>

using namespace std;

struct Set{
	unordered_set<int> got;
	vector<int> elem;

	Set(){
	    stringstream ss;
	    string s;
	    int n;
    	    getline(cin, s);
	    ss << s;
    	    while(ss >> n){
        	if(got.find(n) == got.end()){
            	    got.insert(n);
	            elem.push_back(n);
    	        }
    	    }
	}
};

void Union(){
	cin.ignore();
	Set s1;
	Set s2;
	unordered_set<int>::iterator i;
	vector<int>::iterator j;
	for(j = s2.elem.begin();j != s2.elem.end();j++){
		if(s1.got.find(*j) == s1.got.end())
			cout << *j << ' ';
	}
	for(i = s1.got.begin();i != s1.got.end();i++)
		cout << *i << ' ';
	cout << endl;
	return;
}

void Intersection(){
	cin.ignore();
	Set s1;
	Set s2;
	vector<int>::iterator i;
	for(i = s2.elem.begin();i != s2.elem.end();i++){
		if(s1.got.find(*i) != s1.got.end())
			cout << *i << ' ';
	}
	cout << endl;
	return;
}

void elem(){
	int t, n;
	stringstream ss;
	string s;
	cin >> t;
	cin.ignore();
	getline(cin, s);
	ss << s;
	while(ss >> n){
		if(n == t){
			cout << "Yes" << endl;
			return;
		}
	}
	cout << "No" << endl;
	return;
}

int main(){
	int n;
	while(1){
		cout << "1.union\n2.intersection\n3.in\n4.quit\ninput #:";
		cin >> n;
		switch (n){
			case 1:
				Union();
				break;
			case 2:
				Intersection();
				break;
			case 3:
				elem();
				break;
			case 4:
				return 0;
			default:
				cout << "No this option" << endl;
		}
		cout << "--------------------------------------" << endl;
	}	
}
 

> 幹麻一直偷我要寫的題目 [name=ZoneTwelve][time=Wed, Mar 18, 2020 10:21AM][color=#0084ff]
>> 你就慢[name=vic0103520]

// 這還沒寫完
#include <iostream>
#include <vector>

class SET{
  public:
    std::vector<int> array;
    int find(int el);
    void add(int el);
    void print();
    SET union(SET B);
    SET intersection(SET B);
};
int SET::find(int el){
  int l = 0, r = array.size(), c = -1;
  while(l<r){
    c = l + ( ( r - l ) / 2 );
    if(el>array[c]){
      l = c;
    }else if(el<array[c]){
      r = c;
    }else{
      return c;
    }
    std::cout<<l<<" - "<<c<<" - "<<r<<"\n";
  }
}
void SET::add(int el){
  int i = 0;
  for(i;i<array.size()&&array[i]<el;i++){
    if(array[i]==el)
      return;
  }
  array.insert(array.begin()+i, el);
}
SET SET::union(SET B){
  int i;
  while(i<array.size()||i<B.array.size()){
    std::cout<<(i++)<<" ";
  }
}
void SET::print(){for(int i=0;i<array.size();i++)std::cout<<array[i]<<" ";std::cout<<"\n";}

int main(){
  SET A;
  std::cout<<"Hello\n";
  A.add(3);
  A.add(1);
  A.add(4);
  A.add(2);
  A.print();
  std::cout<<"Program end;\n";
}

# Problem 5 (solved)
## 解法1:
演算法概念:
透過已排序的兩個陣列去做 binary search 來搜尋X中的每項相對最接近的值
要求: min i, j (|X[i] - Y[j]|) 項
X[m], Y[n]
binary search => O(M$\log_{2}{n}$)

#include <iostream>
#include <vector>

std::vector<int> X; // 3, 5, 7
std::vector<int> Y; //  4 , 7

int abs(int a){return a>0?a:-a;}
void minimum(std::vector<int> X, std::vector<int> Y){
  int min = 99999;
  int ri, rj;
  for(int x=0;x<X.size();x++){
    int l = 0, r = Y.size();
    int c;
    while(l<r){
      c = l + (r - l) / 2;
      if(X[x]>Y[c]){
        l+=c;
      }else if(X[x]<Y[c]){
        r-=c+1;
      }else{
        break;
      }
    }
    if(min>abs(X[x]-Y[c])){
      min = abs(X[x]-Y[c]);
      ri = x;
      rj = c;
    }
  }
  std::cout<<"result: "<<min<<" - "<<ri<<", "<<rj<<"\n";
}

int main(){
  int xlen = 5, ylen = 5;
  //int x[xlen] = {3, 5, 7};
  //int y[ylen] = { 4 , 7 };
  int x[xlen] = {1, 4, 8, 9, 10};
  int y[ylen] = {2, 3 ,7, 8, 10};
  for(int i=0;i<xlen;i++)
    X.push_back(x[i]);
  for(int i=0;i<ylen;i++)
    Y.push_back(y[i]);
  //for(int i=0;i<Y.size();i++)
  //  std::cout<<Y[i]<<" ";
  minimum(X, Y);
}

> 有 bug [name=ZoneTwelve][time=Wed, Mar 18, 2020 10:32 AM][color=#0084ff]

## 解法2:
>修是修好了,但index可能會倒過來:)[name=中央第一網管]
>> 臭87 [name=ZoneTelve][color=#0084ff]

> 我發現Y的尾巴大就不會出問題,所以先比較最後一項再決定怎麼call
> 原本
> 1 2 10
> 5 6 9
> 會出問題,j在X比較大的時候會跑出input,Y[j]會變成零,所以簡單的解決辦法就是先比較再call
> [name=中央最強網管]
>
> Time complexity O(M+N)

#include <iostream>
#include <vector>

using namespace std;

int abs(int x){return x >= 0 ? x : -x;}

void minimum(vector<int> x, vector<int> y){
	int i, j = 0, min = 999999, a, b;
	for(i = 0;i < x.size();i++){
		for(;j < y.size() && y[j] < x[i];j++){}
		if(y[j] == x[i]){
			cout << i << ' ' << j << ' ' << 0 << endl;
			return;
		}
		else if(y[j] - x[i] < min || j > 0 && x[i] - y[--j] < min){
			min = abs(y[j] - x[i]);
			a = i;
			b = j;
		}
	}
	cout << a << ' ' << b << ' ' << min << endl;
	return;
}

int main(){
	vector<int> X, Y;
	int n;
	while(cin >> n){
		if(n == 0)
			break;
		X.push_back(n);
	}
	while(cin >> n){
		if(n == 0)
			break;
		Y.push_back(n);
	}
	X.back() > Y.back() ? minimum(Y, X) : minimum(X, Y);
}

# Problem 6 (solved)
T(n) = 2T(n/2)+n-1
= 4T(n/4)+2n-(1+2)
= 8T(n/8)+3n-(1+2+4)
.
.
.
= 2^(k-1)*T(2)+(k-1)n-(2^(k-1)-1)
= cn/2+n(lgn-1)-n/2+1
= nlgn+(c/2-3/2)n+1

# Problem 7
## Solution:

#include <bits/stdc++.h>
#include <sstream>
std::vector<int> keys;
class SET{
public:
  int length;
  std::vector<int> keys;
  std::map<int, int> set;
  
  SET(){length = 0;}
  void pushme(int);
};
void SET::pushme(int el){
  keys.push_back(el);
  set[el] = el;
  length++;
}

void solution(SET mySet, int x, std::string com = "", int n = 0, int result = 0){
  std::stringstream ss;
  std::string tmp;
  for(int i=n+1;i<mySet.length+1;i++){
    ss<<mySet.keys[n];
    ss>>tmp;
    if(i<mySet.length)
      solution(mySet, x, com+tmp+" ", i, result+mySet.keys[n]);
  }
  if(result==x)
    std::cout<<result<<"\t"<<com<<"\n";
}

int main(){
  int x, tmp;
  SET mySet;

  std::cin>>x;
  while(std::cin>>tmp)
    mySet.pushme(tmp);
  
  std::cout<<"---Program run---\n";
  solution(mySet, x);
  std::cout<<"---Program end---\n";
}

## 描述拉幹:
題目：判斷可否從n個數字中找出k個數和為M
作法：從n個數中取一數稱t,再從剩下n-1個中找是否有k-1個數和為M-t,持續此動作直到k＝1,若M'=k則true else false
分析：此作法等同找出任意大小為k,和為M之組合,每個動作都找出一個樣本,則動作總數為樣本空間之大小C(n, k)=>時間複雜度為min(O(n^k), O(n^(n-k))).