# Super Junior's Club Day5 ### 📚 資料結構與演算法搭配 Leetcode - Ref：[資料結構與演算法 (JavaScript)](https://www.udemy.com/course/algorithm-data-structure/) - Ref：[LeetCode with JavaScript](https://ithelp.ithome.com.tw/users/20123681/ironman/3439?page=1) by Angelina --- # Sorting Algorithm --- ### 六種 Sorting Algorithm Bubble, Insertion, Selection, Merge, Heap, Quick --- ### Today's Topic ### Insertion Sort # 🤔 --- 1. 認識 Insertion Sort 2. 虛擬碼 3. coding 4. 時間複雜度 --- Bubble vs Insertion --- 效率比 Bubble sort 好 但理論上 O(n^2) 是一樣的 --- ### What is Insertion Sort? - 不斷插入一個新的值到一個 sorted array 中，並插入到正確位置，保持是一個 sorted array --- ### How does it work? Let me tell you # 🧙🏻‍♀️ --- ``` 有一個 array => 4, 1, 2, 5, 3, 7 第一個 element => 設定為已經被排列好的 array => 4 => length = 1 下一個 element => insert 到 array 中，並與第一個 element 比較 => 1, 4 => length = 2 下一個 element => insert 到 array 中，不斷與左邊的 element 比較 => 2 比 4 小，互換 => 1, 2, 4 => 1 比 2 小，不換 => 1, 2, 4 => length = 3 下一個 element... => insert 到 array 中，不斷與左邊的 element 比較 最後 array => 1, 2, 3, 4, 5, 7 ``` --- ### Pseudocode --- ```javascript= INSERTION-SORT(A): for j form index 1 to A.length - 1 (inclusive): key = A[j] // Now, insertion key into the sorted sequence A[0, 1, 2, ..., j-1] i = j - 1 while i >= 0 and A[i] > key: A[i+1] = A[i] i = i - 1 A[i+1] = key ``` - input A 為要排列的 array - for loop 從 index 1~length - 1，因為將 index 0 設為一個 sorted array(被排列好的陣列)，所以從 index 1 開始做 insert - 將 key insert 到 sorted array 中 - `i = j - 1` 將 i 當為 j-1 項(表示 j 的前一項) - `while i >= 0 and A[i] > key` 表示 i 的 index 要比 index -1 大，小於 key 表示不斷與左邊的值比較，當左邊的值比較大，就需要交換位置 - `A[i+1] = A[i]` 表示將 i 的值往右丟 - `i = i - 1` 表示不斷執行 while loop，符合條件就會一直往右移，不斷移出一個新的格子 - `A[i+1] = key` while loop 執行完後，多出來的新格子，就把 key 丟進去 --- Let's coding! # 🔥 --- ```javascript= let unsorted = [14, -4, 17, 6, 22, 1, -5] function insertionSort(arr) { for (let j = 1; j <= arr.length - 1; j++) { let key = arr[j] i = j - 1 while (i >= 0 && arr[i] > key) { arr[i + 1] = arr[i] i -= 1 } arr[i+1] = key // console.log(arr) } console.log(arr) } insertionSort(unsorted) ``` --- ### 時間複雜度 # ❓ --- - Worst Case Performance： O(n^2) ⇒ 要排由小到大，但拿到一個由大到小的陣列 - Best Case Performance： O(n) => 要排由小到大，本身已經接近排好的狀態 - Average Performance： O(n^2) => 外層一個 for loop，內從一個 while loop --- ### 計算 Worst Case 時間複雜度 - array = [n, n-1, n-2, ..., 3, 2, 1, 0] - 對於 n-1 而言，與 n 交換 1 次 - 對於 n-2 而言，與 n 交換 2 次 - 對於最後一個 1 而言，總共交換了 n 次 ``` 計算 1+2+3+...+n = n(n-1)/2 = (n^2)/2 - n/2 轉換 Big O 1. Small Terms don't matter => n/2 去掉 2. Constant doesn't matter => 1/2 去掉 => O(n^2) ``` --- ### 計算 Best Case 時間複雜度 ``` array = [0, 1, 2, 6, 9, 17] 1 => 不需要換 2 => 不需要換 ... 要檢查 n-1 個 elements 後 才能確認已經被排好 所以時間複雜度為 n-1 轉換 Big O Small Terms don't matter => -1 去掉 => O(n) ``` --- ### 最後進入 Leetcode 拉 # 💯 --- ### Today's Topic ### [48. rotate-image](https://leetcode.com/problems/rotate-image/) # 🤔 --- 輸入一個 n * n 大小陣列 matrix，將陣列向右90度旋轉 You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise). You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.   Constraints: - matrix.length == n - matrix[i].length == n - 1 <= n <= 20 - -1000 <= matrix[i][j] <= 1000 --- ### 解法 - matrix[i][j] => matrix[j][i] - reverse each row --- ```javascript= function rotate(matrix) { for (let i = 0; i < matrix.length; i++) { for (let j = i; j < matrix.length; j++) { let temp = matrix[i][j] matrix[i][j] = matrix[j][i] matrix[j][i] = temp } } for (let i = 0; i < n; i++) { matrix[i].reverse() } console.log(matrix) } rotate([[1,2,3],[4,5,6],[7,8,9]]) ``` --- 時間複雜度為 n^2+n => O(n^2) 優化方向 O(1) >> [[解題] LeetCode - 48 Rotate Image](http://glj8989332.blogspot.com/2019/09/leetcode-48-rotate-image.html) --- 安安教室 感謝您的收看 下回再見 👋🏻