Tài Liệu Giảng Dạy: Cấu Trúc Dữ Liệu & Giải Thuật – Chuyên Đề Các Thuật Toán Sắp Xếp

Tổng quan về giáo trình

Tài liệu bài giảng "Cấu trúc dữ liệu & Giải thuật" (Data Structures and Algorithms) do ThS. Nguyễn Trí Tuấn biên soạn tại Khoa Công nghệ Thông tin, Trường Đại học Khoa học Tự nhiên – Đại học Quốc gia TP.HCM (phiên bản cập nhật tháng 09/2013). Trong chương trình đào tạo cử nhân ngành Công nghệ Thông tin và Khoa học Máy tính, đây là học phần cơ sở ngành đóng vai trò nền tảng cho việc thiết kế, phân tích và tối ưu hóa phần mềm.

Mục tiêu học tập của chuyên đề bao gồm việc cung cấp kiến thức nền tảng về bài toán sắp xếp nội (internal sorting) trên cấu trúc mảng số nguyên, phân tích chi tiết cơ chế hoạt động của từng thuật toán, cài đặt mã nguồn bằng ngôn ngữ lập trình C/C++, và đánh giá độ phức tạp thuật toán dựa trên số phép so sánh, phép gán, phép hoán vị trong các trường hợp tốt nhất và xấu nhất.

Cấu trúc bài giảng được thiết kế theo tiến trình phát triển từ các giải thuật sơ cấp có độ phức tạp thời gian bậc hai $O(n^2)$ như Selection Sort (Sắp xếp chọn trực tiếp) và Insertion Sort (Sắp xếp chèn trực tiếp), tiến tới giải thuật cải tiến Shell Sort với việc phá vỡ rào cản $O(n^2)$, và giải thuật tối ưu $O(n \log_2 n)$ trên cấu trúc dữ liệu dạng cây như Heap Sort (Sắp xếp vun đống).

Cách tiếp cận của tài liệu nhấn mạnh vào tính trực quan hóa trạng thái dữ liệu qua từng bước lặp, phân định ranh giới giữa "phần đã sắp" và "phần chưa sắp" trên mảng, kết hợp đối sánh lý thuyết toán học với hiện thực hóa mã nguồn thực tế.

Nội dung kiến thức cốt lõi

Các chương và chủ đề chính

Nội dung bài giảng được cấu trúc thành các phần rõ ràng, phát triển từ cơ bản đến chuyên sâu:

                  ┌────────────────────────────────────────────────────────┐
                  │ BÀI TOÁN SẮP XẾP MẢNG SỐ NGUYÊN TĂNG DẦN                │
                  └──────────────────────────┬─────────────────────────────┘
                                             │
             ┌───────────────────────────────┴──────────────────────────────┐
             ▼                                                              ▼
┌───────────────────────────┐                                 ┌───────────────────────────┐
│ CÁC THUẬT TOÁN SƠ CẤP     │                                 │ CÁC THUẬT TOÁN CẢI TIẾN   │
│ Độ phức tạp O(n²)         │                                 │ Độ phức tạp < O(n²)       │
└────────────┬──────────────┘                                 └─────────────┬─────────────┘
             │                                                              │
     ┌───────┴───────┐                                              ┌───────┴───────┐
     ▼               ▼                                              ▼               ▼
┌─────────┐     ┌───────────┐                                  ┌──────────┐    ┌──────────┐
│Selection│     │ Insertion │                                  │  Shell   │    │   Heap   │
│  Sort   │     │   Sort    │                                  │   Sort   │    │   Sort   │
└─────────┘     └───────────┘                                  └──────────┘    └──────────┘

1. Bài toán sắp xếp trên mảng một chiều

Xác định bài toán sắp xếp một mảng $n$ số nguyên theo thứ tự tăng dần. Phân tích cấu trúc chỉ số mảng $a[0 \dots n-1]$ và sự dịch chuyển dữ liệu qua các bước lặp.

2. Thuật toán Chọn trực tiếp (Selection Sort)

  • Ý tưởng cốt lõi: Phân chia mảng thành hai phần: "phần đã sắp" (bên trái) và "phần chưa sắp" (bên phải). Tại mỗi bước lặp thứ $i$, tìm phần tử có giá trị nhỏ nhất trong phần chưa sắp, sau đó hoán vị phần tử này với phần tử đầu tiên của phần chưa sắp ($a[i]$).
  • Điều kiện dừng: Quá trình dừng lại khi phần chưa sắp chỉ còn đúng 1 phần tử (phần tử lớn nhất).
  • Cài đặt hàm:
void SelectionSort(int a[], int n) {
    int min; // Vị trí phần tử nhỏ nhất trong phần chưa sắp
    int tmp; // Biến tạm dùng khi hoán vị
    for (int i = 0; i < n; i++) {
        min = i;
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[min])
                min = j;
        }
        if (a[min] < a[i]) {
            tmp = a[i];
            a[i] = a[min];
            a[min] = tmp;
        }
    }
}
  • Đánh giá giải thuật:
    • Số phép so sánh trong mọi trường hợp: $$\sum_{i=1}^{n-1} (n - i) = (n - 1) + (n - 2) + \dots + 1 = \frac{n(n - 1)}{2} = O(n^2)$$
    • Số phép hoán vị: Trường hợp xấu nhất là $O(n)$, trường hợp tốt nhất (mảng đã có thứ tự tăng dần) là $0$.

3. Thuật toán Chèn trực tiếp (Insertion Sort)

  • Ý tưởng cốt lõi: Ban đầu, phần đã sắp chỉ gồm 1 phần tử đầu tiên $a[0]$. Mở rộng phần đã sắp bằng cách lấy phần tử kế tiếp $a[i]$ trong phần chưa sắp, lưu vào biến trung gian saved, dịch chuyển các phần tử lớn hơn saved trong phần đã sắp sang phải một vị trí để tạo khoảng trống, sau đó ghi giá trị saved vào đúng vị trí.
  • Cài đặt hàm:
void InsertionSort(int a[], int n) {
    int saved; // Biến trung gian lưu lại giá trị phần tử cần chèn
    for (int i = 1; i < n; i++) {
        saved = a[i];
        int j;
        for (j = i; j > 0 && saved < a[j - 1]; j--) {
            a[j] = a[j - 1]; // Dịch chuyển phần tử sang phải
        }
        a[j] = saved; // Chèn phần tử vào đúng vị trí
    }
}
  • Đánh giá giải thuật:
    • Trường hợp xấu nhất (mảng có thứ tự giảm dần): $$1 + 2 + \dots + (n - 1) = \frac{n(n - 1)}{2} = O(n^2) \text{ phép so sánh và dịch chuyển}$$
    • Trường hợp tốt nhất (mảng đã có thứ tự tăng dần): $O(n)$ phép so sánh và $0$ phép dịch chuyển.
  • So sánh Selection Sort và Insertion Sort: Cả hai đều có độ phức tạp xấu nhất $O(n^2)$, không phù hợp cho tập dữ liệu lớn. Tuy nhiên, Insertion Sort thể hiện hiệu năng thực thi tốt hơn khi dữ liệu đầu vào đã có tính thứ tự cục bộ hoặc gần như đã sắp xếp.

4. Thuật toán Shell Sort

  • Lịch sử và mục tiêu: Do Donald L. Shell đề xuất năm 1959 trên tạp chí Communications of the ACM, nhằm khắc phục nhược điểm dịch chuyển từng bước một của Insertion Sort và phá vỡ rào cản $O(n^2)$.
  • Nguyên lý chia khoảng cách: Chia mảng thành $h$ dãy con gồm các phần tử cách nhau khoảng cách $h$: $$a_k, a_{k+h}, a_{k+2h}, \dots \quad (\text{với } 0 \le k < h)$$ Thực hiện sắp xếp từng dãy con bằng phương pháp Insertion Sort. Lặp lại quá trình với các giá trị $h$ giảm dần về $1$.
  • Dãy gia số (Increment Sequence $h_k$): Dãy $h_1, h_2, \dots, h_t$ thỏa mãn tính chất giảm dần $h_i > h_{i+1}$ và $h_t = 1$.
  • Cài đặt hàm:
void ShellSort(int h[], int a[], int t, int n) {
    for (int k = 0; k < t; k++) {
        int increment = h[k];
        for (int i = increment; i < n; i++) {
            int saved = a[i];
            int j;
            for (j = i; j >= increment && saved < a[j - increment]; j -= increment) {
                a[j] = a[j - increment];
            }
            a[j] = saved;
        }
    }
}
  • Phân tích hiệu năng theo các dãy gia số:
    • Dãy Donald Shell: Chi phí trường hợp xấu nhất là $O(n^2)$.
    • Dãy Hibbard: Chi phí trường hợp xấu nhất là $O(n^{3/2})$.
    • Dãy Donald Knuth ($h_1 = 1, h_i = 3h_{i-1} + 1$, dừng tại $i = \lfloor\log_2 n\rfloor - 1$): Chuỗi giá trị $1, 4, 13, 40, 121, \dots$
    • Dãy Pratt ($2^p 3^q$): Chi phí đạt $O(n(\log_2 n)^2)$.

5. Thuật toán Sắp xếp vun đống (Heap Sort)

  • Lịch sử và vị trí: Được đề xuất năm 1964 bởi J. Williams trên tạp chí Communications of the ACM.
  • Đặc điểm kỹ thuật:
    • Thuộc nhóm thuật toán có độ phức tạp thời gian $O(n \log_2 n)$.
    • So với Quick Sort: Không đòi hỏi ngăn xếp đệ quy phức tạp.
    • So với Merge Sort: Không đòi hỏi mảng phụ để lưu trữ trung gian (sắp xếp tại chỗ - in-place).
  • Cấu trúc Heap: Định nghĩa Heap là một cây nhị phân đầy đủ (complete binary tree), trong đó mỗi nút chứa một giá trị có thể so sánh và thỏa mãn quan hệ thứ tự với các nút con; biểu diễn cây Heap trực tiếp thông qua mảng một chiều.

Kiến thức nền tảng và kỹ năng phát triển

Hạng mục Nội dung chi tiết
Kiến thức lý thuyết • Khái niệm mảng một chiều, chỉ số truy cập phần tử.
• Kỹ thuật phân hoạch không gian mảng thành các vùng dữ liệu có trạng thái khác nhau.
• Mô hình cây nhị phân hoàn chỉnh và kỹ thuật ánh xạ cây lên mảng.
• Phân tích tiệm cận hàm thời gian chạy $O(n)$, $O(n^2)$, $O(n^{3/2})$, $O(n \log^2 n)$, $O(n \log n)$.
Kỹ năng phân tích • Xác định số phép so sánh khóa (key comparisons) và phép gán/dịch chuyển dữ liệu (data movements).
• Nhận diện tình huống thực thi tốt nhất (best-case) và xấu nhất (worst-case) dựa trên trật tự ban đầu của dữ liệu.
• Phân tích sự phụ thuộc của hiệu năng thuật toán vào cấu trúc dãy gia số (đối với Shell Sort).
Kỹ năng lập trình • Hiện thực hóa thuật toán bằng ngôn ngữ C/C++ với vòng lặp lồng nhau và quản lý biến con trỏ/chỉ số.
• Tối ưu hóa việc ghi đè mảng thay cho hoán vị liên tục bằng cách sử dụng biến nhớ tạm thời (saved, tmp).

Phương pháp giảng dạy và học tập

Phương pháp sư phạm trực quan

Bài giảng sử dụng phương pháp mô hình hóa từng bước (step-by-step trace) thông qua sơ đồ mảng số nguyên. Mỗi vòng lặp được bóc tách rõ ràng theo trạng thái:

  • Chỉ số hiện hành của mảng.
  • Vùng chỉ số thuộc "phần đã sắp" và vùng chỉ số thuộc "phần chưa sắp".
  • Vị trí của biến trỏ giá trị nhỏ nhất min hoặc biến tạm lưu giá trị cần chèn saved.
Ví dụ vết thực thi Shell Sort trên mảng 13 phần tử:
Dữ liệu gốc: [81, 94, 11, 96, 12, 35, 17, 95, 28, 58, 41, 75, 15]

Bước 1 (h = 5):
  Chia 5 dãy con cách nhau 5 vị trí -> Sắp xếp Insertion Sort trên từng dãy
  Kết quả:   [35, 17, 11, 28, 12, 41, 75, 15, 96, 58, 81, 94, 95]

Bước 2 (h = 3):
  Chia 3 dãy con cách nhau 3 vị trí -> Sắp xếp Insertion Sort trên từng dãy
  Kết quả:   [28, 12, 11, 35, 15, 41, 58, 17, 94, 75, 81, 96, 95]

Bước 3 (h = 1):
  Áp dụng Insertion Sort tiêu chuẩn trên toàn bộ mảng
  Kết quả:   [11, 12, 15, 17, 28, 35, 41, 58, 75, 81, 94, 95, 96]

Bài tập thực hành và câu hỏi củng cố

Tài liệu tích hợp các câu hỏi kiểm tra tư duy trực tiếp trong tiến trình bài học:

  • Ví dụ kiểm tra số thao tác: Đặt câu hỏi định lượng "Có bao nhiêu phép dịch chuyển xảy ra?" khi chèn phần tử cuối cùng của mảng trong thuật toán Insertion Sort (xác định chính xác $4$ phép dịch chuyển trước khi khôi phục giá trị vào mảng).
  • Thực hành mã nguồn: Yêu cầu sinh viên chuyển đổi thuật toán từ mã giả/sơ đồ khối sang hàm C hoàn chỉnh, đảm bảo xử lý chính xác điều kiện biên tại các chỉ số $i = 0$, $j > 0$, $j \ge \text{increment}$.

Điểm nổi bật và tài liệu trích dẫn học thuật

Tài liệu thể hiện tính chuẩn xác học thuật thông qua việc trích dẫn nguồn gốc lịch sử của các phát minh thuật toán từ các tạp chí khoa học quốc tế:

  1. Công trình của Donald L. Shell (1959): Trích dẫn bài báo công bố thuật toán Shell Sort trên tạp chí chuyên ngành Communications of the ACM (CACM), làm rõ bước ngoặt lịch sử khi lần đầu tiên đưa độ phức tạp của bài toán sắp xếp vượt qua ngưỡng giới hạn $O(n^2)$.
  2. Công trình của J. Williams (1964): Trích dẫn công bố giải thuật Heap Sort trên tạp chí Communications of the ACM, phân tích cấu trúc cây nhị phân hoàn chỉnh được mảng hóa và chứng minh tính ổn định của chi phí thời gian $O(n \log_2 n)$.
  3. Tổng hợp nghiên cứu về chuỗi gia số: Điểm danh các công trình nghiên cứu toán học về tối ưu hóa dãy gia số $h_k$ của Hibbard, Donald Knuth và Pratt, khẳng định tính phức tạp toán học chưa có lời giải tuyệt đối về chuỗi gia số tối ưu tổng quát.

Đối tượng sử dụng giáo trình

┌─────────────────────────────────────────────────────────────────────────┐
│                        ĐỐI TƯỢNG SỬ DỤNG BÀI GIẢNG                       │
├────────────────────────────┬────────────────────────────────────────────┤
│ Sinh viên đại học          │ Sinh viên năm 1 và năm 2 khối ngành CNTT,  │
│                            │ Khoa học Máy tính, Kỹ thuật Phần mềm.      │
├────────────────────────────┼────────────────────────────────────────────┤
│ Kiến thức tiên quyết       │ • Lập trình C/C++ cơ bản (mảng, vòng lặp,  │
│                            │   hàm, biến con trỏ).                      │
│                            │ • Toán rời rạc (phép đếm, tổng chuỗi, log).│
├────────────────────────────┼────────────────────────────────────────────┤
│ Giảng viên & Nghiên cứu    │ Khung bài giảng chuẩn hóa cho các buổi học │
│                            │ lý thuyết và thực hành thuật toán cơ sở.   │
├────────────────────────────┼────────────────────────────────────────────┤
│ Tự học & Tham khảo         │ Tài liệu tham khảo chuẩn bị cho các kỳ thi │
│                            │ tuyển dụng kỹ thuật và lập trình thuật toán│
└────────────────────────────┴────────────────────────────────────────────┘

Câu hỏi thường gặp

1. Tài liệu này phù hợp với đối tượng nào?

Tài liệu được thiết kế trực tiếp cho sinh viên đại học đang học môn Cấu trúc dữ liệu và Giải thuật, cũng như người học cần hệ thống hóa các nguyên lý phân tích thuật toán sắp xếp kinh điển.

2. Cần chuẩn bị kiến thức nền tảng nào trước khi tiếp cận?

Người học cần nắm vững cú pháp lập trình C căn bản, thao tác duyệt và thao tác trên mảng số nguyên, cùng kiến thức toán học cơ bản về cấp số cộng và khái niệm độ phức tạp tiệm cận (Big-O).

3. Điểm khác biệt của tài liệu này so với các bài giảng sắp xếp thông thường là gì?

Tài liệu không chỉ dừng lại ở các thuật toán cơ bản $O(n^2)$ mà phân tích chuyên sâu giải thuật Shell Sort với các chiến lược xây dựng chuỗi gia số khác nhau ($Shell, Hibbard, Knuth, Pratt$), đồng thời so sánh cấu trúc vận hành của Heap Sort với Quick Sort và Merge Sort.

4. Phương pháp tự học hiệu quả với tài liệu này là gì?

Người học nên tự vẽ lại vết thực thi của từng thuật toán trên các mảng mẫu số nguyên kích thước nhỏ, sau đó tự tay cài đặt mã nguồn C/C++ dựa trên cấu trúc vòng lặp được cung cấp mà không nhìn bài giải mẫu.

5. Tài liệu có cung cấp mã nguồn minh họa hoàn chỉnh không?

Tài liệu cung cấp trực tiếp mã nguồn hàm viết bằng ngôn ngữ C cho các thuật toán: SelectionSort, InsertionSort, và ShellSort với đầy đủ chú thích chức năng của từng biến và điều kiện lặp.

Kết luận

Bài giảng "Cấu trúc dữ liệu & Giải thuật: Các thuật toán sắp xếp" của Khoa Công nghệ Thông tin, Trường Đại học Khoa học Tự nhiên TP.HCM cung cấp một hệ thống kiến thức hoàn chỉnh về mặt lý thuyết và thực hành đối với chuyên đề sắp xếp dữ liệu.

Bằng việc kết hợp giữa phân tích toán học độ phức tạp, mô hình hóa trực quan trạng thái mảng và cung cấp mã nguồn chuẩn xác, tài liệu thiết lập một lộ trình học tập logic từ các giải thuật $O(n^2)$ đến các giải thuật tối ưu $O(n \log_2 n)$. Đây là tài liệu học thuật cơ sở chuẩn mực phục vụ hiệu quả cho việc nghiên cứu và giảng dạy chuyên ngành công nghệ thông tin.