Học DSA có chán không? Hãy thử DSA View View 👀👀 — Two Sum, Binary Search và Bubble Sort
Hoi hoi!
Mình là @nyaomaru, một frontend engineer không thích những nơi quá đông người, nên mình đang lên kế hoạch cho một kỳ nghỉ yên tĩnh vào tháng 9. 🏝️
Bạn đã thử DSA View View chưa? 👀👀
https://dev.to/nyaomaru/i-built-a-tool-to-visualize-dsa-lets-learn-together-dsa-view-view--djo
DSA View View giúp chúng ta hiểu DSA bằng cách trực quan hóa cách implementation thực sự chạy ở runtime.
Nhưng chỉ giới thiệu tool thôi thì chưa đủ.
Nó có thực sự giúp chúng ta hiểu DSA không?
Hãy thử xem!
Trong bài viết này, chúng ta sẽ cùng xem ba bài toán kinh điển:
- Two Sum
- Binary Search (Tìm kiếm nhị phân)
- Bubble Sort (Sắp xếp nổi bọt)
Đầu tiên, chúng ta sẽ hiểu algorithm hoạt động như thế nào, sau đó dùng DSA View View để xem điều gì thực sự xảy ra trong runtime.
Mình cũng vẫn đang học DSA, nên cùng học với nhau nhé! 😸
🗺️ Two Sum
Hãy bắt đầu với một bài toán rất nổi tiếng.
Cho một array các số và một giá trị target, chúng ta cần tìm index của hai số có tổng bằng target.
Ví dụ:
nums = [2, 7, 11, 15];
target = 9;
Kết quả là:
[0, 1];
Vì:
2 + 7 = 9
Đơn giản!
Vậy làm thế nào để tìm được hai số này? 🤔
Brute Force
Cách đơn giản nhất có lẽ là kiểm tra tất cả các cặp có thể.
function twoSum(nums: number[], target: number): number[] {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] === target) {
return [i, j];
}
}
}
return [];
}
Cách này hoạt động.
Nhưng nếu array trở nên lớn, chúng ta có thể phải so sánh rất nhiều cặp, đúng không?
Time complexity là:
O(n²)
Liệu có cách nào tránh việc kiểm tra lại những giá trị mà chúng ta đã thấy không?
Có.
Hãy dùng Map.
function twoSum(nums: number[], target: number): number[] {
const seen = new Map<number, number>();
for (let i = 0; i < nums.length; i++) {
const current = nums[i];
const need = target - current;
if (seen.has(need)) {
return [seen.get(need)!, i];
}
seen.set(current, i);
}
return [];
}
Phần quan trọng là dòng này 👇
const need = target - current;
Thay vì hỏi:
Hai số nào cần được ghép với nhau?
chúng ta hỏi:
Mình còn cần số nào để đạt được target?
Hãy đi theo ví dụ.
Ban đầu:
current = 2
target = 9
need = 9 - 2
= 7
Chúng ta đã thấy 7 chưa?
Chưa.
Vậy hãy lưu 2.
seen = {
2 → 0
}
Tiếp theo:
current = 7
target = 9
need = 9 - 7
= 2
Chúng ta đã thấy 2 chưa?
Rồi! 👀👀
seen = {
2 → 0
}
Vậy:
return [0, 1];
Xong!
Vì chúng ta chỉ cần đi qua array một lần:
Time: O(n)
Space: O(n)
👀 Hãy View View nó
Implementation khá ngắn.
Nhưng khi mình mới học pattern này, đoạn sau vẫn có cảm giác hơi "ma thuật":
if (seen.has(need))
needđến từ đâu?- Hiện tại
seenchứa những gì? - Tại sao kiểm tra các giá trị đã xuất hiện lại giải được bài toán?
Đây chính là lúc visualization trở nên hữu ích.
Với DSA View View, chúng ta có thể đi qua runtime từng step một và quan sát các giá trị thay đổi.
2
↓
Need 7
↓
Remember 2
↓
7
↓
Need 2
↓
Found 2!
🎉
Bây giờ Map không còn giống một trick bí ẩn nữa.
Chúng ta thực sự có thể theo dõi ý tưởng:
Ghi nhớ những gì đã thấy, rồi kiểm tra xem giá trị mình cần có ở đó không.
Nice! 😸
🔍 Binary Search (Tìm kiếm nhị phân)
Tiếp theo là Binary Search.
Giả sử chúng ta có array đã được sắp xếp:
[1, 3, 5, 7, 9, 11, 13]
Và muốn tìm:
11
Tất nhiên, chúng ta có thể bắt đầu từ 1 và kiểm tra từng số.
1 → 3 → 5 → 7 → 9 → 11
Cách đó hoạt động.
Nhưng Binary Search thông minh hơn một chút.
Thay vì bắt đầu từ đầu, nó kiểm tra phần tử ở giữa.
[1, 3, 5, 7, 9, 11, 13]
↑
mid
Giá trị ở giữa là 7.
Chúng ta đang tìm 11.
11 > 7
Vì array đã được sắp xếp, chúng ta biết ngay một điều rất hữu ích.
Tất cả các giá trị ở bên trái 7 cũng nhỏ hơn 11.
Vậy chúng ta có thể bỏ cả nửa đó đi. 👋
[1, 3, 5, 7, 9, 11, 13]
└───────┘
search
Bây giờ kiểm tra phần tử giữa của range còn lại.
[9, 11, 13]
↑
mid
Và:
11 === 11
Tìm thấy rồi! 🎉
Đây là implementation:
function binarySearch(nums: number[], target: number): number {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] === target) {
return mid;
}
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
Có ba biến quan trọng:
left
right
mid
Chúng đại diện cho search range hiện tại.
Trong ví dụ của chúng ta, ban đầu:
left = 0
right = 6
mid = 3
[1, 3, 5, 7, 9, 11, 13]
↑ ↑ ↑
left mid right
Vì:
nums[mid] < target;
chúng ta di chuyển left.
left = mid + 1;
Bây giờ:
[1, 3, 5, 7, 9, 11, 13]
↑ ↑ ↑
left mid right
Và chúng ta tìm thấy 11.
Tại sao Binary Search lại nhanh?
Đây là phần thú vị.
Ở mỗi step, chúng ta loại bỏ khoảng một nửa số candidate còn lại.
Nếu có 1.000 giá trị, chúng ta không nhất thiết phải kiểm tra 1.000 lần.
Nó sẽ trông gần giống thế này:
1000
↓
500
↓
250
↓
125
↓
...
Vì vậy Binary Search có:
Time: O(log n)
Space: O(1)
Nhưng có một điều kiện rất quan trọng:
Dữ liệu phải được sắp xếp.
Nếu dữ liệu không được sắp xếp, chúng ta không thể an toàn loại bỏ một nửa search range.
👀 Hãy View View nó
Binary Search là một trong những algorithm khiến mình muốn có một visualization tool ngay từ đầu.
Code khá ngắn:
left = mid + 1;
hoặc:
right = mid - 1;
Easy.
Nhưng khi mới học, đôi khi mình vẫn nghĩ:
Khoan đã... bây giờ chúng ta đang tìm ở phần nào vậy? 😿
Khi trực quan hóa left, mid và right, ý tưởng trở nên dễ theo dõi hơn rất nhiều.
Chúng ta không thay đổi ba con số một cách ngẫu nhiên.
Chúng ta đang liên tục thu nhỏ search range.
███████████████
↓
███████
↓
███
↓
█
Đó là Binary Search!
Cắt bỏ một nửa không cần thiết.
Sau đó cắt tiếp.
Và tiếp.
Và tiếp.
Cho đến khi tìm thấy câu trả lời. ✂️😸
🫧 Bubble Sort (Sắp xếp nổi bọt)
Cuối cùng, hãy sort một thứ gì đó!
Xem array này:
[5, 1, 4, 2, 8];
Chúng ta muốn:
[1, 2, 4, 5, 8];
Bubble Sort liên tục so sánh hai giá trị liền kề.
Nếu chúng sai thứ tự, chúng ta swap chúng.
Hãy xem bước đầu tiên.
[5, 1, 4, 2, 8]
↑ ↑
So sánh:
5 > 1
Vậy swap.
[1, 5, 4, 2, 8]
Tiếp theo:
[1, 5, 4, 2, 8]
↑ ↑
Lại so sánh:
5 > 4
Swap!
[1, 4, 5, 2, 8]
Tiếp tục.
[1, 4, 5, 2, 8]
↑ ↑
5 > 2
Swap!
[1, 4, 2, 5, 8]
Dần dần, những giá trị lớn hơn sẽ di chuyển về cuối array.
Chúng giống như...
những bong bóng nổi lên. 🫧
Đó là lý do nó được gọi là Bubble Sort.
Đây là một implementation đơn giản:
function bubbleSort(nums: number[]): number[] {
for (let i = 0; i < nums.length - 1; i++) {
for (let j = 0; j < nums.length - i - 1; j++) {
if (nums[j] > nums[j + 1]) {
[nums[j], nums[j + 1]] = [nums[j + 1], nums[j]];
}
}
}
return nums;
}
Chúng ta liên tục so sánh:
nums[j];
và:
nums[j + 1];
rồi swap nếu cần.
Sau một pass hoàn chỉnh, giá trị lớn nhất còn lại sẽ tới đúng vị trí của nó gần cuối array.
Vì vậy trong pass tiếp theo, chúng ta không cần kiểm tra vị trí đó nữa.
Đó là lý do inner loop có:
nums.length - i - 1;
Complexity
Bubble Sort không nhanh với array lớn.
Complexity của nó là:
Time: O(n²)
Space: O(1)
Vì vậy ngày mai mình chắc cũng không thay toàn bộ sorting trong production bằng Bubble Sort đâu. 😸
Nhưng với tư cách là một algorithm để học, mình rất thích nó.
Tại sao?
Vì chúng ta có thể nhìn thấy algorithm đang hoạt động.
👀 Hãy View View nó
Có lẽ đây là bài thỏa mãn nhất về mặt visualization trong ba bài.
Thay vì chỉ đọc:
[nums[j], nums[j + 1]] = [nums[j + 1], nums[j]];
chúng ta có thể theo dõi các giá trị di chuyển trong array.
[5, 1, 4, 2, 8]
↓ swap
[1, 5, 4, 2, 8]
↓ swap
[1, 4, 5, 2, 8]
↓ swap
[1, 4, 2, 5, 8]
Sau đó một pass mới bắt đầu.
Code có nested loops, index, comparison và swap.
Nhưng về mặt trực quan, rule cơ bản cực kỳ đơn giản:
So sánh hai phần tử liền kề. Nếu bên trái lớn hơn, swap chúng.
Lặp lại.
Lặp lại.
Lặp lại.
Sorted! 🎉
🧠 Chúng ta thực sự học được gì?
Ba bài toán này trông rất khác nhau.
Nhưng mỗi bài giới thiệu một cách suy nghĩ hữu ích.
Two Sum
Ghi nhớ thông tin từ những step trước.
Mình đã thấy giá trị mình cần chưa?
Binary Search
Dùng những gì đã biết để loại bỏ các candidate không thể là đáp án.
Mình có thể an toàn bỏ đi một nửa search space không?
Bubble Sort
Chia một vấn đề lớn thành nhiều comparison nhỏ.
Hai giá trị này đã đúng thứ tự chưa?
Đây là một trong những điều mình thấy thú vị khi học DSA.
Ban đầu, implementation có thể trông chỉ như một đống index, loop, condition và variable khó hiểu.
Nhưng phía sau code thường là một ý tưởng đơn giản hơn nhiều.
Và đôi khi, chỉ nhìn code thôi thì mình vẫn chưa thực sự hiểu được ý tưởng đó.
Mình muốn nhìn thấy nó. 👀👀
🎯 Kết luận
Trong bài viết này, chúng ta đã xem ba algorithm kinh điển:
- Two Sum với
Map - Binary Search
- Bubble Sort
Và quan trọng hơn, chúng ta đã xem data thay đổi như thế nào trong khi code chạy.
Mình nghĩ đây chính là nơi visualization đặc biệt hữu ích.
- Đọc implementation cuối cùng cho chúng ta biết code là gì.
- Đi qua runtime step-by-step giúp chúng ta hiểu tại sao nó hoạt động.
Đó chính là lý do mình tạo ra DSA View View.
https://dsa-view-view.vercel.app
Bạn có thể viết hoặc load một TypeScript implementation, chạy nó với input của riêng mình, rồi di chuyển tiến hoặc lùi trong runtime.
Nếu bạn cũng đang học DSA, hãy thử lấy một bài mà bạn đã giải rồi và visualization nó từng step một.
Có thể bạn sẽ nhận ra điều gì đó mà trước đây chỉ đọc code thì chưa thấy. 👀
Và nếu có DSA problem nào bạn muốn mình viết trong bài tiếp theo, hãy nói với mình ở phần comment nhé!
Mình vẫn còn rất nhiều algorithm phải học. 😸
Cùng luyện cơ DSA nào! 💪
Nếu bạn thích DSA View View, hãy cho repo một star ⭐
https://github.com/nyaomaru/dsa-view-view
Hẹn gặp lại ở bài tiếp theo!
Bài viết gốc:
https://dev.to/nyaomaru/is-learning-dsa-boring-lets-use-dsa-view-view-two-sum-binary-search-and-bubble-sort-374o
All rights reserved
