# 8/13讀書會(開發工具、資料結構)
###### tags: `面試考古題` 資料結構

### Merge sort (合併排序法)

#### 時間複雜度：
- O(n log n)，執行時間會隨著以二為底的 log n 再乘上 n 增加

#### 基本步驟：
- 拆分
1. 把大陣列切一半成為兩個小陣列
2. 把切好的兩個小陣列再各自切一半
3. 重複步驟二直到每個小陣列都只剩一個元素
- 合併
1. 排序兩個只剩一個元素的小陣列並合併
2. 把兩邊排序好的小陣列合併並排序成一個陣列
3. 重複步驟二直到所有小陣列都合併成一個大陣列



#### 時間複雜度說明
- 拆分
- 因為要把一個n的陣列拆分到每個小陣列只有一個數字，所以需要n-1個步驟
- 合併
- 在合併兩個已經排序好的小陣列時，只需要比較第一個數字，把比較小的丟進新的陣列中，再重新比較兩個小陣列，所以合併n個數字，就需要n個步驟
- 再者計算花了幾回合的合併，從一開始的7個陣列，合併完變4，再合併變2，最後合併成1個，每一回合的合併都讓下一回合少一半，所以是以2為底的log n次
- **每回合合併步驟：O(n)**
- **總花費回合數：O(log n)**

- 綜合 拆分 & 合併
- (n - 1) + (n * log n)
- 化成大 O 符號時，只計最高項係數並省略常數，因此合併排序法的時間複雜度，即為 O( n log n)

**Reference**
[JS 學資料結構與演算法 (排序篇) — 合併排序法 Merge Sort](https://oldmo860617.medium.com/js-%E5%AD%B8%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B%E8%88%87%E6%BC%94%E7%AE%97%E6%B3%95-2-%E5%90%88%E4%BD%B5%E6%8E%92%E5%BA%8F%E6%B3%95-merge-sort-cf1a8457c9e0)
[初學者學演算法｜排序法進階：合併排序法](https://medium.com/appworks-school/%E5%88%9D%E5%AD%B8%E8%80%85%E5%AD%B8%E6%BC%94%E7%AE%97%E6%B3%95-%E6%8E%92%E5%BA%8F%E6%B3%95%E9%80%B2%E9%9A%8E-%E5%90%88%E4%BD%B5%E6%8E%92%E5%BA%8F%E6%B3%95-6252651c6f7e)
[Repl](https://replit.com/@MarcoLin1/Merge-sort#index.js)

### Quick sort (快速排序)

#### 時間複雜度：
- 最好情況 O(n log n)，當所選的pivot剛好是中位數
- 最差情況 Ο(n2)，當所選的pivot每次都是最大or最小時
- 平均值 O(n log n)

#### 基本步驟：
- 從陣列中最後一個元素為基準，稱為pivot
- 目標：
- 將序列中比pivot小的放左邊
- 將序列中比pivot大的放右邊
- **調整數列(Partition)**
- 功能：將數列區分成小於pivot和大於pivot兩半
- 步驟
- front為數列最前端的index，end為數列最尾端index
- 初始化的i為 front - 1 (因為有可能所有數都比pivot大)，j為front
- 當j的數值比pivot大，就j++
- 當j的數值比pivot小，就i++，然後將i的數值和j的數值對調，再繼續j++
- 一直持續上面步驟，直到j = end 代表都比較完，然後i++，將pivot與i的數值對調，此時左邊都是比pivot小的數值，右邊都是比pivot大
- 持續重複Partition到左右數列都沒有數值或只剩一個



[Quick Sort快速排序法](http://alrightchiu.github.io/SecondRound/comparison-sort-quick-sortkuai-su-pai-xu-fa.html)
[JS 學資料結構與演算法 (排序篇)— 快速排序法 Quick Sort](https://oldmo860617.medium.com/js-%E5%AD%B8%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B%E8%88%87%E6%BC%94%E7%AE%97%E6%B3%95-1-%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E6%B3%95-quick-sort-8904e226ad5d)

### What are some advantages/disadvantages to testing your code?

測試種類：
1. 單元測試(unit testing)
- 以程式碼的最小單位進行測試，保護程式邏輯不會在維護中被破壞
3. 整合測試(integration testing)
- 整合多方資源進行測試，確保模組與模組間互動行為正確，讓不同模組各自開發維護過成中，不會因為功能調整而遭到破壞
5. 端對端測試(E2E testing)
- 從使用者角度出發，對真實系統進行測試，通常是人工測試，但也可以寫測試程式自動化

不建議寫測試的情況：
- **需求不確定**，因為當需求改變測試程式也要跟著改寫，開發成本增加
- **價值性不高**，網站價值性取決於經營者對價值的設定，因為測試需要時間，但時間就是金錢，如果沒有合理的時間寫測試，也就沒有撰寫測試的可能性

優點：
- 快速找到bug，節省開發成本
- 重構時能更快速且安全的解完成
- 確保code的品質
- 測試先行可以強迫開發者寫code前先做規劃
- 幫助開發者了解現有系統的功能
- 加快開發流程，避免開發完後還花時間修bug
- 可以記錄過程並且測試腳本可以重複使用

缺點：
- 開發者需要花更多時間寫更多複雜的code，有時候開發時程較短，就無法逐一寫測試
- 可以測試商業邏輯，但是比較難測試UI
- 測試無法抓出所有問題
- 如果程式重構的時候，大部分的testing code也要被翻新

### What is the purpose of a code style linting tool?

JavaScript是一個自由度高，但又是弱型別的語言，因此容易會有不經意的錯誤

Linting tool
- 主要目的：
- 標記語法可疑、潛在的問題語法或指令
- 開發過程中減少錯誤的產生
- 幫助團隊建議易讀性高、維護性好的coding style
- 減少針對coding style的爭論，有助於code review
- 提高coding品質

- 特色:
- 高度設定彈性，可依需求或喜好設定
- 具有擴充功能，函式庫或框架的開發者，可以依照需求再開發擴充

[What Is a Linter? Here’s a Definition and Quick-Start Guide](https://www.testim.io/blog/what-is-a-linter-heres-a-definition-and-quick-start-guide/)
[ESLint - Lint工具的後起之秀](https://ithelp.ithome.com.tw/articles/10184924)

# binary search

## 簡介

在**有序**陣列中搜尋某一特定元素(target)的演算法，永遠都從中間元素開始：

1. 若該target等於中間元素，搜尋結束
2. 若該target大於中間元素，則搜尋該陣列右半邊區塊
3. 若該target小於中間元素，則搜尋該陣列左半邊區塊

## 時間複雜度：

O(log n)

## 條件：

需要事先被排序

## 實作

[Gist實作](https://gist.github.com/tim80411/10db0011ad90dcae6f988e313ea4f0ae)

# Insertion Sort(插入排序法)

## 簡介

將第i元素放入「前i - 1張排序過」的組合，可以得到i張排序過的組合。

意思是說，如果我從第一張重新開始排序，就必定能確保排序N次後能得到長度為N的已排序組合。

2, 3, 4

- [ ] [4, 2, 3 ]

24

2,4

2,3,4

## 關鍵問題

概念知道了，但核心在於當我要插入第i元素時，要如何知道要插入到1~i-1筆資料中哪個位置呢?

- 透過一個一個比較： for loop 1~i-1，遇到大於自己的index就插入到index - 1減1的位置
- 倒過來比較，避免length增加造成的無線迴圈
- 到達index === 0的地方要判斷是大於還是小於

2,3,4

## 實作

[Gist實作](https://gist.github.com/tim80411/87446e3792e1d954b1b66a4b80ac1855)

## 時間複雜度


[http://alrightchiu.github.io/SecondRound/comparison-sort-insertion-sortcha-ru-pai-xu-fa.html](http://alrightchiu.github.io/SecondRound/comparison-sort-insertion-sortcha-ru-pai-xu-fa.html)

- best case：越接近完成排序的狀況下，時間複雜度會越接近O(N)
- worst case：如果是完全倒序的狀況下，N-1個元素都需要比較N-1次，時間複雜度是(N-1)平方：O(N$^2$)