--- slideOptions: transition: slide --- <!-- .slide: data-transition="fade-in convex-out" --> # ```std::sort```<br>&<br>```next_permutation``` 南天門日月卦長 --- <!-- .slide: data-transition="fade-in convex-out" --> ## 課前小提醒 * 今天要教的東西都會在```<algorithm>```標頭檔裡喔<br>記得```#include<algorithm>```！ * algorithm的中文翻譯就是演算法的意思 * 裡面有很多別人幫你寫好的演算法```template<>``` * [cplusplus Reference algorithm](http://www.cplusplus.com/reference/algorithm/) --- <!-- .slide: data-transition="fade-in convex-out" --> ## ```std::sort``` --- ## 排序好慢 還記得我們之前教的排序sort嗎？ 複雜度都是$\mathcal O(N^2)$ 但是排序目前被證明最快可以做到$\mathcal O(N log N)$ ---- ## STL可以排序嗎？ 而且我們教的排序只能用在陣列上 那STL的<br>vector、stack、queue、deque、list可以排序嗎？ ---- ## STL sort * 幸好C++ STL的開發者解決了這個問題 * 在```<algorithm>```裡面一些專門用來排序的函數 * 讓我們一起來看看這些函數吧！ --- ## ```std::sort()``` * 複雜度$\mathcal O(N log N)$ * 用template實作，不用擔心型態問題 * 使用[Introsort(introspective sort)](https://en.wikipedia.org/wiki/Introsort) * 可以使用在一般的陣列<br>或是有Random Access Iterator的STL容器 ---- ## Random Access Iterator? 初學者可以理解成： 有Random Access Iterator的STL容器 都有類似陣列的功能 * 以下為目前教過有Random Access Iterator的容器 * std::vector * std::deque ---- ## sort使用方法(STL容器) ```sort(起始iterator, 結尾iterator);``` ```cpp= std::vector<int> s; for(int i=0;i<10;++i){ s.push_back(rand());//隨機產生元素 } std::sort(s.begin(), s.end());//由小排到大 for(int e:s) std::cout << e << '\n'; ``` ---- ## sort使用方法(一般陣列) 可以把iterator想成指標 ```sort(陣列起始位置, 陣列結束位置);``` ```cpp= int s[10]; for(int i=0;i<10;++i) s[i] = rand(); std::sort(s, s+10);//由小排到大 for(int e:s) std::cout << e << '\n'; ``` --- ## compare function 1 比較函數 ---- ## 由大排到小？ 直接呼叫sort他會幫你把東西由小排到大 那如果要由大排到寫怎麼辦呢？ 難道在sort完之後再用for把陣列顛倒? ---- ## 隱藏的東西 * std::sort其實有第三個隱藏的參數 * 這個參數要填的是一個特定型態的函數！ ```cpp= bool cmp(int a,int b){ return a > b; } int main(){ vector<int> s = {7, 1, 2, 2, 9, 4, 8, 7}; sort(s.begin(), s.end(), cmp); for(int e:s) cout<<e<<endl; return 0; } ``` ---- ## 解析 * 以由大排到小為例，Type是要排序的元素型態 * 函數會回傳一個bool值： * true: ```if(a!=b)```排序後a會排在b的前面 * false: ```if(a!=b)```排序後b會排在a的前面 ```cpp= bool function_name(Type a,Type b){ return a > b; } ``` --- ## compare function 2 struct/class 也可以拿去排序喔！ ---- ## struct排序 * 給你一個struct的陣列 * 你要先依照id由小到大排序 * 如果有id相同的部分就按造val由大到小排序 ``` cpp= struct GG{ int id, val; }; vector<GG> s; ``` ---- ## 比較函數 * 原則和一般的比較函數一樣： * true: ```if(a!=b)```排序後a會排在b的前面 * false: ```if(a!=b)```排序後b會排在a的前面 ```cpp= bool cmp(const GG &a, const GG &b){ if(a.id!=b.id) return a.id < b.id; return a.val > b.val; } ``` ---- ## 更精簡的寫法 這樣寫更短且函數執行解果不會改變 ```cpp= bool cmp(const GG &a, const GG &b){ return a.id<b.id||(a.id==b.id&&a.val>b.val); } ``` --- <!-- .slide: data-transition="fade-in convex-out" --> ## std::stable_sort --- ## 穩定排序 * 如果陣列中有兩個相同的元素 * 排序的時候他們的相對位置不會改變的排序 * 就稱為穩定排序 * 剛剛教的std::sort **「不是」** 穩定排序 ---- ## std::stable_sort * STL也有內建穩定排序 * 使用[merge sort](https://en.wikipedia.org/wiki/Merge_sort) * 用法和std::sort一樣 * 也可以使用比較函數 * 以下附上幾個範例給大家參考 ---- ## 一般陣列 ```cpp= int s[]={7,1,2,2,8,9,5,6}; stable_sort(s, s+8); ``` ---- ## STL 容器 ```cpp= vector<int> s={7,1,2,2,8,9,5,6}; stable_sort(s.begin(), s.end()); ``` ---- ## 比較函數 ```cpp= struct P{ int id, val; P(int id, int val):id(id), val(val){} } bool cmp(const P &a, const P &b){ return a.id<b.id||(a.id==b.id&&a.val>b.val); } vector<P> s; int main(){ for(int i=0;i<5;++i){ int id=rand(); s.puah_back(P(id,rand())); s.puah_back(P(id,rand())); } stable_sort(s.begin(), s.end(), cmp); } ``` --- <!-- .slide: data-transition="fade-in convex-out" --> ## next_permutation 中文直接翻譯就是下一個排列 --- ## 所有排列 * 高中數學學過，$N$個東西可以有$N!$種排列 * 將所有排列按造字典順序印出來 * 你會發現第一個排列是由小排到大<br>最後一個排列是由大排到小 ---- ## 範例 * {1,2,3}的所有排列(依字典順序排)： 1. {1, 2, 3} 2. {1, 3, 2} 3. {2, 1, 3} 4. {2, 3, 1} 5. {3, 1, 2} 6. {3, 2, 1} ---- ## 下一個排列 * 我們說某個排列$P$的下一個排列 * 指的是將所有排列依字典順序排之後 * 編號為$P$的編號+1的那個排列 * 例如{1, 3, 2}的下一個排列就是{2, 1, 3} --- ## 產生下一個排列 * [Next lexicographical permutation algorithm](https://www.nayuki.io/page/next-lexicographical-permutation-algorithm) * C++ STL已經幫你寫好了，只要會用就行了 ---- ## std::next_permutation * 傳入的參數和sort一樣 * 他會還傳一個bool<br>如果是true表示現在這個排列不是最後一個排列 ```cpp= int s[] = {1, 3, 2}; bool end = next_permutation(s, s+3); cout<<end<<'\n'; for(int i=0;i<3;++i) cout<<s[i]<<' '; ``` ---- ## STL 容器也可以用 ```cpp= vector<int> s = {1, 3, 2}; bool end = next_permutation(s.begin(), s.end()); cout<<end<<'\n'; for(int i=0;i<3;++i) cout<<s[i]<<' '; ``` ---- ## 產生所有排列 * 只要給出第一個排列 * 不斷呼叫next_permutation * 直到回傳值變成false就行了 ```cpp= int s[]={1,2,3}; do{ for(int i=0;i<3;++i){ if(i) cout<<' '; cout<<s[i]; } cout<<'\n'; }while(next_permutation(s, s+3)); ``` ---- ## 比較函數 next_permutation也可以用比較函數喔！ 程式碼已經重複出現很多次了我就不放了 --- ## 題目練習 [文字轉轉轉](https://neoj.sprout.tw/problem/153/)