DSA Từ A-Z – Day 2: Sorting Algorithms

Chào các bạn thân mến! Loser1 từ Learning AI with Losers đây. Chúc mừng năm mới 2025! Hôm nay, trong không khí Tết vui tươi, chúng ta sẽ cùng nhau khám phá những thuật toán sắp xếp tuyệt vời và học cách áp dụng chúng một cách hiệu quả. Let’s sort it out! 🎯

1. Overview – Sắp Xếp Là Gì? 🤔

Tưởng tượng bạn đang sắp xếp bài:
[7♠] [2♥] [5♦] [1♣] [4♠]
     ↓
[1♣] [2♥] [4♠] [5♦] [7♠]

→ Đó chính là sorting!

Tại sao sorting quan trọng? 🌟

1. Tìm kiếm nhanh hơn:
   Unsorted: [7,2,5,1,4] → O(n)
   Sorted:   [1,2,4,5,7] → O(log n)

2. Phân tích dữ liệu dễ dàng:
   - Tìm min/max
   - Tìm median
   - Phát hiện duplicates

2. Bubble Sort – “Bong Bóng Nổi” 🫧

2.1 Trực Quan Hóa 🎨

Initial: [5] [2] [8] [1] [9]

Step 1:  [2] [5] [1] [8] [9]  
         ↑   ↑
Step 2:  [2] [1] [5] [8] [9]
             ↑   ↑
Step 3:  [1] [2] [5] [8] [9]
         ↑   ↑

→ Lớn nhất "nổi" lên trên!

2.2 Code với Animation 💻

C++

void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    bool hadSwap;

    for(int i = 0; i < n-1; i++) {
        hadSwap = false;
        // Visualization của mỗi pass:
        // [5,2,8,1,9] → pass 1
        // [2,5,1,8,9] → pass 2
        // [2,1,5,8,9] → pass 3
        // [1,2,5,8,9] → Sorted!
        for(int j = 0; j < n-1-i; j++) {
            if(arr[j] > arr[j+1]) {
                swap(arr[j], arr[j+1]);
                hadSwap = true;
            }
        }
        if(!hadSwap) break;  // Optimization!
    }
}

3. Selection Sort – “Chọn Người Xuất Sắc” 🏆

3.1 Trực Quan Hóa 🎨

Initial: [64] [34] [25] [12] [22]
         └──── Tìm min trong cả dãy ──┘

Pass 1:  [12] [34] [25] [64] [22]
              └─── Tìm min ────┘

Pass 2:  [12] [22] [25] [64] [34]
                   └── min ──┘

3.2 Code với Animation 🎯

C++

void selectionSort(vector<int>& arr) {
    int n = arr.size();

    for(int i = 0; i < n-1; i++) {
        int minIdx = i;
        // Visualization:
        // [64,34,25,12,22] → Find 12
        // [12,34,25,64,22] → Find 22
        // [12,22,25,64,34] → Find 25
        for(int j = i+1; j < n; j++) {
            if(arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        if(minIdx != i) {
            swap(arr[i], arr[minIdx]);
        }
    }
}

4. Insertion Sort – “Xếp Bài Poker” 🎴

4.1 Trực Quan Hóa 🃏

Giống như cách bạn xếp bài:
[5] [2] [8] [1] [9]

Step 1: [2,5] | [8,1,9]
        ← 2 chèn trước 5

Step 2: [2,5,8] | [1,9]
        8 đã đúng vị trí

Step 3: [1,2,5,8] | [9]
        ← 1 chèn đầu dãy

4.2 Code với Animation ✨

C++

void insertionSort(vector<int>& arr) {
    int n = arr.size();

    for(int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;

        // Visualization:
        // [5|2,8,1,9] → [2,5|8,1,9]
        // [2,5,8|1,9] → [1,2,5,8|9]
        // [1,2,5,8,9] → Done!

        while(j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

5. Complexity Comparison 📊

Visualization của Time Complexity:

O(n²) Algorithms:
n = 5 elements
┌─────────────┐
│ Bubble    25│ █████
│ Selection 25│ █████
│ Insertion 25│ █████
└─────────────┘

Best Cases:
┌─────────────┐
│ Bubble    5 │ █
│ Selection 25│ █████
│ Insertion 5 │ █
└─────────────┘

6. Khi Nào Dùng Gì? 🤔

Bubble Sort:
✅ Dữ liệu gần như đã sort
✅ Cần stable sort
❌ Dữ liệu lớn, random

Selection Sort:
✅ Cần ít swap nhất có thể
✅ Memory giới hạn
❌ Cần stable sort

Insertion Sort:
✅ Dữ liệu gần như đã sort
✅ Sort online (dữ liệu đến real-time)
✅ Memory giới hạn

DSA From Zero to Hero – Day 2: Advanced Sorting – Magic of Divide & Conquer! 🚀

Chúng ta sẽ khám phá hai thuật toán sắp xếp “đỉnh của chóp”: Quick Sort và Merge Sort! Let’s make sorting quick and fun! 🎯

1. Quick Sort – Nghệ Thuật Chọn “Người Dẫn Đường” 🏃‍♂️

1.1. Tư Duy Quick Sort 🧠

Tưởng tượng bạn là trưởng nhóm sắp xếp:

Initial: [6] [3] [8] [5] [2]
         ⭐         
Chọn 6 làm "pivot" (người dẫn đường):
[3] [2] [5] [6] [8]
 ← nhỏ hơn 6 → | ← lớn hơn 6 →

1.2. Visualization Step by Step 🎨

Array: [6,3,8,5,2]
Pivot: 6

Step 1: Partition
[6] [3] [8] [5] [2]  Initial
[2] [3] [8] [5] [6]  Swap 2
[2] [3] [5] [8] [6]  Swap 5
[2] [3] [5] [6] [8]  Place pivot

Step 2: Recursion
Left:  [2,3,5]  Right: [8]
   ↓              ↓
[2,3,5]         [8]     Done!

1.3. Code Implementation with Rich Comments 🎯

C++

void quickSort(vector<int>& arr, int left, int right) {
    if (left >= right) return;  // Trường hợp cơ bản: 1 phần tử

    // 1. Chọn chốt (pivot) bằng phương pháp trung vị của ba phần tử
    int mid = left + (right - left) / 2;
    int pivot = medianOfThree(arr[left], arr[mid], arr[right]);

    // 2. Phân hoạch (partition) xung quanh chốt
    int pivotIdx = partition(arr, left, right, pivot);

    // Minh họa sau khi phân hoạch:
    // [2, 3, 5 | 6 | 8]
    //  ← nhỏ hơn →   ← lớn hơn →

    // 3. Gọi đệ quy để sắp xếp hai phần mảng con
    quickSort(arr, left, pivotIdx - 1);   // Sắp xếp nửa bên trái
    quickSort(arr, pivotIdx + 1, right);  // Sắp xếp nửa bên phải
}

int partition(vector<int>& arr, int left, int right) {
    int pivot = arr[right];  // Chọn phần tử ngoài cùng bên phải làm chốt
    int i = left - 1;        // Chỉ mục của phần tử nhỏ hơn

    // Di chuyển các phần tử nhỏ hơn sang bên trái
    for (int j = left; j < right; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
            // Minh họa: [nhỏ][nhỏ]|[lớn][chốt][chưa biết]
            //                   ↑     
        }
    }

    // Đặt chốt vào vị trí đúng
    swap(arr[i + 1], arr[right]);
    return i + 1;
}

2. Merge Sort – Nghệ Thuật “Chia Để Trị” 🎭

2.1. Tư Duy Merge Sort 🧩

Chia nhỏ vấn đề:
[7,2,6,3]
    ↙    ↘
[7,2]    [6,3]
↙  ↘    ↙  ↘
[7][2]  [6][3]  → Đã sắp xếp!
  ↓       ↓
[2,7]   [3,6]   → Merge
    ↘   ↙
[2,3,6,7]       → Final merge

2.2. Visualization of Merging 🎨

Gộp [2,7] và [3,6]:

Bước 1: So sánh phần tử đầu tiên
[2│7] [3│6]
 ↑    ↑
 min = 2 → [2]

Bước 2: Tiếp tục so sánh
[2│7] [3│6]
    ↑  ↑
 → [2,3]

Bước 3: Hoàn thành việc gộp
[2,3,6,7]

2.3. Detailed Implementation 💻

C++

void mergeSort(vector<int>& arr, int left, int right) {
    // Trường hợp cơ bản: Một phần tử đã được sắp xếp sẵn
    if (left >= right) return;

    // 1. Chia mảng thành hai nửa
    int mid = left + (right - left) / 2;

    // Minh họa quá trình chia:
    // [7,2,6,3] → [7,2] [6,3]

    // 2. Đệ quy sắp xếp từng nửa
    mergeSort(arr, left, mid);      // Sắp xếp nửa bên trái
    mergeSort(arr, mid + 1, right); // Sắp xếp nửa bên phải

    // 3. Gộp hai nửa đã sắp xếp
    merge(arr, left, mid, right);
}

void merge(vector<int>& arr, int left, int mid, int right) {
    vector<int> temp(right - left + 1);  // Mảng tạm thời
    int i = left;     // Con trỏ bắt đầu nửa trái
    int j = mid + 1;  // Con trỏ bắt đầu nửa phải
    int k = 0;        // Con trỏ của mảng tạm thời

    // So sánh và gộp hai nửa
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
            // Minh họa: [2,7]|[3,6] → [2]|[7][3,6]
        } else {
            temp[k++] = arr[j++];
            // Minh họa: [2,7]|[3,6] → [2,3]|[7][6]
        }
    }

    // Sao chép các phần tử còn lại
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];

    // Sao chép dữ liệu từ mảng tạm về mảng gốc
    for (int p = 0; p < k; p++) {
        arr[left + p] = temp[p];
    }
}

3. Complexity & Comparison 📊

Space-Time Tradeoff 📈

Quick Sort vs Merge Sort:

Memory Usage:        Speed:
┌────────────┐      ┌────────────┐
│Quick  O(1) │ █    │Quick O(nlogn)│ ████
│Merge  O(n) │ ███  │Merge O(nlogn)│ ████
└────────────┘      └────────────┘

Stability:
Quick Sort: Không ổn định
Merge Sort: Ổn định ✨

When to Use What? 🤔

Quick Sort:
✅ Memory hạn chế
✅ Cần tốc độ trung bình nhanh nhất
✅ Dữ liệu random

Merge Sort:
✅ Cần stable sort
✅ Có đủ memory
✅ Cần worst case O(nlogn)

4. Advanced Tips & Tricks 💡

Hybrid Approaches:

C++

// Kết hợp với Insertion Sort cho arrays nhỏ
if(right - left < 10) {
    insertionSort(arr, left, right);
    return;
}

Pivot Selection:

C++

// Median of three
int pivot = medianOfThree(
    arr[left],
    arr[(left + right)/2],
    arr[right]
);

Memory Optimization:

C++

// In-place merge sort
// Sử dụng rotation thay vì mảng phụ

Chúc các bạn học vui! Let’s divide and conquer our way to sorting mastery! 🚀

P/S: Follow mình tại Learning AI with Loser để cập nhật các bài DSA thú vị khác nhé! 💻✨

#dsa #algorithms #programming #learningwithlosers

Author: Loser1 from Learning AI With Losers

DSA Từ A-Z: Day 2 – Heap Sort và Thuật Toán Sắp Xếp Đặc Biệt 🎯

Xin chào các bạn yêu quý! Loser1 từ Learning AI with Losers đây. Hôm nay chúng ta sẽ khám phá ba thuật toán sắp xếp “thần thánh”: Heap Sort, Counting Sort và Radix Sort! Let’s make sorting magical! ✨

1.Heap Sort – Nghệ Thuật Xây Dựng “Kim Tự Tháp” 🔺

1. Binary Heap – Cấu Trúc Kim Tự Tháp 🔺

Binary Max Heap là một cây nhị phân hoàn chỉnh (complete binary tree) với hai tính chất:

Tính chất hình dạng: Cây được lấp đầy từ trái sang phải, không có “lỗ hổng”.
Tính chất thứ tự: Mỗi nút cha có giá trị lớn hơn hoặc bằng các nút con (Max Heap).

Ví dụ minh họa:

        9         ← Root (phần tử lớn nhất)
      /   \
     6     8      ← Các nút con
    / \   /
   4   5 7        ← Các nút lá

Parent (9) > Children (6, 8) > Grandchildren (4, 5, 7).

2. Biểu Diễn Heap Bằng Mảng 📊

Heap được lưu trong mảng với các quy tắc:

Gốc (root): arr[0]
Con trái của arr[i]: arr[2*i + 1]
Con phải của arr[i]: arr[2*i + 2]
Cha của arr[i]: arr[(i-1)/2]

Ví dụ:

Mảng: [9, 6, 8, 4, 5, 7]
Index: 0  1  2  3  4  5

Cây tương ứng:
        9 (0)
      /   \
    6 (1) 8 (2)
   / \    /
4(3)5(4)7(5)

3. Heapify – Trái Tim Của Heap Sort ❤️

Heapify là quá trình đảm bảo một nút và các con của nó thỏa mãn tính chất Max Heap. Nếu nút cha nhỏ hơn con, ta hoán đổi cha và con, sau đó tiếp tục heapify xuống dưới.

Ví dụ minh họa:
Giả sử ta có cây:

Bước 1: So sánh 4 với con trái (9) và con phải (8). 9 là lớn nhất.
Bước 2: Hoán đổi 4 và 9.
Bước 3: Tiếp tục heapify cho nút 4 (đang ở vị trí con trái của 9).

Code C++:

C++

void heapify(vector<int>& arr, int n, int i) {
    int largest = i;         // Khởi tạo largest là cha
    int left = 2 * i + 1;    // Con trái
    int right = 2 * i + 2;   // Con phải

    // Tìm phần tử lớn nhất giữa cha, con trái, và con phải
    if (left < n && arr[left] > arr[largest])
        largest = left;
    if (right < n && arr[right] > arr[largest])
        largest = right;

    // Nếu largest không phải cha, hoán đổi và tiếp tục heapify
    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest); // Đệ quy heapify nhánh bị ảnh hưởng
    }
}

4. Quá Trình Heap Sort Từng Bước 🎬

Bước 1: Xây Dựng Max Heap (buildMaxHeap)

Mục tiêu: Biến mảng thành một Max Heap hợp lệ.
Cách làm: Heapify tất cả nút không phải lá (từ n/2 - 1 về 0).

Ví dụ: Mảng [4, 1, 3, 2, 5] → Xây Max Heap:

Giai đoạn 1: Bắt đầu từ nút không phải lá cuối cùng (index = 1)
        4
      /   \
    1      3
  / \
 2   5

Heapify tại index 1 (giá trị 1):
- So sánh 1 với con phải 5 → Hoán đổi → [4,5,3,2,1]
        4
      /   \
    5      3
  / \
 2   1

Heapify tại index 0 (giá trị 4):
- So sánh 4 với 5 và 3 → Hoán đổi 4 và 5 → [5,4,3,2,1]
        5
      /   \
    4      3
  / \
 2   1

Bước 2: Trích Xuất Phần Tử Lớn Nhất

Mục tiêu: Đưa phần tử lớn nhất (root) về cuối mảng, giảm kích thước heap, và heapify lại.

Ví dụ:

Mảng sau buildMaxHeap: [5,4,3,2,1]
Lần lặp 1:
- Hoán đổi 5 (root) và 1 (cuối mảng): [1,4,3,2,5]
- Heapify phần đầu (n=4, i=0):
        1
      /   \
    4      3
  / 
 2

Heapify tại 0:
- So sánh 1 với 4 và 3 → Hoán đổi 1 và 4 → [4,1,3,2,5]
        4
      /   \
    1      3
  / 
 2

Mảng hiện tại: [4,1,3,2,5] → Phần đã sắp xếp: [5]

Lần lặp 2:
- Hoán đổi 4 và 2: [2,1,3,4,5]
- Heapify phần đầu (n=3, i=0):
        2
      /   \
    1      3

Heapify tại 0:
- So sánh 2 với 3 → Hoán đổi → [3,1,2,4,5]
...
Tiếp tục đến khi mảng được sắp xếp: [1,2,3,4,5]

5. Tại Sao Heapify Bắt Đầu Từ n/2 – 1? 🤔

Các nút lá (từ n/2 đến n-1) không có con, nên chúng đã thỏa mãn tính chất Max Heap.
Chỉ cần heapify các nút không phải lá (từ n/2 - 1 về 0).

6. Độ Phức Tạp ⚡

Xây dựng Max Heap: O(n)
Trích xuất và heapify: O(n log n)
Tổng: O(n log n) cho mọi trường hợp.

Kết Luận: Heap Sort như một “kiến trúc sư” xây dựng kim tự tháp (Max Heap), sau đó lần lượt chọn đá lớn nhất đặt đúng vị trí. Heapify là trái tim của thuật toán, đảm bảo tính chất Max Heap được duy trì sau mỗi lần trích xuất!

2 . Counting Sort – Giải Thích Từng Bước Với Minh Họa Chi Tiết 🧮

1. Tư Duy Chính Của Counting Sort 🧠

Counting Sort là thuật toán sắp xếp không so sánh, hoạt động bằng cách:

Đếm số lần xuất hiện của từng giá trị trong mảng.
Ánh xạ các giá trị này vào vị trí chính xác trong mảng đã sắp xếp.

Ưu điểm:

Độ phức tạp O(n + k) (k là khoảng giá trị), cực nhanh khi phạm vi giá trị nhỏ.
Ổn định (giữ nguyên thứ tự các phần tử bằng nhau).

Nhược điểm:

Không phù hợp khi phạm vi giá trị (k) quá lớn.

2. Ví Dụ Minh Họa Sống Động 🌟

Input: [4, 2, 1, 4, 2, 3, 1]
Mục tiêu: Sắp xếp mảng tăng dần.

3. Bước 1: Xác Định Phạm Vi Giá Tr trị 🌍

Tìm min và max:
minVal = 1 (giá trị nhỏ nhất)
maxVal = 4 (giá trị lớn nhất)
Tính range: maxVal - minVal + 1 = 4 - 1 + 1 = 4
→ Tạo mảng count có 4 phần tử (index 0-3 tương ứng giá trị 1-4).

4. Bước 2: Đếm Tần Suất Xuất Hiện 🔢

C++

vector<int> count(range); // Khởi tạo count = [0,0,0,0]
for (int num : arr) {
    count[num - minVal]++; // num - 1 → ánh xạ về index 0-3
}

Kết quả:

Giá trị: 1  2  3  4
Index:  0  1  2  3
Count: [2, 2, 1, 2] 
→ 1 xuất hiện 2 lần, 2 xuất hiện 2 lần, 3 xuất hiện 1 lần, 4 xuất hiện 2 lần.

5. Bước 3: Tính Vị Trí Tích Lũy 📈

Mục tiêu: Tính vị trí cuối cùng của mỗi giá trị trong mảng đã sắp xếp.

C++

for (int i = 1; i < range; i++) {
    count[i] += count[i - 1];
}

Giải thích:

count[i] = số phần tử ≤ giá trị tương ứng.
Biến đổi count từ [2, 2, 1, 2] → [2, 4, 5, 7]:

  Index 0 (giá trị 1): 2 phần tử ≤ 1
  Index 1 (giá trị 2): 2 + 2 = 4 phần tử ≤ 2
  Index 2 (giá trị 3): 4 + 1 = 5 phần tử ≤ 3
  Index 3 (giá trị 4): 5 + 2 = 7 phần tử ≤ 4

6. Bước 4: Xây Dựng Mảng Đầu Ra 🏗️

Quy tắc: Duyệt mảng từ cuối về đầu để đảm bảo tính ổn định.

C++

vector<int> output(arr.size());
for (int i = arr.size() - 1; i >= 0; i--) {
    int num = arr[i];
    int pos = --count[num - minVal]; // Giảm count trước, lấy vị trí
    output[pos] = num;
}

Giải thích từng phần tử (theo thứ tự duyệt ngược):

Phần Tử	Giá Trị	Index trong `count`	`count` trước khi giảm	Vị Trí `pos`	Mảng `output` sau mỗi bước
1	1	0	count[0] = 2 → 1	1	[, 1, , , , , ]
3	3	2	count[2] = 5 → 4	4	[, 1, , , 3, , _]
2	2	1	count[1] = 4 → 3	3	[, 1, , 2, 3, , ]
4	4	3	count[3] = 7 → 6	6	[, 1, , 2, 3, _, 4]
2	2	1	count[1] = 3 → 2	2	[, 1, 2, 2, 3, , 4]
1	1	0	count[0] = 1 → 0	0	[1, 1, 2, 2, 3, _, 4]
4	4	3	count[3] = 6 → 5	5	[1, 1, 2, 2, 3, 4, 4]

Kết quả: output = [1, 1, 2, 2, 3, 4, 4] ✨

7. Tại Sao Phải Duyệt Từ Cuối? 🔄

Giữ nguyên thứ tự của các phần tử bằng nhau (tính ổn định).
Ví dụ: Hai số 4 cuối cùng trong input được đặt vào vị trí 5 và 6 trong output, đảm bảo thứ tự ban đầu.

8. Code Hoàn Chỉnh 🖥️

C++

void countingSort(vector<int>& arr) {
    if (arr.empty()) return;

    // Bước 1: Tìm phạm vi giá trị
    int minVal = *min_element(arr.begin(), arr.end());
    int maxVal = *max_element(arr.begin(), arr.end());
    int range = maxVal - minVal + 1;

    // Bước 2: Đếm tần suất
    vector<int> count(range, 0);
    for (int num : arr) {
        count[num - minVal]++;
    }

    // Bước 3: Tính vị trí tích lũy
    for (int i = 1; i < range; i++) {
        count[i] += count[i - 1];
    }

    // Bước 4: Xây dựng mảng đầu ra
    vector<int> output(arr.size());
    for (int i = arr.size() - 1; i >= 0; i--) {
        int num = arr[i];
        output[--count[num - minVal]] = num;
    }

    // Gán lại mảng gốc
    arr = output;
}

9. Độ Phức Tạp ⚡

Bước 1, 2, 4: O(n)
Bước 3: O(k) (k là range)
Tổng: O(n + k)

Kết Luận: Counting Sort như một “thợ xây” thông minh, dùng bản đồ tần suất (count array) để sắp xếp chính xác từng viên gạch (phần tử) vào đúng vị trí! 🧱✨

Đây là một ví dụ chi tiết về Radix Sort:

3. Radix Sort – “Sắp Xếp Từng Chữ Số” 🔢

Radix Sort là một thuật toán sắp xếp dựa trên các chữ số của các phần tử trong mảng. Nó sắp xếp các phần tử từ chữ số thấp nhất (đơn vị) lên cao nhất (hàng trăm, hàng nghìn, v.v.). Đặc biệt, thuật toán này sử dụng Counting Sort như một phần của quá trình sắp xếp.

3.1. Visual Process 🎯

Mảng ban đầu:
[170, 45, 75, 90, 802]

Bước 1 (đơn vị):
Chúng ta sắp xếp theo chữ số ở vị trí đơn vị (ones place). Sau khi sắp xếp, mảng trở thành:
[170, 90, 802, 45, 75]

Bước 2 (chục):
Tiếp theo, chúng ta sắp xếp theo chữ số ở vị trí chục (tens place). Sau khi sắp xếp, mảng trở thành:
[802, 45, 70, 75, 90]

Bước 3 (trăm):
Cuối cùng, chúng ta sắp xếp theo chữ số ở vị trí trăm (hundreds place). Sau khi sắp xếp, mảng cuối cùng trở thành:
[45, 70, 75, 90, 802]

3.2. Elegant Implementation ✨

C++

void radixSort(vector<int>& arr) {
    // Tìm số lớn nhất để xác định số chữ số cần xét
    int maxNum = *max_element(arr.begin(), arr.end());

    // Thực hiện Counting Sort cho từng chữ số (đơn vị, chục, trăm,...)
    for (int exp = 1; maxNum / exp > 0; exp *= 10) {
        countingSortByDigit(arr, exp);

        // Minh họa sau mỗi lần sắp xếp:
        // exp = 1:   [170,90,802,45,75]
        // exp = 10:  [802,45,70,75,90]
        // exp = 100: [45,70,75,90,802]
    }
}

Trong đoạn mã trên:

max_element(arr.begin(), arr.end()) được sử dụng để tìm số lớn nhất trong mảng, từ đó xác định số chữ số cần xét (ví dụ: nếu số lớn nhất là 802, chúng ta sẽ phải xét 3 chữ số: hàng đơn vị, hàng chục và hàng trăm).
countingSortByDigit là một hàm sắp xếp Counting Sort được sử dụng để sắp xếp các phần tử dựa trên chữ số tại vị trí đang xét (ví dụ: đơn vị, chục, trăm).

Chú ý rằng thuật toán này có thể được tối ưu hóa thêm, nhưng nhìn chung, đây là cách thực hiện cơ bản của Radix Sort.

4. Algorithm Selection Guide 🎯

Khi nào dùng thuật toán nào? 🤔


Heap Sort:         Counting Sort:     Radix Sort:
🎯 O(nlogn)       🎯 O(n+k)          🎯 O(d*(n+k))
🎯 In-place       🎯 Ổn định         🎯 Ổn định
🎯 Không tốn bộ nhớ phụ 🎯 Phạm vi nhỏ 🎯 Số cố định

Performance Visualization 📊

Hiệu suất trực quan 📊

Sử dụng bộ nhớ:
┌─────────────┐
│Heap     O(1)│ █
│Counting O(k)│ ████
│Radix   O(n) │ █████
└─────────────┘

Tốc độ (trung bình):
┌─────────────┐
│Heap    nlogn│ ████
│Counting  n+k│ ██
│Radix  d(n+k)│ ███
└─────────────┘

Best Use Cases 🎯

Heap Sort:
✅ Giới hạn bộ nhớ
✅ Cần đảm bảo O(nlogn)
✅ Cần sắp xếp tại chỗ (in-place)

Counting Sort:
✅ Phạm vi số nhỏ
✅ Cần sắp xếp ổn định
✅ Dữ liệu là số nguyên hoặc ký tự

Radix Sort:
✅ Số nguyên có độ dài cố định
✅ Cần sắp xếp ổn định
✅ Có thể đánh đổi bộ nhớ lấy tốc độ

Chúc các bạn học vui! May your arrays always be sorted! 🚀