# Super Junior's Club Day1 ### 📚 資料結構與演算法搭配 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 --- ## Why # 🤔 --- 在電腦科學中，排列演算法是最基本的 但在許多語言中有內建的 sorting function 那幹嘛還要學？ --- 這堂課教你 這些 sorting 是如何運作的 怎麼寫出可以排列 array 的演算法 --- 以六種 Sorting Algorithm 帶你認識演算法 (Bubble, Insertion, Selection, Merge, Heap, Quick) --- 有些時間複雜度較差，有些較好 但在不同的情況下，是無法透過時間複雜度衡量的 --- ## Are you ready? # 😆 --- ### Today's Topic ### Bubble Sort # 🤔 --- 1. 認識 Bubble Sort 2. 虛擬碼 3. coding 4. 時間複雜度 5. 優化 --- ### What is Bubble Sort? - 比較相鄰的元素，如果順序不對，會互換位置 - 因為太簡單，所以現實中幾乎沒有被運用，許多近代的程式語言中，內建的的排序演算法，不是用 Bubble Sort，而是用 Quick Sort 或 Merge Sort 等等，較複雜但更有效的演算法 --- ### How does it work? Let me tell you # 🧙🏻‍♀️ --- ``` 有一個 array => 4, 7, 1, 2, 5, 3 需要由小到大排列 先比較最後兩個元素 => 5, 3 => 互換 => 4, 7, 1, 2, 3, 5 檢查下兩個元素 2, 3 => 不用對調 檢查下兩個元素 1, 2 => 不用對調 檢查下兩個元素 7, 1 => 互換 => 4, 1, 7, 2, 3, 5 檢查下兩個元素 4, 1 => 互換 => 1, 4, 7, 2, 3, 5 => 1 做標記，不再移動 array => 1, 4, 7, 2, 3, 5 比較最後兩個元素 3, 5 => 不用對調 檢查下兩個元素 2, 3 => 不用對調 檢查下兩個元素 7, 2 => 互換 => 1, 4, 2, 7, 3, 5 檢查下兩個元素 4, 2 => 互換 => 1, 2, 4, 7, 3, 5 => 2 做標記，不再移動 array => 1, 2, 4, 7, 3, 5 比較最後兩個元素...重複動作 最後 array => 1, 2, 3, 4, 5, 7 ``` --- ### Pseudocode --- ```javascript= BUBBLE-SORT(A): for i from 0 to A.length - 2 (inclusive): for j from A.length - 1 to i + 1 (inclusive): if A[j] < A[j-1]: exchange A[j] with A[j-1] ``` - 第一個迴圈 i => sorted element - 從第一個到陣列倒數第二個 (因為最後一個已經自動被排好) - 第二個迴圈 j => adjacent elements - 從陣列最後一個往前排，排到 i+1，因為當排 i+1(j) 時，i(j-1) 已經自動被排好 --- Let's coding! # 🔥 --- ```javascript= function bubbleSort(arr) { for (let i = 0; i <= arr.length - 2; i++) { for (let j = arr.length - 1; j >= i + 1; j--) { if (arr[j] < arr[j - 1]) { let temp = arr[j] arr[j] = arr[j - 1] arr[j - 1] = temp } } } console.log(arr) } bubbleSort([4, 1, 5, 2, 7]) ``` --- ### 計算 step + 隨機陣列 --- ```javascript= function bubbleSort(arr) { let step = 0 for (let i = 0; i <= arr.length - 2; i++) { for (let j = arr.length - 1; j >= i + 1; j--) { if (arr[j] < arr[j-1]) { let temp = arr[j] arr[j] = arr[j-1] arr[j-1] = temp step++ } } } console.log(arr) console.log("It takes " + step + " steps to complete.") } let test = [] for (let i = 0; i < 100; i++) { test.push(Math.floor(Math.random() * 100)) } bubbleSort(test) ``` --- ### 時間複雜度 # ❓ --- - Worst Case Performance： O(n^2) ⇒ 要排由小到大，但拿到一個由大到小的陣列 - Best Case Performance： O(n) - Average Performance： O(n^2) ⇒ nested for loop --- ### 計算 Worst Case 時間複雜度 - array = [n, n-1, n-2, ..., 3, 2, 1] - 對於 1 而言，總共交換了 n-1 次 (先跟2交換) - 對於 2 而言，總共交換了 n-2 次 (不用跟第一個交換) - 計算 (n-1)+(n-2)+(n-3)+...+3+2+1+0 ``` 等差級數 = (首項+末項)*項數/2 (n-1)*n/2 = 1/2*n^2 - 1/2*n 轉換 Big O 1. Small Terms don't matter => 1/2*n 去掉 2. Constant doesn't matter => 1/2 去掉 => O(n^2) ``` --- ### 測試看看 ```javascript= function bubbleSort(arr) { let step = 0 for (let i = 0; i <= arr.length - 2; i++) { for (let j = arr.length - 1; j >= i + 1; j--) { if (arr[j] < arr[j-1]) { let temp = arr[j] arr[j] = arr[j-1] arr[j-1] = temp step++ } } } console.log(arr) console.log("It takes " + step + " steps to complete.") } bubbleSort([5, 4, 3, 2, 1]) // 計算 Big O // n = 5 // 1/2 * n^2 - 1/2 * n // 25/2 - 5/2 = 10 ``` --- ### Why Best Case Performance is O(n)? ### 一起優化來看看 --- - 情況：在 j 迴圈裡，可能不會做交換 - 解決：當排列已經完成，避免繼續一直排列下去，表示沒有任何的 elements 可以再被交換，就馬上把 Bubble Sort 暫停 --- ```javascript= function bubbleSort(arr) { let step = 0 for (let i = 0; i <= arr.length - 2; i++) { let swapping = false for (let j = arr.length - 1; j >= i + 1; j--) { if (arr[j] < arr[j-1]) { let temp = arr[j] arr[j] = arr[j - 1] arr[j - 1] = temp step++ swapping = true console.log(arr) } } if (swapping == false) { break } } console.log("It takes " + step + " steps to complete.") console.log(arr) } bubbleSort([1, 2, 3, 4, 0, 5, 6, 7]) // It takes 4 steps to complete. ``` --- ### 最後進入 Leetcode 拉 # 💯 --- ### Today's Topic ### [1. Two Sum](https://leetcode.com/problems/two-sum/) # 🤔 ---  ---  --- ```javascript= function twoSum(nums, target) { for(let i = 0; i < nums.length - 1; i++) { for (let j = i +1; j <= nums.length - 1; j++) { if (nums[i] + nums[j] === target) { console.log([i, j]) return [i, j] } } } } twoSum([1, 2, 5, 5, 10], 3) ``` --- 安安教室 感謝您的收看 下回再見 👋🏻