Pseudo-code Drills: Sorting & Searching

92%

Quảng cáo • Advertisement

📢 Sponsor Ad

Google AdSense

🎯 Vua của các thuật toán

1. Binary Search (Tìm kiếm nhị phân)


function binary_search(arr, target):
    low = 0, high = len(arr) - 1
    while low <= high:
        mid = (low + high) / 2
        if arr[mid] == target: return mid
        else if arr[mid] < target: low = mid + 1
        else: high = mid - 1
    return -1

Lưu ý: Mảng PHẢI được sắp xếp trước thì mới dùng được Binary Search.

2. Bubble Sort (Nổi bọt)

Thuật toán kinh điển hay hỏi trong đề thi.

for i from 0 to N-2:
    for j from N-1 down to i+1:
        if arr[j] < arr[j-1]:
            swap(arr[j], arr[j-1])

Để ý chiều vòng lặp: Có thể chạy từ dưới lên hoặc trên xuống. Kết quả vẫn là đẩy thằng nhỏ nhất/lớn nhất về đúng chỗ.

🆚 Bảng so sánh nhanh:

Thuật toán	Best case	Worst case	Dùng khi nào?
Bubble/Insert/Select	O(n)	O(n^2)	Mảng cực nhỏ (< 50 phần tử).
Quick Sort	O(n log n)	O(n^2)	Nhanh nhất thực tế. Dùng mặc định.
Merge Sort	O(n log n)	O(n log n)	Cần ổn định (Stable). Tốn RAM.

3. Merge Sort (Sắp xếp trộn) - Chia để trị

Quy trình:

Chia mảng làm đôi cho đến khi mỗi mảng chỉ còn 1 phần tử.
Trộn (Merge) các mảng con lại theo thứ tự tăng dần.

graph TD A[38, 27, 43, 3] --> B[38, 27] A --> C[43, 3] B --> D[38] B --> E[27] C --> F[43] C --> G[3] D & E --> H[27, 38] F & G --> I[3, 43] H & I --> J[3, 27, 38, 43]

📝 Luyện tập Part B (Exam Drills):

Câu hỏi: Thuật toán sắp xếp nào có hiệu năng kém nhất (O(n^2)) khi mảng đã gần như sắp xếp xong?
Đáp án
Bubble Sort và Selection Sort. (Quick Sort cũng có thể rơi vào O(n^2) nếu chọn pivot tệ).
Câu hỏi: Trong Binary Search, mảng có 1000 phần tử thì tối đa mất bao nhiêu lần so sánh để tìm thấy target?
Đáp án
10 lần. ($2^{10} = 1024 > 1000$).

4. Mảng 2 chiều (Matrix)

Duyệt mảng 2 chiều là kỹ năng bắt buộc. (Ảnh số thực chất là ma trận pixel).


// Tính tổng đường chéo chính (i == j)
sum = 0
for i from 0 to N-1:
    sum = sum + A[i][i]

// Xoay ảnh 90 độ (Khó)
// 1. Transpose (Đổi hàng thành cột: A[i][j] <-> A[j][i])
// 2. Reverse từng hàng

DAY 92🇯🇵 整列・探索アルゴリズム