Bạn đang tìm hiểu về thuật toán sắp xếp và muốn nắm vững Quick Sort trong C++? Bài viết này sẽ hướng dẫn bạn một cách chi tiết và dễ hiểu, từ khái niệm cơ bản đến ví dụ minh họa cụ thể, giúp bạn tự tin áp dụng Quick Sort vào các dự án của mình.
I. Quick Sort là gì?
Quick Sort, hay thuật toán sắp xếp nhanh, là một thuật toán quan trọng và phổ biến trong lập trình. Vậy Quick Sort hoạt động như thế nào? Nó dựa trên nguyên tắc “chia để trị” (Divide and Conquer), tức là chia một bài toán lớn thành các bài toán nhỏ hơn, dễ giải quyết hơn, rồi gộp kết quả lại.
Hình ảnh minh họa Quick Sort
Cụ thể, Quick Sort chọn một phần tử trong mảng làm “điểm đánh dấu” (pivot). Sau đó, mảng được chia thành hai mảng con: một mảng chứa các phần tử nhỏ hơn hoặc bằng pivot, và mảng còn lại chứa các phần tử lớn hơn pivot. Quá trình này được lặp lại đệ quy trên hai mảng con cho đến khi toàn bộ mảng được sắp xếp.
Việc chọn pivot ảnh hưởng đến hiệu suất của Quick Sort. Một số cách chọn pivot phổ biến bao gồm:
- Chọn phần tử đầu tiên của mảng.
- Chọn phần tử cuối cùng của mảng.
- Chọn phần tử ở giữa mảng.
- Chọn ngẫu nhiên một phần tử.
II. Giải Thuật Quick Sort
Giải thuật Quick Sort bao gồm các bước sau:
- Chọn điểm đánh dấu (pivot): Thường chọn phần tử cuối cùng của mảng cho đơn giản.
- Phân chia mảng: Sử dụng hai con trỏ, một từ đầu mảng (trái) và một từ cuối mảng (phải), di chuyển về phía nhau. Nếu phần tử tại con trỏ trái nhỏ hơn pivot, di chuyển con trỏ trái sang phải. Nếu phần tử tại con trỏ phải lớn hơn pivot, di chuyển con trỏ phải sang trái. Khi cả hai con trỏ dừng lại, hoán đổi vị trí hai phần tử nếu phần tử trái nhỏ hơn pivot và phần tử phải lớn hơn pivot. Tiếp tục quá trình này cho đến khi hai con trỏ gặp nhau.
- Sắp xếp mảng con: Sau khi phân chia, pivot nằm đúng vị trí. Áp dụng đệ quy Quick Sort cho hai mảng con, một bên trái pivot và một bên phải pivot.
III. Cài Đặt Quick Sort trong C++
1. Hàm Partition
Hàm Partition là cốt lõi của Quick Sort. Nó thực hiện việc phân chia mảng và trả về vị trí của pivot sau khi phân chia.
Minh họa hàm Partition
2. Hàm Swap
Hàm Swap đơn giản là hoán đổi vị trí của hai phần tử.
{width=800 height=215}3. Hàm Quick Sort
Hàm QuickSort gọi đệ quy hàm Partition để sắp xếp toàn bộ mảng.
Minh họa hàm Quick Sort
IV. Ví Dụ Minh Họa
Để rõ hơn, hãy xem ví dụ sắp xếp mảng arr[] = {9, -3, 5, 2, 6, 8, -6, 1, 3} theo thứ tự tăng dần bằng Quick Sort.
Input và Output của ví dụ
Chi tiết code C++ bạn có thể tham khảo tại: Thuật toán sắp xếp nhanh (Quick Sort) – Freetuts
V. Kết Luận
Quick Sort là một thuật toán sắp xếp hiệu quả và được sử dụng rộng rãi. Hy vọng bài viết này đã giúp bạn hiểu rõ hơn về Quick Sort và cách cài đặt nó trong C++. Hãy luyện tập và áp dụng Quick Sort vào các bài toán thực tế để nâng cao kỹ năng lập trình của bạn. Đừng quên khám phá thêm các thuật toán sắp xếp khác để mở rộng kiến thức nhé!
