排序與搜尋

複習
常用小工具
排序
內建排序
二分搜

複習

STL

最常用

vector
set
map

某些演算法會用到(暫時先跳過)

queue
priority_queue

vector

可以把它當成 array 的用法，而且他是有序的，所以可以用 vec[i]。

push_back()









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;
}

設置大小












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;
}

pop_back()/empty()











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;
}

二維vector











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[][] 差不多

function

用 STL 傳進函式會很方便，像是 string 和 char 差別









// 可以這樣傳進來
int f (vector<int> vec, int n) {
    
}

// arr 版本
int f (int arr[], int n) {
    
}

差別？

vector 丟進去改值的話不會改變（複製一個新的）
array 會 (視為 pointer 傳入)

那要怎麼讓 vector 也可以改值？

reference

Reference 就像就像別名一樣，改個名字而已，但實際引用是同一個



int f (vector<int> &vec) {

}

fill

想把 vector 裡面設定一個數字需 O(n) 時間





// vec is a vector<int> with size n
fill(vec.begin(), vec.end(), key);

// array用法
memset(arr, key, sizeof(arr));

set

set 預設會由小排到大（同個元素只會有一個）
pair 放 set 會先排 first 再排 second
不是有序的他是一棵 tree （不支援拿取第 k 個元素）
插入 n 個元素時間複雜度 \(O(nlogn)\)
搜尋元素 (logn)

用法














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;
}

map

一個 key 對應一個 value 會根據 key 由小排到大
只會有一個 key，不會有相同的
不是有序的他是一棵 tree
插入搜尋時間複雜度和 set 一樣

用法















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;
}

find 指標

和尋找有關的指令，都會回傳一個 pointer







// 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;

清空

目前學到的STL支援 clear() 用法
注意不是把內容物設 0, 而是回到原始的空容器







mp.clear();
vec.clear();
st.clear();
// vec 需要重設大小 or push_back() insert .. 
mp[a] = b;
st.insert(c);
vec.push_back(d);

常用小工具

min/max()
swap()
__gcd()
abs()
sqrt()
ceil()/floor()/round()

min/max

兩個 val


int a = 5, b = 3;
cout << max(a,b);

多個 val


int a = 1, b = 3, c = 2, d = 4; // ...
cout << min({a,b,c,d});

swap()



int a = 3, b = 5;
swap(a,b);
cout << a << " " << b << endl;

xor寫法 (正常不會這樣寫)





int a = 3, b = 5;
a ^= b;
b ^= a;
a ^= b;
cout << a << " " << b << endl;

__gcd()

輾轉相除法的 gcd function
c++17 支援 gcd() 用法但考試沒有C++17
兩個底線 _ 和 gcd



int a = 24654;
int b = 123944;
cout << __gcd(a,b);

abs()

取絕對值






int a = 10, b = 5;
if (abs(b-a) > 5) {
    cout << "long distance" << endl;
}else{
    cout << "short distance" << endl;
}

sqrt()

開根號



// 會回傳 double，用 int 存會自動捨去小數
double c = 1234;
cout << sqrt(c) << endl;

取整

四捨五入 round()
無條件進位 ceil()
無條件捨去 floor()
注意是取整





double c = 1.23;
double d = 1.35;
cout << ceil(c); // 2
cout << floor(c); // 1
cout << round(c+d); // 3

排序演算法

選擇排序法
氣泡排序法
插入排序法
合併排序法
快速排序法

Selection Sort

反覆從未排序的資料中找出最大(小)值，與最前端尚未排序的資料交換。

截圖 2024-04-25 下午3.32.16

截圖 2024-04-25 下午3.33.08

截圖 2024-04-25 下午3.33.33

截圖 2024-04-25 下午3.33.54

實作 \(O(n^2)\)










// 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]);
    }      
}

Bubble Sort

原理是從第一筆資料開始，比較相鄰兩筆資料，如果兩筆大小順序有誤則做交換，反之則不動，接者再進行下一筆資料比較，所有資料比較完第1回合後，可以確保最後一筆資料是正確的位置。

截圖 2024-04-25 下午3.36.30

截圖 2024-04-25 下午3.36.53

截圖 2024-04-25 下午3.37.19

截圖 2024-04-25 下午3.37.57

實作 \(O(n^2)\)











// 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;
    }      
}

Insertion Sort

原理是逐一將原始資料加入已排序好資料中，並逐一與已排序好的資料作比較，找到對的位置插入。

實作 \(O(n^2)\)











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;
            } 
        }
    }
}

練習

使用以上三種其中一種試試看

H001
休息一下

Merge Sort

將資料分割成兩部分，再把分割的部分再分割成兩部分，直到每個部份都剩下2個以下，再回頭將這些部分合併。

時間複雜度 \(O(nlogn)\)

實作的部分，因為是使用分治法，所以會在分治那篇做實作，先知道原理就好，在排序的部分很少會自己刻了。

快速排序法

在混亂的資料中，快速排序是目前公認效率極佳的演算法，原理是先從原始資料列中找一個基準值(Pivot)，接著逐一將資料與基準值比較，小於基準值的資料放在左邊，大於基準值的資料放在右邊，再將兩邊區塊分別再找出基準值，重複前面的步驟，直到排序完為止。

時間複雜度 \(O(nlogn)\)

操作流程:

資料列中找出一個基準值(Pivot)
將小於Pivot的資料放在左邊，大於Pivot的資料放在右邊
左右兩邊資料分別重複1~2步驟，直到剩下1筆資料
合併

實作的部分，同樣是使用分治法，所以會在分治那篇做實作，先知道原理就好，在排序的部分很少會自己刻了。

內建排序 sort ☆☆☆☆☆

在c++ <algorithm> 裡面的函式，用法是
sort( RandomIt first, RandomIt last, Compare comp );
就是一個資料的頭，跟尾巴，以及排序方式的比較函式
同時其時間複雜度也是\(O(nlogn)\) 而且優化的最好(如果你能寫贏下個sort就是你的程式碼了)

實作

如果不寫比較函數，預設就是由小排到大




vector<int> vec = {1,3,4,2,6};
sort(vec.begin(), vec.end());
for (int i = 0 ; i < 5 ; i++) 
    cout << vec[i] << " ";

比較函數 cmp

需要定義一個 bool function
傳入兩個和排序一樣的值
回傳你想要排序的關係 (true false)

實作











// 假設要排序 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);

實作II











// 假設排序 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);

答案

先根據 first 由小到大
如果 first 一樣 second 由大排到小

練習

提示： (會用其他型態的也可以 ex: struct) 下次再教


// 存 vector<pair<string, pair<int,int>>> vec;

H002
休息一下

搜尋演算法

想要在資料裡面，找到某個值在哪

線性搜尋
二分搜尋

線性搜尋

最簡單也最爆力的方法，直接走訪每個元素，找要的值。

舉例來說，想知道班上考X分的那個人是誰。 (用pair存名字和分數)










// 假設這邊已經給好所有人的值了 first為名字，second為分數
vector<pair<string,int>> point; 
int target;
cin >> target;
for (auto it : point){
    if (it.second == target) {
        cout << it.first << '\n';
        break;
    }
}

二分搜尋

針對 "以排序好" 的資料，做二分的動作。但請不要認為這很容易，這是很多人很苦惱的地方，因為邊界的判斷以及判斷的方法其實很難掌握。

會遇到的問題?

你可能第一次看到二分，會寫出以下程式碼










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;
    }
}

會遇到的問題?

假設現在 l = 5, r = 6，而 key 的位置在 6
但是 mid = (l + r)/2 會是 5
你會發現會跑無窮迴圈

方法一

針對修改邊界做一點處理












// 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;
}

方法二












// 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;
}

方法三

有人會稱之跳跳二分搜










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;
}

時間複雜度 \(O(logn)\)

練習

H003
休息一下

內建二分搜

binary_search()：回傳是否在以排序數據中「等於」val (True or False)：


bool check = binary_search(v.begin(), v.end(), val);

lower_bound() 找出以排序數據中「大於或等於」val的「最小值」的位置：


auto it = lower_bound(v.begin(), v.end(), val);
cout << *it;

upper_bound() 找出vector中「大於」val的「最小值」的位置:


auto it = upper_bound(v.begin(), v.end(), val);
cout << *it

注意

使用lower\upper內建的話，回傳是位置，要取值記得 *
這兩個雖然也很常用，不過很多時候的二分還是要靠自己寫，所以上面的二分模板請務必記熟。

挑戰題

H004

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`	在筆記中貼入程式碼
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.