Sắp xếp và tìm kiếm nhanh với mảng trong C

[Nguyễn Bá Ngọc/ 29-11-2023]

C được thiết kế tối giản, và có thể người lập trình C thường ưa thích tự triển khai các thành phần cần thiết, vì vậy có rất ít cấu trúc dữ liệu và thuật toán được cung cấp trong các thư viện chuẩn. Mảng hiện vẫn đang là cấu trúc dữ liệu tra cứu duy nhất sẵn có trong C và cũng chỉ có rất ít thuật toán xử lý thông dụng nhất được cung cấp. Trong bài viết này chúng ta sẽ tìm hiểu cách sắp xếp mảng bằng hàm qsort và tìm kiếm nhanh trong mảng đã sắp xếp bằng hàm bsearch. Cả 2 hàm đều nằm trong stdlib.h.

1.1. Tổng quan về qsort

1.2. Sắp xếp mảng int theo thứ tự tăng dần và giảm dần

1.3. Sắp xếp danh sách chuỗi ký tự được biểu diễn như mảng 2 chiều

1.4. Sắp xếp danh sách chuỗi ký tự cấp phát động

1.5. Quan sát

1.6. Ví dụ tự giải

2. Tìm kiếm nhanh trên mảng đã sắp xếp với bsearch

2.1. Tổng quan về bsearch

2.2. Tìm kiếm nhị phân trên mảng số nguyên

2.3. Quan sát

1. Sắp xếp mảng với qsort

1.1. Tổng quan về qsort

Tuy có thể có những giải thuật khác nhau phù hợp nhất với đặc điểm phân bố dữ liệu của các phần tử mảng và yêu cầu của từng bài toán cụ thể. Nhưng nếu không có lý do đặc biệt nào thì sắp xếp nhanh vơi qsort có thể là 1 lựa chọn mặc định thích hợp.

Hàm qsort được thiết kế với giao diện khái quát cùng với với khả năng mở rộng để có thể sắp xếp bất kỳ mảng 1 chiều nào. Nguyên mẫu giản lược như sau:

void qsort (void *base, size_t nmemb, size_t size, __compar_fn_t compar);

Trong đó:

base - là con trỏ tới byte đầu tiên của mảng.

nmemb - là số lượng phần tử của mảng.

size - là kích thước 1 phần tử của mảng.

compar - là con trỏ hàm so sánh 2 phần tử của mảng.

Các tham số base, nmemb và size hợp thành 1 biểu diễn khái quát, tương thích với tất cả các mảng 1 chiều. So sánh các phần tử mảng trong tiến trình sắp xếp được thực hiện với hàm compar. Con trỏ hàm compar có thể được coi như điểm mở rộng của hàm qsort. Nhờ có cơ chế mở rộng nên hàm qsort có thể sắp xếp mảng 1 chiều bất kỳ theo nhiều thứ tự khác nhau nhưng không cần thay đổi mã nguồn mà chỉ cần truyền vào hàm so sánh thích hợp.

Tham số compar có kiểu __compar_fn_t là kiểu con trỏ hàm được định nghĩa như sau:

typedef int (*__compar_fn_t) (const void *, const void *);

Đối số cho compar phải là con trỏ tới hàm nhận 2 tham số có kiểu const void *, và trả về giá trị kiểu int. Trong tiến trình xử lý qsort sẽ gọi hàm được trỏ tới bởi compar để so sánh các phần tử mảng, qsort truyền 2 đối số là các con trỏ tới các phần tử cần được so sánh của mảng. Để sắp xếp tăng dần hàm so sánh phải trả về giá trị theo định dạng tương tự hàm strcmp: Nếu giá trị thứ nhất < giá trị thứ 2 thì trả về 1 số âm; Nếu giá trị thứ nhất > giá trị thứ 2 thì trả về 1 số dương; Nếu ngược lại ̶ nếu 2 giá trị bằng nhau thì trả về 0. Để sắp xếp giảm dần thì hàm so sánh phải đảo dấu các giá trị trả về (hoặc đảo vị trí các tham số) so với hàm so sánh để sắp xếp tăng dần.

Để sắp xếp mảng với qsort về cơ bản chỉ cần viết hàm so sánh, công việc này đơn giản hơn nhiều so với việc điều chỉnh triển khai của chính hàm qsort theo từng yêu cầu sắp xếp. Để minh họa chúng ta xét 1 số trường hợp sắp xếp cơ bản.

1.2. Sắp xếp mảng int theo thứ tự tăng dần và giảm dần

#include <stdlib.h>
int icmp(const void *p1, const void *p2) {
return *(const int*)p1 - *(const int*)p2;
}
int ricmp(const void *p1, const void *p2) {
return *(const int*)p2 - *(const int*)p1;
}
int main() {
int a[] = {3, 1, 2, 5, 9, 8, 10};
int n = sizeof(a)/sizeof(a[0]);
// Sắp xếp tăng dần
qsort(a, n, sizeof(a[0]), icmp);
// Sắp xếp giảm dần
qsort(a, n, sizeof(a[0]), ricmp);
}

Trong câu lệnh gọi hàm qsort ở dòng 13, đối số a khi được truyền cho base được ép kiểu void * tương tự như:

void *base = a; // Biểu thức a có kiểu int * được ép kiểu thành void *

Hàm qsort không biết kiểu của các phần tử của mảng a. Vị trí của phần tử thứ i của mảng a có thể được xác định bằng biểu thức a + i * size.

Đối số icmp được truyền cho tham số compar, vì vậy khi thực hiện dòng 13, mỗi câu lệnh gọi hàm với con trỏ compar trong qsort sẽ kích hoạt hàm icmp.

Bên trong triển khai của hàm qsort mỗi khi cần so sánh 2 phần tử thứ i và thứ j hàm được trỏ tới bởi compar sẽ được gọi với các đối số là các con trỏ tới các phần tử:

const void *p1 = base + i * size;

const void *p2 = base + j * size;

Tương ứng với câu lệnh gọi qsort ở dòng 13 và khai báo mảng a, bên trong hàm icmp chúng ta mong đợi các con trỏ p1 và p2 sẽ trỏ tới các đối tượng kiểu int, đây giống như 1 thỏa thuận giữa người gọi hàm qsort và người triển khai hàm so sánh.

Câu lệnh dòng 13 sắp xếp các phần tử mảng a theo thứ tự tăng dần, còn câu lệnh dòng 16 sắp xếp theo thứ tự giảm dần. Thứ tự tăng dần và giảm dần thu được từ hiệu ứng của các hàm so sánh, trong mục này là icmp và ricmp.

1.3. Sắp xếp danh sách chuỗi ký tự được biểu diễn như mảng 2 chiều

#include <stdlib.h>
#include <string.h>
int s2cmp(const void *p1, const void *p2) {
return strcmp(p1, p2);
}
int main() {
char a[][100] = {"aaaaaa", "ccccccc", "bbbbbb"};
int n = sizeof(a)/sizeof(a[0]);
qsort(a, n, sizeof(a[0]), s2cmp);
}

Trong ví dụ này a là 1 mảng 2 chiều với kích thước chiều thứ nhất được ngầm định = 3. Mảng a có thể được sử dụng như 1 mảng 3 chuỗi ký tự với độ dài không quá 99 ký tự (và 1 phần tử chức năng lưu dấu hiệu kết thúc chuỗi).

Theo quy chuẩn ngôn ngữ C biểu thức a có kiểu char (*)[100] - Kiểu con trỏ tới mảng 100 phần tử char. Biểu thức a được tự động chuyển thành con trỏ tới mảng 1 chiều đầu tiên, điều này đồng nghĩa với a trỏ tới byte đầu tiên của mảng a, sự khác biệt cần quan tâm là kiểu của đối tượng được trỏ tới. Như đã biết mảng 2 chiều trong C có bố cục bộ nhớ hướng dòng và liên tục, vì vậy có thể xử lý a như mảng 1 chiều của các mảng 1 chiều 100 ký tự hoặc mảng 1 chiều của 3 * 100 phần tử char. Trong câu lệnh gọi qsort ở dòng 9 biểu thức a được ép kiểu thành void *.

void *base = a; // base sẽ trỏ vào ký tự đầu tiên của mảng a, con trỏ &a[0][0]

Mảng a được sử dụng cho câu lệnh qsort trên dòng 9 về bản chất là 1 dãy ký tự liên tiếp, vì vậy bên trong hàm s2cmp chúng ta có thể mong đợi các con trỏ p1 và p2 trỏ tới ký tự đầu tiên của các chuỗi thứ i và chuỗi thứ j vì vậy có thể chuyển tiếp tới hàm strcmp. Câu lệnh gọi hàm qsort ở dòng 9 sắp xếp danh sách chuỗi ký tự theo thứ tự bảng mã ASCII và tăng dần.

Với biểu diễn chuỗi ký tự như mảng 2 chiều thì nội dung của các chuỗi ký tự được hoán đổi trong tiến trình sắp xếp, lượng dữ liệu trao đổi lớn, vì vậy kém hiệu quả. Để giảm dung lượng trao đổi dữ liệu chúng ta có thể biểu diễn danh sách chuỗi ký tự với mảng cấp phát động như trong 1.4.

1.4. Sắp xếp danh sách chuỗi ký tự cấp phát động

#include <stdlib.h>
#include <string.h>
int scmp(const void *p1, const void *p2) {
char * const *ps1 = p1,
* const *ps2 = p2;
return strcmp(*ps1, *ps2);
}
int main() {
char **a = malloc(3 * sizeof(char *));
for (int i = 0; i < 3; ++i) {
a[i] = malloc(10);
}
strcpy(a[0], "aaaaaa");
strcpy(a[1], "ccccccc");
strcpy(a[2], "bbbbb");
qsort(a, 3, sizeof(a[0]), scmp);
for (int i = 0; i < 3; ++i) {
free(a[i]);
}
free(a);
}

Trong ví dụ này a là mảng con trỏ char *, mỗi phần tử của a trỏ đến 1 chuỗi ký tự được cấp phát trong bộ nhớ động, các vùng nhớ cho các chuỗi ký tự có thể không liên tục.

Tương ứng với câu lệnh gọi hàm qsort trên dòng 16 và định nghĩa mảng a, trong hàm scmp chúng ta có thể mong đợi các con trỏ p1 và p2 trỏ tới các con trỏ char * là những con trỏ tới các ký tự đầu tiên của các chuỗi cần được so sánh. Kiểu const void * là kiểu con trỏ tới 1 đối tượng chỉ đọc, vì vậy cần ép kiểu p1 và p2 thành char * const * - con trỏ tới 1 con trỏ char * chỉ đọc. Khác với const char ** là kiểu con trỏ tới 1 con trỏ tới 1 đối tượng char chỉ đọc, ép kiểu p1 và p2 thành const char ** sẽ phát sinh vấn đề gỡ bỏ ràng buộc chỉ đọc đối với các đối tượng được p1 và p2 trỏ tới, trình biên dịch có thể đưa ra cảnh báo trong trường hợp này. Sau khi ép kiểu các tham số thành char * const * chúng ta sử dụng toán tử truy cập để lấy các con trỏ tới các chuỗi ký tự cần so sánh.

Trong ví dụ ở mục này chúng ta không thể ép kiểu các tham số của scmp trực tiếp thành const char * như trong s2cmp, và cũng không thể ép kiểu các tham số của s2cmp thành char * const * như trong scmp do sự khác biệt về bố cục bộ nhớ của các chuỗi ký tự.

Với biểu diễn danh sách chuỗi ký tự như trong ví dụ này, trong tiến trình xử lý của hàm qsort hoán đổi các chuỗi ký tự trong danh sách thực chất chỉ là hoán đổi các con trỏ tới các chuỗi ký tự vì vậy hiệu quả hơn biểu diễn như trong mục 1.4. Tuy nhiên các diễn đạt sử dụng khái niệm bậc thấp phức tạp hơn, đó là 1 thể hiện điển hình của việc tối ưu hóa mã nguồn, cái giá phải trả - sự phức tạp cho hiệu năng - chương trình chạy nhanh hơn.

1.5. Quan sát

Hàm qsort xử lý dữ liệu đầu vào như mảng 1 chiều với con trỏ base trỏ tới vị trí bắt đầu của mảng, nmemb là số lượng phần tử mảng và size là kích thước 1 phần tử. Tương ứng với câu lệnh gọi hàm qsort bên trong hàm so sánh có thể mong đợi p1 và p2 là các con trỏ tới các phần tử mảng với giới hạn chỉ đọc.

Nếu phần tử mảng a có kiểu T thì trong hàm so sánh chúng ta có thể ép kiểu các tham số p1 và p2 thành kiểu T const *. Như trong ví dụ 1.2, phần tử mảng a có kiểu int, vì vậy ép kiểu p1 và p2 thành int const * (tương đương const int *) trong hàm icmp và ricmp.

Có thể có đôi chút nhập nhằng về khái niệm con trỏ tới phần tử mảng trong ví dụ trong mục 1.3. Mảng a được khai báo như mảng 2 chiều 3 x 100 của các phần tử kiểu char vì vậy có thể hiểu a như mảng 1 chiều với các phần tử là các mảng char[100]. Nhưng dựa trên bố cục bộ nhớ cũng có thể coi a như mảng 1 chiều 3 * 100 phần tử kiểu char. Nếu hiểu theo cách 1 thì khái niệm con trỏ tới phần tử mảng a có thể được hiểu thành con trỏ kiểu char (*)[100] - con trỏ tới mảng char[100], và trong hàm so sánh s2cmp phải sử dụng toán tử truy cập để lấy các chuỗi cần được so sánh. Nhưng nếu hiểu theo cách 2 thì có thể truyền trực tiếp các con trỏ p1 và p2 cho hàm strcmp.

Thực chất 2 cách hiểu đã nêu về mặt hành vi là tương đương, bởi vì 1 con trỏ khi trỏ tới 1 mảng 1 chiều thì cũng trỏ tới phần tử đầu tiên của mảng đó. Nếu triển khai hàm s2cmp như sau:

int s2cmp2(const void *p1, const void *p2) {

const char (*ps1)[100] = p1, (*ps2)[100] = p2;

return strcmp(*ps1, *ps2);

}

thì kết quả thu được vẫn không thay đổi, nhưng diễn đạt có phần phức tạp hơn. Các biểu thức *ps1 và *ps2 là các mảng của các phần tử chỉ đọc kiểu char vì vậy theo quy ước được tự động chuyển thành các con trỏ const char *.

Trong ví dụ 1.4 kiểu T của các phần tử mảng a là char *, vì vậy thực hiện ép kiểu tham số trong hàm so sánh scmp thành char * const *. Sau đó Thực hiện toán tử truy cập để lấy các con trỏ kiểu char * const (khác với const char *) trỏ tới các chuỗi ký tự cần so sánh.

Như vậy trong hàm so sánh chúng ta có thể mong đợi các con trỏ p1 và p2 trỏ tới các phần tử của mảng đầu vào cho hàm qsort. Các con trỏ được truyền với giới hạn chỉ đọc cho đối tượng được trỏ tới, và cuối cùng kiểu của các phần tử mảng tất nhiên có thể được xác định dựa trên định nghĩa mảng.

1.6. Ví dụ tự giải

Đọc hiểu và thử nghiệm với mã nguồn sắp xếp danh sách nhân viên theo email như sau:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct nhanvien {
int id;
char hoten[128];
char email[128];
};
int cmp_email(const void *p1, const void *p2) {
const struct nhanvien *nv1 = p1, *nv2 = p2;
return strcmp(nv1->email, nv2->email);
}
int main() {
struct nhanvien a[] = {
{1, "Nguyen Van A", "anv@funy.com"},
{2, "Nguyen Van C", "cnv@funy.com"},
{3, "Nguyen Van B", "bnv@funy.com"}};
int n = sizeof(a) / sizeof(a[0]);
qsort(a, n, sizeof(struct nhanvien), cmp_email);
for (int i = 0; i < n; ++i) {
printf("%d | %s | %s\n",
a[i].id, a[i].hoten, a[i].email);
}
}

Câu hỏi: Giải thích vì sao có thể ép kiểu các tham số p1 và p2 của cmp_email thành const struct nhanvien * ?

2. Tìm kiếm nhanh trên mảng đã sắp xếp với bsearch

2.1. Tổng quan về bsearch

Hàm bsearch là triển khai khái quát của giải thuật tìm kiếm nhị phân trên mảng đã sắp xếp. Ở mỗi bước phần tử cần tìm được so sánh với phần tử ở giữa mảng. Sau mỗi bước so sánh không thành công phạm vi tìm kiếm được thu hẹp 1 nửa (vì vậy còn được gọi là tìm kiếm nhị phân). Hàm bsearch có thể tìm kiếm 1 giá trị trong mảng N phần tử đã sắp xếp với độ phức tạp O(log2N), vì vậy còn được gọi là tìm kiếm nhanh.

Hàm bsearch có nguyên mẫu giản lược như sau:

void *bsearch(const void *key, const void *base,

size_t nmemb, size_t size, compar_fn_t compar);

Trong đó:

key - là con trỏ tới khóa tìm kiếm (đối tượng chứa giá trị cần tìm).

base - là con trỏ tới byte đầu tiên của mảng.

nmemb - là số lượng phần tử của mảng.

size - là kích thước 1 phần tử của mảng.

compar - là con trỏ hàm so sánh 2 phần tử của mảng.

Giá trị trả về - Hàm trả về con trỏ tới phần tử mảng có giá trị bằng giá trị của khóa (hàm so sánh trả về 0) nếu tìm thấy, hoặc NULL nếu không tìm thấy.

Tương tự như trong qsort các tham số base, nmemb, size hợp thành biểu diễn khái quát của mảng 1 chiều, cho phép bsearch tiếp nhận bất kỳ mảng 1 chiều nào. Con trỏ hàm compar được sử dụng để trỏ tới hàm so sánh các phần tử, tương tự như đối với qsort, có thể được coi như điểm mở rộng của hàm bsearch.

Hàm bsearch cũng được thiết kế khái quát để có thể sử dụng với tất cả các mảng 1 chiều. Hàm bsearch không biết kiểu của mảng và khóa cần tìm, nó coi phần tử mảng mà hàm compar trả về 0 khi so sánh với khóa là phần tử cần tìm. Trong tiến trình xử lý của bsearch khi gọi hàm compar đối số thứ nhất được đảm bảo là con trỏ key, và đối số thứ 2 là con trỏ tới 1 phần tử của mảng. Để tìm được giá trị trong mảng người gọi hàm bsearch cần tự đảm bảo các phần tử mảng đã được sắp xếp theo thứ tự, và tính phù hợp của hàm được trỏ tới bởi con trỏ hàm compar - thông thường khóa được sử dụng có cùng kiểu với các phần tử mảng (nhưng không bắt buộc) và tương ứng hàm so sánh cũng thường là hàm có thể được sử dụng để sắp xếp mảng theo cùng thứ tự. Để minh họa chúng ta sẽ xét 1 tình huống tìm kiếm trên mảng số nguyên.

2.2. Tìm kiếm nhị phân trên mảng số nguyên

#include <stdio.h>
#include <stdlib.h>
int icmp(const void *p1, const void *p2) {
return *(const int*)p1 - *(const int*)p2;
}
int ricmp(const void *p1, const void *p2) {
return *(const int*)p2 - *(const int*)p1;
}
int main() {
int a[] = {3, 9, 2, 5, 1, 8, 10};
int n = sizeof(a)/sizeof(a[0]);
// Không tìm thấy, r == NULL do mảng chưa sắp xếp
int *r = bsearch((int[]){9}, a, n, sizeof(a[0]), icmp);
qsort(a, n, sizeof(a[0]), icmp);
// Tìm thấy, r - a == 5
r = bsearch((int[]){9}, a, n, sizeof(a[0]), icmp);
// Không tìm thấy, r == NULL do hàm so sánh không phù hợp
r = bsearch((int[]){9}, a, n, sizeof(a[0]), ricmp);
}

Biểu thức (int[]){9} như trong ví dụ là 1 hằng mảng. Chúng ta cần sử dụng hằng mảng trong ví dụ này bởi vì bsearch yêu cầu tham số key phải là 1 con trỏ. Tuy chúng ta không thể lấy con trỏ từ 1 hằng số (ví dụ 9), nhưng chúng ta có thể đưa nó vào mảng 1 chiều như 1 giải pháp thay thế.

Câu lệnh gọi bsearch trên dòng 14 trả về NULL bởi vì mảng a chưa được sắp xếp. Tương ứng với tham số icmp sau lượt so sánh thứ nhất hàm bsearch sẽ tiếp tục tìm kiếm ở nửa bên phải của mảng, vì vậy sẽ không tìm thấy số 9.

Câu lệnh gọi qsort trên dòng 16 sẽ sắp xếp các phần tử mảng theo thứ tự tăng dần. Với mảng đã ở trạng thái sắp xếp và sử dụng cùng hàm so sánh, câu lệnh gọi bsearch trên dòng 19 sẽ trả về con trỏ tới phần tử trong mảng có giá trị = 9. Để chuyển từ con trỏ tới phần tử mảng sang chỉ số mảng chúng ta có thể sử dụng biểu thức r - a. Trong ví dụ này chỉ số của 9 trong mảng a đã sắp xếp tăng dần là 5.

Tuy mảng a đã được sắp xếp tăng dần nhưng câu lệnh gọi bsearch trên dòng 22 trả về NULL, bởi vì hàm ricmp thiết lập thứ tự ngược lại so với icmp. Khi sử dụng hàm ricmp để so sánh các phần tử, sau lượt so sánh thứ nhất trong ví dụ ở mục này hàm bsearch sẽ tiếp tục tìm kiếm ở nửa trái của mảng a đã sắp xếp tăng dần vì vậy không tìm thấy phần tử có giá trị = 9.

2.3. Quan sát

Thiết kế truyền con trỏ tới giá trị khóa có những hạn chế nhất định, điển hình như những trường hợp chúng ta không thể trực tiếp sử dụng hằng số (số nguyên, số thực, v.v..) để tìm kiếm, tuy nhiên vẫn có giải pháp thay thế như đưa giá trị vào 1 hằng mảng 1 chiều để lấy địa chỉ, hoặc sử dụng các biến.

Hàm bsearch chỉ hoạt động đúng nếu các tiền điều kiện được đáp ứng, người lập trình cần đảm bảo các điều kiện cần thiết đối với các đối số được sử dụng cho câu lệnh gọi hàm. Để tìm đúng giá trị trong mảng người lập trình cần đảm bảo mảng đã được sắp xếp, và tính phù hợp của hàm so sánh được trỏ tới bởi con trỏ hàm compar - thông thường khóa được sử dụng thường có cùng kiểu với các phần tử mảng và tương ứng hàm so sánh thường chính là hàm so sánh có thể được sử dụng để sắp xếp mảng theo cùng thứ tự.