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ẽ giúp bạn hiểu rõ khái niệm, cách thức hoạt động và cách triển khai Quick Sort một cách đơn giản, dễ hiểu, cùng với những ví dụ minh họa cụ thể.
I. Quick Sort là gì?
Quick Sort là một thuật toán sắp xếp hiệu quả, được sử dụng rộng rãi trong lập trình C++. Nó hoạt động dựa trên nguyên lý “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 con nhỏ hơn, giải quyết chúng rồi kết hợp lại thành kết quả cuối cùng.
Quick sort minh họaHình ảnh minh họa cách thức hoạt động của Quick Sort
Cụ thể, Quick Sort chọn một phần tử trong mảng làm “điểm tựa” (pivot). Sau đó, nó sắp xếp lại mảng sao cho các phần tử nhỏ hơn pivot nằm bên trái, còn các phần tử lớn hơn pivot nằm bên phải. 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 lựa 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 hoặc cuối cùng của mảng.
- Chọn phần tử ở giữa mảng.
- Chọn phần tử ngẫu nhiên.
II. Giải thuật Quick Sort
Giải thuật Quick Sort có thể được tóm tắt như sau:
- Chọn điểm tựa (pivot): Thường chọn phần tử cuối cùng của mảng.
- Phân hoạch (Partition): Sắp xếp lại mảng sao cho các phần tử nhỏ hơn pivot nằm bên trái, còn các phần tử lớn hơn pivot nằm bên phải.
- Đệ quy: Áp dụng Quick Sort lên hai mảng con bên trái và bên phải pivot.
Minh họa hàm PartitionMinh họa hàm Partition trong Quick Sort
III. Triển khai Quick Sort trong C++
1. Cấu trúc thuật toán
Để triển khai Quick Sort, chúng ta cần hai hàm chính:
- Hàm
partition: Nhận đầu vào là mảng, chỉ số bắt đầu và kết thúc. Hàm này sẽ phân hoạch mảng theo pivot và trả về vị trí mới của pivot.
Minh họa hàm quickSortMinh họa hàm quickSort
- Hàm
quickSort: Nhận đầu vào là mảng, chỉ số bắt đầu và kết thúc. Hàm này sẽ gọi đệ quy hàmpartitionđể sắp xếp mảng.
Ngoài ra, ta cũng cần hàm swap để đổi chỗ hai phần tử trong mảng.
Minh họa hàm swapMinh họa hàm swap
2. Ví dụ minh họa
Để hiểu rõ hơn, chúng ta hãy xem xét 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ạn có thể tham khảo code C++ đầy đủ tại Thuật toán sắp xếp nhanh (Quick Sort) – Freetuts.
Input và Output của ví dụ
IV. Kết luận
Quick Sort là một thuật toán sắp xếp mạnh mẽ và hiệu quả. Hy vọng bài viết này đã giúp bạn hiểu rõ về Quick Sort và cách triển khai nó trong C++. Hãy thực hành và áp dụng Quick Sort vào các dự án của bạn để nâng cao kỹ năng lập trình. Để tìm hiểu thêm về các thuật toán và cấu trúc dữ liệu khác, bạn có thể tham khảo các bài viết liên quan như:
