# Super Junior's Club Day10 ### 📚 資料結構與演算法搭配 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 ### Selection Sort # 🤔 --- 1. 認識 Selection Sort 2. 虛擬碼 3. coding 4. 時間複雜度 --- ### What is Selection Sort? - 不斷地去找到最小的值，並與 unsorted array 中最左邊的值互換 --- ### How does it work? Let me tell you # 🧙🏻‍♀️ --- ``` array => 5 1 3 2 7 4 找到最小值 1 => 與陣列最左邊的值互換 => 1 5 3 2 7 4 1 不再改變 找到最小值 2 => 與陣列最左邊的值互換 => 1 2 3 5 7 4 1 2 不再改變 找到最小值 3 => 與陣列最左邊的值互換 => 位置不變 => 1 2 3 5 7 4 1 2 3 不再改變 找到最小值 4 => 與陣列最左邊的值互換 => 1 2 3 4 7 5 1 2 3 4 不再改變 找到最小值 5 => 與陣列最左邊的值互換 => 1 2 3 4 5 7 1 2 3 4 5 不再改變 最後一個值已經被排好 => 1 2 3 4 5 7 不再改變 ``` --- 進入 Pseudocode 前 先來看看如何找到最小的值 --- ### Pseudocode of Finding the Smallest Value ```javascript= SMALLEST-VALUE(A): smallest = A[0] for i from 1 to A.length - 1: if A[i] < smallest: smallest = A[i] return smallest ``` - input A 為一個 array - 假設 A[0] 為最小的，如果 A[i] 比 smallest 更小 => 就將其設為 smallest - 執行完 for loop 可以找到 array 中最小的 --- ### Pseudocode --- ```javascript= SELECTION-SORT(A): for i from 0 to A.length - 2: minIndex = i for j from i to A.length - 1: if A[j] < A[minIndex]: minIndex = j swap A[minIndex] and A[j] ``` - 當排列 A.length - 2 時，A.length - 1 已經自動被排好了，所以 for loop 只要到 A.length - 2 --- Let's coding! # 🔥 --- ```javascript= // index = 0 1 2 3 4 5 6 length = 7 let unsorted = [14, -4, 17, 6, 22, 1, -5] selectionSort(unsorted) function selectionSort(arr) { for (let i = 0; i <= arr.length - 2; i++) { let minIndex = i for (let j = i; j <= arr.length -1; j++) { // 找到最小的值 if (arr[j] < arr[minIndex]) { minIndex = j console.log('j: ' + j) } } // swap arr[minIndex] and arr[i] 與陣列最左邊的值交換 let temp = arr[minIndex] arr[minIndex] = arr[i] arr[i] = temp console.log(i, arr) } console.log(arr) return arr } ``` --- ### 時間複雜度 # ❓ --- - Worst Case Performance： O(n^2) ⇒ 要排由小到大，但拿到一個由大到小的陣列 - Best Case Performance： O(n^2) => 要排由小到大，本身已經接近排好的狀態 - Average Performance： O(n^2) => 外層一個 for loop，內層一個 for loop --- ### 計算 Worst Case 時間複雜度 - array = [n, n-1, n-2, ..., 3, 2, 1, 0] - 對於 0 而言，與 n 交換，要 n steps - 對於 1 而言，與 n-1 交換，要 n-1 steps ``` 計算 n+(n-1)+(n-2)+1+0 = 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] - 對於 0 而言，要確認是不是最小，要 n 次 - 對於 1 而言，要確認是不是最小，要 n-1 次 - O(n^2) --- ### 最後進入 Leetcode 拉 # 💯 --- ### Today's Topic ### [14. Longest Common Prefix](https://leetcode.com/problems/longest-common-prefix/) # 🤔 --- Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string "". ``` Example 1: Input: strs = ["flower","flow","flight"] Output: "fl" Example 2: Input: strs = ["dog","racecar","car"] Output: "" Explanation: There is no common prefix among the input strings. Constraints: 1 <= strs.length <= 200 0 <= strs[i].length <= 200 strs[i] consists of only lower-case English letters. ``` --- ```javascript= function longestCommonPrefix(strs) { // 處理edge case if (strs.length === 0) return ""; let ansPrefix = strs[0]; for (let i = 0; i < strs.length; i++) { while (strs[i].indexOf(ansPrefix) !== 0) { console.log('before: ' + ansPrefix) ansPrefix = ansPrefix.substring(0, ansPrefix.length - 1); console.log('after: ' + ansPrefix) if (ansPrefix === null) return ""; } } console.log(ansPrefix) return ansPrefix; }; longestCommonPrefix(["flower", "flow", "flight"]) ``` --- [MDN substring](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String/substring) [MDN indexOf](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String/indexOf) --- 安安教室 感謝您的收看 下回再見 👋🏻