Sorting, COMPARISON-BASED vs NON-COMPARISON

PHÂN LOẠI: COMPARISON-BASED vs NON-COMPARISON

1. THUẬT TOÁN SẮP XẾP CÓ SO SÁNH (Comparison-Based Sorting)

Định nghĩa:

• Sắp xếp dựa trên phép so sánh giữa các phần tử (a < b, a > b, a == b)
• Quyết định thứ tự dựa trên kết quả so sánh
• Không quan tâm giá trị cụ thể của phần tử, chỉ cần biết "ai lớn hơn ai"

Ví dụ:

# Selection Sort - so sánh để tìm min
if arr[j] < arr[min_idx]:  # ← Phép SO SÁNH
    min_idx = j

# Quick Sort - so sánh với pivot
if arr[i] < pivot:  # ← Phép SO SÁNH
    # đặt vào bên trái

Các thuật toán:

• Selection Sort, Insertion Sort, Bubble Sort
• Quick Sort, Merge Sort, Heap Sort

Giới hạn lý thuyết (Lower Bound):

• Không thể nhanh hơn Ω(n log n) trong worst case
• Chứng minh bằng Decision Tree:
  • Cần phân biệt n! cách hoán vị khác nhau
  • Decision tree có ít nhất n! lá
  • Chiều cao tối thiểu: log₂(n!) = Ω(n log n)
  • Mỗi so sánh là 1 nút → cần ít nhất Ω(n log n) so sánh

Ưu điểm:

• Áp dụng cho mọi loại dữ liệu có thể so sánh (số, chuỗi, object tùy chỉnh)
• Không cần biết trước phạm vi giá trị
• Linh hoạt, dễ tùy chỉnh hàm so sánh

Nhược điểm:

• Bị giới hạn bởi Ω(n log n)
• Không thể nhanh hơn dù cố gắng

2. THUẬT TOÁN SẮP XẾP KHÔNG CẦN SO SÁNH (Non-Comparison Sorting)

Định nghĩa:

• Sắp xếp KHÔNG dựa trên so sánh giữa các phần tử
• Thay vào đó: dựa vào thuộc tính/cấu trúc của dữ liệu
  • Giá trị cụ thể của phần tử
  • Phạm vi giá trị (range)
  • Cấu trúc bên trong (chữ số, bits)

Ví dụ:

# Counting Sort - dùng giá trị làm INDEX
count[arr[i]] += 1  # ← KHÔNG SO SÁNH, chỉ đếm

# Radix Sort - dùng chữ số
digit = (num // exp) % 10  # ← KHÔNG SO SÁNH, trích xuất chữ số

Cách hoạt động:

Counting Sort (ví dụ đơn giản nhất):

Mảng: [3, 1, 3, 2, 1]
Giả sử: giá trị từ 0-9

Bước 1: Đếm tần suất (KHÔNG CẦN SO SÁNH!)
count[0] = 0
count[1] = 2  ← có 2 số 1
count[2] = 1  ← có 1 số 2
count[3] = 2  ← có 2 số 3
...

Bước 2: Xây dựng mảng kết quả
→ [1, 1, 2, 3, 3]

KHÔNG CẦN so sánh 3 với 1, 1 với 2, etc.
Chỉ cần đếm và đặt vào đúng vị trí!

Các thuật toán:

• Counting Sort (cơ sở cho các thuật toán khác)
• Bucket Sort
• Radix Sort

Vượt qua giới hạn Ω(n log n):

• Có thể đạt O(n) - linear time!
• Vì KHÔNG bị ràng buộc bởi decision tree
• Trade-off: Cần điều kiện đặc biệt về dữ liệu

Ưu điểm:

• Rất nhanh: O(n) trong trường hợp lý tưởng
• Ổn định (stable)
• Hiệu quả với số nguyên, chuỗi có độ dài cố định

Nhược điểm:

• Chỉ áp dụng cho dữ liệu đặc biệt:
  • Counting Sort: số nguyên trong phạm vi nhỏ
  • Radix Sort: số nguyên hoặc chuỗi
  • Bucket Sort: biết trước phân bố
• KHÔNG áp dụng cho:
  • Số thực (float/double)
  • Object phức tạp
  • Dữ liệu có phạm vi rộng
• Tốn bộ nhớ: O(n + k) với k là phạm vi giá trị

SO SÁNH TRỰC QUAN:

TẠI SAO NON-COMPARISON NHANH HƠN?

Comparison-based bị giới hạn vì:

• Mỗi so sánh chỉ cho 2 kết quả (true/false) → 1 bit thông tin
• Để phân biệt n! hoán vị cần log₂(n!) ≈ n log n so sánh

Non-comparison tránh được vì:

• Dùng nhiều thông tin hơn: giá trị cụ thể (log k bits)
• Counting Sort: biết chính xác vị trí mà không cần so sánh
• Radix Sort: dùng cấu trúc bên trong (chữ số)

VÍ DỤ MINH HỌA:

Bài toán: Sắp xếp [3, 1, 4, 1, 5] (giá trị từ 0-9)

Cách 1: Comparison (Insertion Sort)

So sánh 1: 3 vs 1 → swap
So sánh 2: 3 vs 4 → không swap
So sánh 3: 4 vs 1 → swap
So sánh 4: 3 vs 1 → swap
So sánh 5: 3 vs 5 → không swap
... (nhiều so sánh)

Cách 2: Non-Comparison (Counting Sort)

1. Đếm: count = [0,2,0,1,1,1,0,0,0,0]
           index:  0 1 2 3 4 5 6 7 8 9
2. Kết quả: [1, 1, 3, 4, 5]

KHÔNG CẦN so sánh! Chỉ O(n) thao tác!

II. CÁC THUẬT TOÁN SẮP XẾP SO SÁNH (COMPARISON-BASED)

1. SELECTION SORT

Lịch sử:

• Một trong những thuật toán sắp xếp cổ điển nhất, được mô tả từ những năm 1950s
• Phản ánh cách con người tự nhiên sắp xếp: tìm phần tử nhỏ nhất rồi đặt vào đúng vị trí

Cách hoạt động:

• Chia mảng thành 2 phần: đã sắp xếp và chưa sắp xếp
• Mỗi bước: tìm phần tử nhỏ nhất trong phần chưa sắp xếp, đổi chỗ với phần tử đầu tiên của phần chưa sắp xếp
• Lặp lại cho đến khi hết mảng

Đặc điểm:

• Time Complexity: O(n²) cho mọi trường hợp
• Space Complexity: O(1) - in-place
• Không ổn định (unstable)
• Số lần so sánh: luôn n(n-1)/2
• Số lần swap: tối đa n-1
• Ưu điểm: Ít phép gán nhất trong các thuật toán O(n²), tốt khi chi phí ghi dữ liệu cao
• Nhược điểm: Luôn chậm, không tận dụng được dữ liệu đã sắp xếp

2. INSERTION SORT

Lịch sử:

• Được mô tả chính thức vào những năm 1950s
• Lấy cảm hứng từ cách sắp xếp bài trong tay người chơi

Cách hoạt động:

• Giống như sắp bài: lấy từng lá bài và chèn vào đúng vị trí trong tay
• Duyệt từ trái sang phải, mỗi phần tử được chèn vào đúng vị trí trong phần đã sắp xếp

Đặc điểm:

• Time Complexity:
  • Best case: O(n) - dữ liệu đã sắp xếp
  • Average/Worst: O(n²)
• Space Complexity: O(1)
• Ổn định (stable)
• Ưu điểm:
  • Rất nhanh với dữ liệu gần sắp xếp
  • Online algorithm - có thể sắp xếp khi nhận dữ liệu
  • Đơn giản, hiệu quả với mảng nhỏ
• Nhược điểm: Chậm với dữ liệu lớn, ngẫu nhiên

3. BUBBLE SORT

Lịch sử:

• Xuất hiện vào những năm 1950s
• Tên gọi từ hình ảnh "bong bóng nổi lên" của các phần tử lớn

Cách hoạt động:

• So sánh từng cặp phần tử liền kề
• Đổi chỗ nếu sai thứ tự
• Sau mỗi lượt, phần tử lớn nhất "nổi" lên cuối

Đặc điểm:

• Time Complexity: O(n²), best case O(n) với optimization
• Space Complexity: O(1)
• Ổn định (stable)
• Ưu điểm: Đơn giản, dễ hiểu, dễ cài đặt
• Nhược điểm: Chậm nhất trong các thuật toán O(n²), ít được dùng trong thực tế

4. QUICK SORT

Lịch sử:

• Phát triển bởi Tony Hoare năm 1959, công bố 1961
• Một trong những thuật toán có ảnh hưởng lớn nhất trong lịch sử khoa học máy tính
• Tên gọi từ "quick" vì nó nhanh trong thực tế

Cách hoạt động:

• Divide and Conquer
• Chọn pivot, phân hoạch mảng thành 2 phần: nhỏ hơn và lớn hơn pivot
• Đệ quy sắp xếp 2 phần

Đặc điểm:

• Time Complexity:
  • Average: O(n log n)
  • Worst: O(n²) - pivot xấu
• Space Complexity: O(log n) - đệ quy
• Không ổn định (có thể cài đặt stable nhưng phức tạp)

Giải thích chi tiết về Worst Case O(n²):

Quick Sort có worst case O(n²) khi pivot được chọn rất tệ, dẫn đến phân hoạch không cân bằng.

Khi nào xảy ra Worst Case?

Tất cả phần tử giống nhau:

Mảng: [5, 5, 5, 5, 5]
→ Tùy cách cài đặt, có thể dẫn đến O(n²)

Mảng sắp xếp ngược:

Mảng: [5, 4, 3, 2, 1]
Pivot = 5 (phần tử đầu)
→ Phân hoạch: [4,3,2,1] | pivot=5 | []
→ Vẫn không cân bằng!

Mảng đã sắp xếp + pivot là phần tử đầu/cuối:

Mảng: [1, 2, 3, 4, 5]
Pivot = 1 (phần tử đầu)
→ Phân hoạch: [] | pivot=1 | [2,3,4,5]
→ Một bên 0 phần tử, một bên n-1 phần tử

Lặp lại với [2,3,4,5]:
Pivot = 2
→ Phân hoạch: [] | pivot=2 | [3,4,5]

→ Tổng số phép so sánh: n + (n-1) + (n-2) + ... + 1 = n(n-1)/2 = O(n²)

Tại sao lại O(n²)?

• Độ sâu đệ quy: thay vì log n (cây cân bằng) → trở thành n (cây lệch)
• Mỗi cấp vẫn phải duyệt qua các phần tử: O(n)
• Tổng: O(n) × n cấp = O(n²)

Cách khắc phục Worst Case:

1. Randomized Pivot: Chọn pivot ngẫu nhiên
   • Expected time: O(n log n) với mọi input
   • Không đảm bảo worst case nhưng xác suất rất thấp
2. Median-of-Three: Chọn pivot là median của 3 phần tử (đầu, giữa, cuối)
   • Tránh được worst case với mảng đã sắp xếp
   • Vẫn có thể worst case nhưng hiếm hơn
3. Median-of-Medians: Tìm pivot "thực sự" gần median
   • Đảm bảo O(n log n) worst case
   • Nhưng overhead lớn, ít dùng trong thực tế
4. Intro Sort (C++ STL): Kết hợp Quick Sort + Heap Sort
   • Bắt đầu với Quick Sort
   • Nếu độ sâu đệ quy > 2×log(n) → chuyển sang Heap Sort
   • Đảm bảo O(n log n) worst case

Ví dụ cụ thể về Worst Case:

Mảng n=5: [1, 2, 3, 4, 5], pivot luôn chọn phần tử đầu

Bước 1: pivot=1, so sánh 4 lần
[1] | [2, 3, 4, 5]

Bước 2: pivot=2, so sánh 3 lần
[1, 2] | [3, 4, 5]

Bước 3: pivot=3, so sánh 2 lần
[1, 2, 3] | [4, 5]

Bước 4: pivot=4, so sánh 1 lần
[1, 2, 3, 4] | [5]

Tổng: 4 + 3 + 2 + 1 = 10 = 5×4/2 = n(n-1)/2 = O(n²)

So sánh Best vs Worst Case:

Tần suất trong thực tế:

• Với random pivot: xác suất worst case ≈ 1/(n!) → cực kỳ thấp
• Với median-of-three: hiếm khi xảy ra
• Trong thực tế: Quick Sort gần như luôn O(n log n)
• Ưu điểm:
  • Rất nhanh trong thực tế (cache-friendly, ít overhead)
  • In-place (phiên bản chuẩn)
  • Dễ song song hóa
  • Với randomization, expected time luôn O(n log n)
• Nhược điểm:
  • Worst case O(n²) (tuy hiếm khi xảy ra)
  • Không ổn định
  • Cần cẩn thận chọn pivot cho dữ liệu đặc biệt

5. MERGE SORT

Lịch sử:

• Phát minh bởi John von Neumann năm 1945
• Một trong những thuật toán sắp xếp đầu tiên dùng Divide and Conquer
• Ban đầu dùng cho máy tính đầu tiên EDVAC

Cách hoạt động:

• Divide and Conquer
• Chia mảng thành 2 nửa đến khi còn 1 phần tử
• Merge (trộn) các mảng con đã sắp xếp

Đặc điểm:

• Time Complexity: O(n log n) cho mọi trường hợp
• Space Complexity: O(n) - cần mảng phụ
• Ổn định (stable)
• Ưu điểm:
  • Hiệu năng ổn định, đảm bảo O(n log n)
  • Stable - quan trọng cho nhiều ứng dụng
  • Tốt cho linked list
  • Dễ song song hóa
  • External sorting (sắp xếp dữ liệu không vừa RAM)
• Nhược điểm:
  • Cần thêm O(n) bộ nhớ
  • Chậm hơn Quick Sort trong thực tế

6. HEAP SORT

Lịch sử:

• Phát triển bởi J. W. J. Williams năm 1964
• Dựa trên cấu trúc Binary Heap (Max Heap hoặc Min Heap)
• Kết hợp ý tưởng Selection Sort với cấu trúc dữ liệu hiệu quả

Cách hoạt động:

• Xây dựng Max Heap từ mảng
• Lặp lại:
  • Lấy phần tử lớn nhất (root)
  • Đổi với phần tử cuối
  • Giảm kích thước heap, heapify lại

Đặc điểm:

• Time Complexity: O(n log n) cho mọi trường hợp
• Space Complexity: O(1) - in-place
• Không ổn định (unstable)
• Ưu điểm:
  • Đảm bảo O(n log n) worst case
  • In-place, không cần thêm bộ nhớ
  • Tốt khi bộ nhớ hạn chế
• Nhược điểm:
  • Chậm hơn Quick Sort trong thực tế (cache không thân thiện)
  • Không stable
  • Khó song song hóa

III. CÁC THUẬT TOÁN SẮP XẾP KHÔNG SO SÁNH (NON-COMPARISON)

7. BUCKET SORT (BIN SORT)

Lịch sử:

• Xuất hiện vào những năm 1950s
• Lấy cảm hứng từ việc phân loại thư tín theo địa chỉ

Cách hoạt động:

• Chia dữ liệu vào các "bucket" (thùng) theo giá trị
• Sắp xếp từng bucket (thường dùng Insertion Sort)
• Nối các bucket lại

Đặc điểm:

• Time Complexity:
  • Average: O(n + k) với k là số bucket
  • Worst: O(n²) - tất cả vào 1 bucket
• Space Complexity: O(n + k)
• Có thể stable tùy cài đặt
• Ưu điểm:
  • Rất nhanh khi dữ liệu phân bố đều
  • Linear time trong trường hợp lý tưởng
• Nhược điểm:
  • Cần biết trước phân bố dữ liệu
  • Tốn bộ nhớ
  • Hiệu năng phụ thuộc nhiều vào input

8. RADIX SORT

Lịch sử:

• Sử dụng từ những năm 1887 với máy đếm thẻ đục lỗ của Herman Hollerith
• Được formalize trong computer science những năm 1950s-1960s
• Một trong những thuật toán cổ điển nhất (trước cả máy tính điện tử!)

Cách hoạt động:

• Sắp xếp theo từng chữ số/ký tự (digit)
• LSD (Least Significant Digit): từ phải sang trái
• MSD (Most Significant Digit): từ trái sang phải
• Mỗi lượt dùng Counting Sort hoặc Bucket Sort

Đặc điểm:

• Time Complexity: O(d × (n + k))
  • d: số chữ số
  • k: số giá trị có thể của mỗi chữ số (thường là 10)
• Space Complexity: O(n + k)
• Ổn định (stable) - quan trọng cho thuật toán hoạt động đúng
• Ưu điểm:
  • Linear time O(n) khi d là hằng số
  • Rất nhanh cho số nguyên, chuỗi có độ dài cố định
  • Không cần so sánh
• Nhược điểm:
  • Chỉ áp dụng cho dữ liệu có thể chia thành chữ số
  • Tốn bộ nhớ
  • Chậm khi d lớn

IV. TẠI SAO CẦN NHIỀU THUẬT TOÁN?

1. Độ phức tạp thời gian khác nhau

• O(n²): tốt cho mảng nhỏ (< 50 phần tử), đơn giản
• O(n log n): tốt cho mảng lớn
• O(n): tốt khi có điều kiện đặc biệt

2. Bộ nhớ khác nhau

• In-place (O(1)): Selection, Insertion, Heap, Quick
• Cần thêm O(n): Merge, Bucket, Radix
• Quan trọng với hệ thống nhúng, bộ nhớ hạn chế

3. Tính ổn định (Stability)

• Stable: Insertion, Merge, Bubble, Radix
• Unstable: Selection, Quick, Heap
• Quan trọng khi sắp xếp theo nhiều tiêu chí

4. Đặc điểm dữ liệu đầu vào

• Gần sắp xếp: Insertion Sort xuất sắc O(n)
• Ngẫu nhiên: Quick Sort, Merge Sort
• Phân bố đặc biệt: Bucket, Radix

5. Hiệu năng thực tế vs lý thuyết

• Quick Sort O(n log n) average nhưng nhanh hơn Merge Sort O(n log n) vì:
  • Cache-friendly
  • Ít overhead
  • In-place
• Merge Sort stable và đảm bảo worst case

6. Loại dữ liệu

• So sánh được: dùng comparison-based
• Số nguyên/chuỗi: Radix, Bucket nhanh hơn
• Số thực: chỉ dùng comparison-based

7. Môi trường thực thi

• Đơn luồng: Quick Sort
• Đa luồng: Merge Sort dễ song song hóa
• External sorting: Merge Sort

8. Yêu cầu đặc biệt

• Online algorithm: Insertion Sort
• Worst-case guarantee: Merge Sort, Heap Sort
• Ít swap: Selection Sort

V. BẢNG SO SÁNH TỔNG QUAN

VI. KẾT LUẬN

Không có thuật toán sắp xếp nào "tốt nhất cho mọi trường hợp" vì:

1. Trade-offs khác nhau: Thời gian vs Bộ nhớ, Trường hợp trung bình vs Worst case
2. Đặc điểm dữ liệu: Kích thước, phân bố, loại dữ liệu
3. Yêu cầu hệ thống: Bộ nhớ, stability, đảm bảo hiệu năng
4. Ngữ cảnh ứng dụng: Real-time, embedded, distributed systems

Trong thực tế:

• Java: Dual-Pivot Quick Sort cho primitive types, Tim Sort (Merge + Insertion) cho objects
• Python: Tim Sort (hybrid)
• C++ STL: Intro Sort (Quick + Heap + Insertion)
• Databases: External Merge Sort
• Embedded systems: Insertion Sort hoặc Heap Sort (bộ nhớ hạn chế)

Nguyên tắc chọn thuật toán:

1. Mảng nhỏ (n < 50): Insertion Sort
2. Cần stable: Merge Sort hoặc Tim Sort
3. Bộ nhớ hạn chế: Heap Sort hoặc Quick Sort
4. Đảm bảo worst-case: Merge Sort hoặc Heap Sort
5. Hiệu năng trung bình tốt nhất: Quick Sort (với pivot tốt)
6. Dữ liệu đặc biệt (số nguyên, phân bố đều): Radix Sort, Bucket Sort
7. External sorting: Merge Sort
8. Dữ liệu gần sắp xếp: Insertion Sort

Đây là lý do tại sao sinh viên Computer Science phải học nhiều thuật toán - để hiểu khi nào dùng thuật toán nào! Mỗi thuật toán là một công cụ, và lập trình viên giỏi biết chọn công cụ phù hợp cho từng tình huống.