{%hackmd @hipp0\Hippotumuxthem %} <style> .text-center{ text-align: center; //文字置中 } .text-left{ text-align: left; //文字靠左 } .text-right{ text-align: right; //文字靠右 } </style> <style> .reveal .slides { text-align: left; font-size:30px; } </style> # 排序與搜尋 --- # 排序與搜尋 - 複習 - 常用小工具 - 排序 - 內建排序 - 二分搜 --- <h2 style='color:#C4C400'> 複習 </h2> ---- <h2 style='color:#C4C400'> STL </h2> 最常用 - vector - set - map 某些演算法會用到(暫時先跳過) - queue - priority_queue ---- <h3 style='color:#C4C400'> vector </h3> 可以把它當成 array 的用法，而且他是有序的，所以可以用 vec\[i]。 ---- <h3 style='color:#C4C400'> push_back() </h3> ```cpp= vector<int> vec; int n = 5; for (int i = 0 ; i < 5 ; i++) { vec.push_back(i); } // 之後就可以當 arr for (int i = 0 ; i < 5 ; i++) { cout << vec[i] << endl; } ``` ---- <h3 style='color:#C4C400'> 設置大小 </h3> ```cpp= int n = 5; vector<int> vec(n); // or vec.resize(n); // 直接預設大小為 n for (int i = 0 ; i < 5 ; i++) { vec[i] = i; } for (int i = 0 ; i < 5 ; i++) { cout << vec[i] << endl; } ``` ---- <h3 style='color:#C4C400'> pop_back()/empty() </h3> ```cpp= vector<int> vec; int n = 5; for (int i = 0 ; i < 5 ; i++) { vec.push_back(i); } for (int i = 0 ; i < 5 ; i++) { vec.pop_back(); } if (vec.empty()) { cout << "yes" << endl; } ``` ---- <h3 style='color:#C4C400'> 二維vector </h3> ```cpp= int n = 5, m = 6; // int arr[n][m] vector<vector<int>> vec2(n, vector<int>(m)); // or vector<vector<int>> vec2; vec2.resize(n); for (int i = 0.; i < n ; i++) vec2[i].resize(m); // 之後用法跟 arr[][] 差不多 ``` ---- <h3 style='color:#C4C400'> function </h3> 用 STL 傳進函式會很方便，像是 string 和 char 差別 ```cpp= // 可以這樣傳進來 int f (vector<int> vec, int n) { } // arr 版本 int f (int arr[], int n) { } ``` ---- <h3 style='color:#C4C400'> 差別？ </h3> - vector 丟進去改值的話不會改變 （複製一個新的） - array 會 (視為 pointer 傳入) 那要怎麼讓 vector 也可以改值？ ---- <h3 style='color:#C4C400'> reference </h3> Reference 就像就像別名一樣，改個名字而已，但實際引用是同一個 ```cpp= int f (vector<int> &vec) { } ``` ---- <h3 style='color:#C4C400'> fill </h3> 想把 vector 裡面設定一個數字 需 O(n) 時間 ```cpp= // vec is a vector<int> with size n fill(vec.begin(), vec.end(), key); // array用法 memset(arr, key, sizeof(arr)); ``` ---- <h3 style='color:#C4C400'> set </h3> - set 預設會由小排到大 （同個元素只會有一個） - pair 放 set 會先排 first 再排 second - 不是有序的 他是一棵 tree （不支援拿取第 k 個元素） - 插入 n 個元素時間複雜度 $O(nlogn)$ - 搜尋元素 (logn) ---- <h3 style='color:#C4C400'> 用法 </h3> ```cpp= set<int> st; for (int i = 5 ; i >= 0 ; i--) { st.insert(i); } st.erase(4); int key = 4; if (st.find(key) != st.end()) cout << "find it" << endl; else cout << "not find" << endl; for (auto it : st) { cout << it << endl; } ``` ---- <h3 style='color:#C4C400'> map </h3> - 一個 key 對應一個 value 會根據 key 由小排到大 - 只會有一個 key，不會有相同的 - 不是有序的 他是一棵 tree - 插入搜尋時間複雜度和 set 一樣 ---- <h3 style='color:#C4C400'> 用法 </h3> ```cpp= map<string, int> mp; for (int i = 5 ; i >= 0 ; i--) { string s; int val; cin >> s >> val; mp[s] = val; } if (st.find(key) != st.end()) cout << "find it" << endl; else cout << "not find" << endl; for (auto it : st) { cout << it.first << it.second << endl; } ``` ---- <h3 style='color:#C4C400'> find 指標 </h3> 和尋找有關的指令，都會回傳一個 pointer ```cpp= // mp is map<string, int> // st is set<int> auto ind = mp.find(key); cout << (*)ind.first << (*)ind.second << endl; auto ind2 = st.find(val); cout << (*)ind2 << endl; ``` ---- <h3 style='color:#C4C400'> 清空 </h3> 目前學到的STL支援 clear() 用法 注意不是把內容物設 0, 而是回到原始的空容器 ```cpp= mp.clear(); vec.clear(); st.clear(); // vec 需要重設大小 or push_back() insert .. mp[a] = b; st.insert(c); vec.push_back(d); ``` --- <h2 style='color:#C4C400'> 常用小工具 </h2> - min/max() - swap() - __gcd() - abs() - sqrt() - ceil()/floor()/round() ---- <h3 style='color:#C4C400'> min/max </h3> - 兩個 val ```cpp= int a = 5, b = 3; cout << max(a,b); ``` - 多個 val ```cpp= int a = 1, b = 3, c = 2, d = 4; // ... cout << min({a,b,c,d}); ``` ---- <h3 style='color:#C4C400'> swap() </h3> ```cpp= int a = 3, b = 5; swap(a,b); cout << a << " " << b << endl; ``` - xor寫法 (正常不會這樣寫) ```cpp= int a = 3, b = 5; a ^= b; b ^= a; a ^= b; cout << a << " " << b << endl; ``` ---- <h3 style='color:#C4C400'> __gcd() </h3> - 輾轉相除法的 gcd function - c\+\+17 支援 gcd() 用法 但考試沒有C\+\+17 - 兩個底線 _ 和 gcd ```cpp= int a = 24654; int b = 123944; cout << __gcd(a,b); ``` ---- <h3 style='color:#C4C400'> abs() </h3> - 取絕對值 ```cpp= int a = 10, b = 5; if (abs(b-a) > 5) { cout << "long distance" << endl; }else{ cout << "short distance" << endl; } ``` ---- <h3 style='color:#C4C400'> sqrt() </h3> - 開根號 ```cpp= // 會回傳 double，用 int 存會自動捨去小數 double c = 1234; cout << sqrt(c) << endl; ``` ---- <h3 style='color:#C4C400'> 取整 </h3> - 四捨五入 round() - 無條件進位 ceil() - 無條件捨去 floor() - 注意是取整 ```cpp= double c = 1.23; double d = 1.35; cout << ceil(c); // 2 cout << floor(c); // 1 cout << round(c+d); // 3 ``` --- <h2 style='color:#C4C400'> 排序演算法 </h2> - 選擇排序法 - 氣泡排序法 - 插入排序法 - 合併排序法 - 快速排序法 ---- <h3 style='color:#C4C400'> Selection Sort </h3> 反覆從未排序的資料中找出最大(小)值，與最前端尚未排序的資料交換。 ----  ----  ----  ----  ---- ### <h3 style='color:#C4C400'> 實作 $O(n^2)$ </h3> ```cpp= // remember using reference void solection_sort (vector<int> &arr, int n){ for (int i = 0 ; i < n ; i++) { int mn = i; for (int j = i + 1 ; j < n ; j++) { if (arr[j] < arr[mn]) mn = j; } swap(arr[i],arr[mn]); } } ``` ---- <h3 style='color:#C4C400'> Bubble Sort </h3> 原理是從第一筆資料開始，比較相鄰兩筆資料，如果兩筆大小順序有誤則做交換，反之則不動，接者再進行下一筆資料比較，所有資料比較完第1回合後，可以確保最後一筆資料是正確的位置。 ----  ----  ----  ----  ---- ### <h3 style='color:#C4C400'> 實作 $O(n^2)$ </h3> ```cpp= // remember using reference void bubble_sort (vector<int> &arr, int n) { while (n--) { bool check = false; for (int i = 0 ; i < n ; i++) { if (arr[i] > arr[i+1]) swap(arr[i],arr[i+1]), check = true; } if (!check) break; } } ``` ---- <h3 style='color:#C4C400'> Insertion Sort </h3> 原理是逐一將原始資料加入已排序好資料中，並逐一與已排序好的資料作比較，找到對的位置插入。 ----  ----   ----   ----   ----   ---- ### <h3 style='color:#C4C400'> 實作 $O(n^2)$ </h3> ```cpp= void insert_sort (vector<int> &arr, int n) { for (int i = 1 ; i < n ; i++) { int target = i; for (int j = i-1 ; j >= 0 ; j--) { if (arr[target] < arr[j]) { swap(arr[target],arr[j]); target = j; } } } } ``` ---- <h3 style='color:#C4C400'> 練習 </h3> 使用以上三種其中一種試試看 - H001 - 休息一下 ---- <h3 style='color:#C4C400'> Merge Sort </h3> 將資料分割成兩部分，再把分割的部分再分割成兩部分，直到每個部份都剩下2個以下，再回頭將這些部分合併。 ### 時間複雜度 $O(nlogn)$ ----  ---- 實作的部分，因為是使用分治法，所以會在分治那篇做實作，先知道原理就好，在排序的部分很少會自己刻了。 ---- <h3 style='color:#C4C400'> 快速排序法 </h3> 在混亂的資料中，快速排序是目前公認效率極佳的演算法，原理是先從原始資料列中找一個基準值(Pivot)，接著逐一將資料與基準值比較，小於基準值的資料放在左邊，大於基準值的資料放在右邊，再將兩邊區塊分別再找出基準值，重複前面的步驟，直到排序完為止。 ### 時間複雜度 $O(nlogn)$ ---- 操作流程: 1. 資料列中找出一個基準值(Pivot) 2. 將小於Pivot的資料放在左邊，大於Pivot的資料放在右邊 3. 左右兩邊資料分別重複1~2步驟，直到剩下1筆資料 4. 合併 ----  ---- 實作的部分，同樣是使用分治法，所以會在分治那篇做實作，先知道原理就好，在排序的部分很少會自己刻了。 --- <h2 style='color:#C4C400'> 內建排序 sort ☆☆☆☆☆ </h2> ---- - 在c++ <algorithm\> 裡面的函式，用法是 - sort( RandomIt first, RandomIt last, Compare comp ); - 就是一個資料的頭，跟尾巴，以及排序方式的比較函式 - 同時其時間複雜度也是$O(nlogn)$ 而且優化的最好(如果你能寫贏下個sort就是你的程式碼了) ---- <h3 style='color:#C4C400'> 實作 </h3> 如果不寫比較函數，預設就是由小排到大 ```cpp= vector<int> vec = {1,3,4,2,6}; sort(vec.begin(), vec.end()); for (int i = 0 ; i < 5 ; i++) cout << vec[i] << " "; ``` ---- <h3 style='color:#C4C400'> 比較函數 cmp </h3> - 需要定義一個 bool function - 傳入兩個和排序一樣的值 - 回傳你想要排序的關係 (true false) ---- <h3 style='color:#C4C400'> 實作 </h3> ```cpp= // 假設要排序 vector<int> 要丟 int 進去 bool cmp (int a, int b) { // 把 a 看成資料前面的 // 把 b 看成資料後面的 // 所以假設回傳 a > b // 也就是說，前面資料 > 後面資料才會是 true return a > b; } // main function sort(vec.begin(), vec.end(), cmp); ``` ---- <h3 style='color:#C4C400'> 實作II </h3> ```cpp= // 假設排序 vector<pair<int,int>> vec; // 猜一下如何排序的 bool cmp (pair<int,int> a, pair<int,int> b) { if (a.first == b.first) return a.second > b.second; else return a.first < b.first; } // main function sort(vec.begin(), vec.end(), cmp); ``` ---- <h3 style='color:#C4C400'> 答案 </h3> - 先根據 first 由小到大 - 如果 first 一樣 second 由大排到小 ---- <h3 style='color:#C4C400'> 練習 </h3> 提示： (會用其他型態的也可以 ex: struct) 下次再教 ```cpp= // 存 vector<pair<string, pair<int,int>>> vec; ``` - H002 - 休息一下 --- <h2 style='color:#C4C400'> 搜尋演算法 </h2> 想要在資料裡面，找到某個值在哪 - 線性搜尋 - 二分搜尋 ---- <h3 style='color:#C4C400'> 線性搜尋 </h3> 最簡單也最爆力的方法，直接走訪每個元素，找要的值。 舉例來說，想知道班上考X分的那個人是誰。 (用pair存名字和分數) ```cpp= // 假設這邊已經給好所有人的值了 first為名字，second為分數 vector<pair<string,int>> point; int target; cin >> target; for (auto it : point){ if (it.second == target) { cout << it.first << '\n'; break; } } ``` ---- <h3 style='color:#C4C400'> 二分搜尋 </h3> 針對 "以排序好" 的資料，做二分的動作。 但請不要認為這很容易，這是很多人很苦惱的地方，因為邊界的判斷以及判斷的方法其實很難掌握。 ---- <h3 style='color:#C4C400'> 會遇到的問題? </h3> 你可能第一次看到二分，會寫出以下程式碼 ```cpp= int l = 0, r = n - 1; while (l < r) { int mid = (l + r)/2; if (vec[mid] > key) l = mid; else if (vec[mid] < key) r = mid; else { cout << mid << endl; break; } } ``` ---- <h3 style='color:#C4C400'> 會遇到的問題? </h3> - 假設現在 l = 5, r = 6，而 key 的位置在 6 - 但是 mid = (l + r)/2 會是 5 - 你會發現會跑無窮迴圈 ---- <h3 style='color:#C4C400'> 方法一 </h3> 針對修改邊界做一點處理 ```cpp= // l 是左邊界 , r 是右邊界 int BinarySearch_min(vector<int> arr,int n,int key) { int l = 0,r = n - 1; while(l < r){ int mid = (l + r)/2; if (arr[mid] < key) l = mid + 1; else r = mid; } return (l + r)/2; } ``` ---- <h3 style='color:#C4C400'> 方法二 </h3> ```cpp= // l 是左邊界 , r 是右邊界 int BinarySearch_Max(vector<int> arr,int n,int key) { int l = 0, r = n - 1; while (l < r) { int mid = (l + r + 1) / 2;//取中間靠後 if (arr[mid] <= key) l = mid; else r = mid - 1; } return (l + r + 1)/2; } ``` ---- <h3 style='color:#C4C400'> 方法三 </h3> 有人會稱之 跳跳二分搜 ```cpp= int jump_search (int a[], int n, int x) { if (a[0] >= x) return -1 ; // 檢查第一個是否已經大於X了 int ans = 0; for (int jump = n/2 ; jump > 0 ; jump /= 2) { //jump /= 2 也可以寫成 jump >>= 1 while (ans + jump < n && a[ans + jump] < X) ans += jump; } return ans; } ``` ----  ---- ### <h3 style='color:#C4C400'> 時間複雜度 $O(logn)$ </h3> ---- <h3 style='color:#C4C400'> 練習 </h3> - H003 - 休息一下 ---- <h3 style='color:#C4C400'> 內建二分搜 </h3> - binary_search()：回傳是否在以排序數據中「等於」val (True or False)： ```cpp= bool check = binary_search(v.begin(), v.end(), val); ``` - lower_bound() 找出以排序數據中「大於或等於」val的「最小值」的位置： ```cpp= auto it = lower_bound(v.begin(), v.end(), val); cout << *it; ``` - upper_bound() 找出vector中「大於」val的「最小值」的位置: ```cpp= auto it = upper_bound(v.begin(), v.end(), val); cout << *it ``` ---- <h3 style='color:#C4C400'> 注意 </h3> - 使用lower\upper內建的話，回傳是位置，要取值記得 * - 這兩個雖然也很常用，不過很多時候的二分還是要靠自己寫，所以上面的二分模板請務必記熟。 ---- <h3 style='color:#C4C400'> 挑戰題 </h3> - H004