Advanced Sorting Algorithms (Day 33) | FE Master

🎯 Nhanh hơn, Mạnh mẽ hơn: O(N log N)

Khi dữ liệu lên đến hàng triệu dòng, O(N²) của Bubble Sort là thảm họa. Chúng ta cần những thuật toán "Chia để trị" (Divide & Conquer) thông minh hơn.

1. Quick Sort (Sắp xếp Nhanh) - "Chia để trị"

Đây là thuật toán phổ biến nhất thế giới (Hàm Arrays.sort() trong Java hay C++ thường dùng nó hoặc biến thể của nó).

Chiến thuật: Chọn Pivot (Trục).

B1: Chọn 1 phần tử làm Pivot (thường là số ở giữa hoặc cuối).
B2: Partition (Phân hoạch): Đá tất cả những thằng NHỎ hơn Pivot sang trái. Đá tất cả những thằng LỚN hơn Pivot sang phải.
B3: Lúc này Pivot đã nằm CHUẨN XÁC ở vị trí cuối cùng của nó.
B4: Gọi đệ quy làm lại B1-B3 cho nửa bên trái và nửa bên phải.

graph TD A[Pivot = 4
Arr = 5, 2, 6, 1, 4, 3] -- Partition --> B[2, 1, 3] A -- Partition --> C[Pivot=4] A -- Partition --> D[5, 6] style C fill:#f9f,stroke:#333

Điểm yếu của Quick Sort:

Nó là Unstable Sort (Không ổn định). Ví dụ có hai số 5 (5a và 5b). Sau khi Quick Sort, có thể 5b lại đứng trước 5a. Điều này không tốt nếu bạn đang sort Excel nhiều cột.

Worst Case (Xấu nhất): O(N²). Xảy ra khi mảng đã sắp xếp sẵn mà ta lại chọn Pivot là phần tử đầu/cuối.

2. Merge Sort (Sắp xếp Trộn)

Chiến thuật: "Chia nhỏ rồi gộp lại".

B1: Cắt đôi mảng ra. Cắt mãi cho đến khi mỗi mảng con chỉ còn 1 phần tử.
B2: Merge (Trộn): Lấy 2 mảng con đã sắp xếp, trộn chúng lại thành 1 mảng to hơn cũng đã sắp xếp.

Ví dụ Trộn:

Mảng 1: [1, 3, 5]. Mảng 2: [2, 4, 6].
So sánh đầu 2 mảng: 1 < 2 -> Lấy 1.
Còn lại [3, 5] và [2, 4, 6]. So 3 với 2 -> Lấy 2.
Còn lại [3, 5] và [4, 6]. So 3 với 4 -> Lấy 3.
... Kết quả: [1, 2, 3, 4, 5, 6].

Ưu điểm Merge Sort:

Luôn luôn là O(N log N) bất kể trường hợp xấu nhất. Và nó là Stable Sort (Ổn định). Rất phù hợp để sort Linked List.

Nhược điểm: Tốn RAM (Space Complexity O(N)) vì cần mảng phụ để chứa dữ liệu lúc trộn.

3. Heap Sort (Sắp xếp Vun đống)

Dùng cấu trúc dữ liệu Binary Heap (Cây nhị phân hoàn chỉnh).

Max Heap: Cha luôn lớn hơn Con. -> Gốc (Root) là số to nhất thế giới.
Quy trình sort:
1. Biến mảng thành Max Heap.
2. Lấy thằng Gốc (Max) ra, vứt xuống cuối mảng.
3. Vun lại cây Heap cho phần còn lại.
4. Lặp lại.

Ưu điểm: Nhanh O(N log N), không tốn RAM phụ như Merge Sort, không bị O(N²) như Quick Sort. Một sự lựa chọn an toàn.

🎯 Nhanh hơn, Mạnh mẽ hơn: O(N log N)

Khi dữ liệu lên đến hàng triệu dòng, O(N²) của Bubble Sort là thảm họa. Chúng ta cần những thuật toán "Chia để trị" (Divide & Conquer) thông minh hơn.

1. Quick Sort (Sắp xếp Nhanh) - "Chia để trị"

Đây là thuật toán phổ biến nhất thế giới (Hàm Arrays.sort() trong Java hay C++ thường dùng nó hoặc biến thể của nó).

Chiến thuật: Chọn Pivot (Trục).

B1: Chọn 1 phần tử làm Pivot (thường là số ở giữa hoặc cuối).
B2: Partition (Phân hoạch): Đá tất cả những thằng NHỎ hơn Pivot sang trái. Đá tất cả những thằng LỚN hơn Pivot sang phải.
B3: Lúc này Pivot đã nằm CHUẨN XÁC ở vị trí cuối cùng của nó.
B4: Gọi đệ quy làm lại B1-B3 cho nửa bên trái và nửa bên phải.

graph TD A[Pivot = 4
Arr = 5, 2, 6, 1, 4, 3] -- Partition --> B[2, 1, 3] A -- Partition --> C[Pivot=4] A -- Partition --> D[5, 6] style C fill:#f9f,stroke:#333

Điểm yếu của Quick Sort:

Worst Case (Xấu nhất): O(N²). Xảy ra khi mảng đã sắp xếp sẵn mà ta lại chọn Pivot là phần tử đầu/cuối.

2. Merge Sort (Sắp xếp Trộn)

Chiến thuật: "Chia nhỏ rồi gộp lại".

B1: Cắt đôi mảng ra. Cắt mãi cho đến khi mỗi mảng con chỉ còn 1 phần tử.
B2: Merge (Trộn): Lấy 2 mảng con đã sắp xếp, trộn chúng lại thành 1 mảng to hơn cũng đã sắp xếp.

Ví dụ Trộn:

Mảng 1: [1, 3, 5]. Mảng 2: [2, 4, 6].
So sánh đầu 2 mảng: 1 < 2 -> Lấy 1.
Còn lại [3, 5] và [2, 4, 6]. So 3 với 2 -> Lấy 2.
Còn lại [3, 5] và [4, 6]. So 3 với 4 -> Lấy 3.
... Kết quả: [1, 2, 3, 4, 5, 6].

Ưu điểm Merge Sort:

Luôn luôn là O(N log N) bất kể trường hợp xấu nhất. Và nó là Stable Sort (Ổn định). Rất phù hợp để sort Linked List.

Nhược điểm: Tốn RAM (Space Complexity O(N)) vì cần mảng phụ để chứa dữ liệu lúc trộn.

3. Heap Sort (Sắp xếp Vun đống)

Dùng cấu trúc dữ liệu Binary Heap (Cây nhị phân hoàn chỉnh).

Max Heap: Cha luôn lớn hơn Con. -> Gốc (Root) là số to nhất thế giới.
Quy trình sort:
1. Biến mảng thành Max Heap.
2. Lấy thằng Gốc (Max) ra, vứt xuống cuối mảng.
3. Vun lại cây Heap cho phần còn lại.
4. Lặp lại.

Ưu điểm: Nhanh O(N log N), không tốn RAM phụ như Merge Sort, không bị O(N²) như Quick Sort. Một sự lựa chọn an toàn.

Thuật toán Sắp xếp Nâng cao (Advanced Sorting)

lesson.content.title

🎯 Nhanh hơn, Mạnh mẽ hơn: O(N log N)

1. Quick Sort (Sắp xếp Nhanh) - "Chia để trị"

Điểm yếu của Quick Sort:

2. Merge Sort (Sắp xếp Trộn)

Ưu điểm Merge Sort:

3. Heap Sort (Sắp xếp Vun đống)

Thuật toán Sắp xếp Nâng cao (Advanced Sorting)

lesson.content.title

🎯 Nhanh hơn, Mạnh mẽ hơn: O(N log N)

1. Quick Sort (Sắp xếp Nhanh) - "Chia để trị"

Điểm yếu của Quick Sort:

2. Merge Sort (Sắp xếp Trộn)

Ưu điểm Merge Sort:

3. Heap Sort (Sắp xếp Vun đống)