owned this note
owned this note
Published
Linked with GitHub
---
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/)
Google Drive
Gist
Clipboard
Sign in with Wallet
