C++ Quicksort: Cách khởi tạo và sử dụng
Hi các bạn,
Như các bạn nếu đã học về môn “Cấu trúc dữ liệu và giải thuật” thì thuật toán này ko xa lạ gì nữa đúng ko?
Nhưng để ta viết luôn 1 hàm để dùng thì nó khá là dài và lâu, phức tạp, không chỉ vậy C++ Library cũng đã có sẵn hàm này, tại sao ta lại ko lấy ra xài luôn nhỉ? 😀
Nên hôm nay mình sẽ hướng dẫn các bạn sử dụng Quicksort của library có sẵn nhé 😀
1/C++ Quicksort: Cơ bản về hàm
qsort(mảng dữ liệu, số lượng sẽ sort, data size, hàm so sánh)
Cụ thể:
- Mảng dữ liệu: 1 mảng [] bình thường hoặc khởi tạo qua con trỏ.
- Số lượng: số lượng phần tử sẽ sort trong mảng.
- Data size: khai báo size của 1 phần tử trong mảng, vd sizeof(int) hoặc sizeof(StructCuaBan)
- Hàm so sánh: sẽnói bên dưới.
Và để sử dụng hàm qsort cơ bản ta chỉ cần 1 dòng như sau:
// ví dụ mảng arr có 50 phần tử, dùng kiểu int
qsort(arr, 50, sizeof(int), cmp);
Vậy để viết hàm so sánh như thế nào, qua phần sau nhé.
Lưu ý: để sử dụng dc hàm này, ta cần phải include thư viện stdlib.h
2/ Hàm so sánh cho qsort
Một hàm so sánh cơ bản dành cho mảng kiểu int:
int cmp(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
Đây là 1 kiểu viết tắt nhanh chóng, nhưng nếu ghi dài ra thì nó sẽ như sau:
int cmp(const void *a, const void *b) {
int aa = *(int*)a;
int bb = *(int*)b;
if (aa > bb) {
return 1;
}
else if (aa < bb) {
return -1;
}
else {
return 0;
}
}
Đây là 1 kiểu sắp xếp từ nhỏ => lớn, nếu sắp xếp lớn đến nhỏ ta chỉ cẩn reverse lại 1 và -1. Và kiểu trả về cho hàm cmp này lúc nào cũng fải là int
Ta cũng có thể sắp xếp cho 1 mảng có cấu trúc như sau:
struct MyTest {
int a, int b;
};
int cmp(const void *a, const void *b) {
MyTest aa = *(MyTest*)a;
MyTest bb = *(MyTest*)b;
if (aa->a > bb->a) {
return 1;
}
else if (aa->a < bb->b) {
return -1;
}
else {
return 0;
}
}
Ngoài ra, ta cũng có thể sắp xếp struct theo 2 tiêu chí, như struct ở trên sẽ là tiêu chí a trước, sau đó tới b:
int cmp2(const void *a, const void *b) {
MyTest aa = *(MyTest*)a;
MyTest bb = *(MyTest*)b;
if (aa->a > bb->a) {
return 1;
}
else if (aa->a < bb->b) {
return -1;
}
else {
if (aa->b > bb->b)
return 1;
else if (aa->b < bb->b)
return -1;
else
return 0;
}
}
Rất đơn giản nhỉ 😀
Các bạn có thể tìm hiểu thêm hàm này tại: http://www.cplusplus.com/reference/cstdlib/qsort/
Cám ơn các bạn đã quan tâm 😀