C++ Quicksort

C++ Quicksort: Cách khởi tạo và sử dụng

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 😀

facebook
Seth Phát

Seth Phát

Mình là Phát - biệt danh Seth Phát. Hiện đang là một Sr. Full-Stack Engineer. Mình là một người yêu thích và đam mê lập trình và hiện tại đang theo về phần Web là chủ yếu. Mạnh Back-end và khá Front-end, vẫn đang theo đều cả 2 :v. Còn gì bằng khi được làm những thứ mà mình yêu thích, đam mê ;)

Bình luận qua Facebook