[C]. Hàm qsort()

1. Hàm Qsort()

Hàm qsort() nằm trong thư viện stdlib.h được cài đặt bằng thuật toán tối ưu và rất phổ biến là thuật toán sắp xếp nhanh - Quick sort.

Thông thường để thực hiện sắp mảng, dãy số thì bạn phải tự cài đặt các thuật toán này hoặc sử dụng hàm có sẵn.

Khuôn mẫu hàm qsort : qsort(array, elements, size, comparison_function)

Trong đó :

array : Mảng mà bạn muốn sắp xếp
elements : Số lượng phần tử trong mảng mà bạn muốn sắp xếp
size : Kích thước theo byte của 1 phần tử trong mảng
comparison_function : Hàm so sánh thể hiện logic mà bạn muốn sắp xếp

Hàm qsort() sẽ sắp xếp các phần tử trong mảng của bạn theo logic trong hàm so sánh, mình hay gọi là comparator hay comparison function.

Khuôn mẫu comparison function : int comparator(const void* ptr1, const void* ptr2);

Hàm này có kiểu trả về là số int và có 2 tham số là 2 con trỏ kiểu void. Khi sắp xếp bạn cần ép 2 con trỏ này sang con trỏ có kiểu dữ liệu phù hợp với mảng mà bạn muốn sắp xếp

Hàm này có giá trị trả về dựa vào logic sau :

< 0 : Nếu phần tử được trỏ bởi con trỏ ptr1 đứng trước phần tử được trỏ bởi con trỏ ptr2
= 0 : Nếu phần tử được trỏ bởi con trỏ ptr1 bằng phần tử được trỏ bởi con trỏ ptr2
> 0 : Nếu phần tử được trỏ bởi con trỏ ptr1 đứng sau phần tử được trỏ bởi con trỏ ptr2

Ví dụ 1 : Sắp xếp các phần tử trong mảng tăng, giảm dần

#include "stdio.h"
#include "stdlib.h"

//Hàm so sánh
int cmp1(const void *ptr1, const void *ptr2){
    //Ép kiểu
    int *x = (int*)ptr1;
    int *y = (int*)ptr2;
    if(*x < *y){
        return -1;
    }
    else{
        return 1;
    }
    //return *x - *y sẽ nhanh hơn
}

int cmp2(const void *ptr1, const void *ptr2){
    //Ép kiểu
    int *x = (int*)ptr1;
    int *y = (int*)ptr2;
    if(*x > *y){
        return -1;
    }
    else{
        return 1;
    }
    //return *y - *x sẽ nhanh hơn
}

int main(){
    int n = 10;
    int a[10] = {3, 1, 2, 4, 5, 9, 8, 7, 10, 6};
    printf("Mang sap tang dan : ");
    qsort(a, n, sizeof(int), cmp1);
    for(int i = 0; i < n; i++){
        printf("%d ", a[i]);
    }
    printf("\nMang sap giam dan : ");
    qsort(a, n, sizeof(int), cmp2);
    for(int i = 0; i < n; i++){
        printf("%d ", a[i]);
    }
}

Output :

Mang sap tang dan : 1 2 3 4 5 6 7 8 9 10 
Mang sap giam dan : 10 9 8 7 6 5 4 3 2 1

Giải thích :

Khi bạn sắp xếp tăng dần thì phần tử đứng trước phải nhỏ hơn phần tử đứng sau, khi đó *x là giá trị trỏ bởi con trỏ x nếu nhỏ hơn *y là giá trị trỏ bởi con trỏ y hàm so sánh sẽ trả về số âm, mình thường lấy là -1, các giá trị âm khác cũng được chấp nhận.

Ngược lại thì bạn trả về số dương, với việc sắp xếp tăng dần thì bạn chỉ cần return về *x - *y khi đó nếu *x < *y thì hàm sẽ trả về số âm để cho x đứng trước y, ngược lại nếu *x > *y thì hàm sẽ trả về số dương để x đứng sau y, khi *x = *y thì phần tử nào đứng trước cũng được vì nó bằng nhau.

Khi sắp tăng dần mình thường return *x - *y còn khi sắp giảm dần thì return *y - *x

2. Ví Dụ Với Hàm Qsort()

Ví dụ 1 : Sắp xếp theo trị tuyệt đối tăng dần

#include "stdio.h"
#include "stdlib.h"
#include "math.h"

int cmp1(const void *ptr1, const void *ptr2){
    int *x = (int*)ptr1;
    int *y = (int*)ptr2;
    return abs(*x) - abs(*y);
}

int main(){
    int n = 10;
    int a[10] = {3, -1, 2, 4, -5, -9, 8, 7, -10, 6};
    printf("Sap xep theo tri tuyet doi tang dan :\n");
    qsort(a, n, sizeof(int), cmp1);
    for(int i = 0; i < n; i++){
        printf("%d ", a[i]);
    }
    return 0;
}

Output :

Sap xep theo tri tuyet doi tang dan :
-1 2 3 4 -5 6 7 8 -9 -10

Ví dụ 2 : Sắp xếp theo tổng chữ số tăng dần

#include "stdio.h"
#include "stdlib.h"
#include "math.h"

int tong(int n){
    int ans = 0;
    while(n){
        ans += n % 10;
        n /= 10;
    }
    return ans;
}

int cmp1(const void *ptr1, const void *ptr2){
    int *x = (int*)ptr1;
    int *y = (int*)ptr2;
    return tong(*x) - tong(*y);
}

int main(){
    int n = 10;
    int a[10] = {6, 111, 19, 876, 300001, 114, 44, 99, 2000, 10};
    printf("Sap xep theo tong chu so tang dan :\n");
    qsort(a, n, sizeof(int), cmp1);
    for(int i = 0; i < n; i++){
        printf("%d ", a[i]);
    }
    return 0;
}

Output :

Sap xep theo tong chu so tang dan :
10 2000 111 300001 114 6 44 19 99 876

Ví dụ 3 : Sắp xếp theo tổng chữ số tăng dần, nếu 2 số có cùng tổng chữ số thì số nhỏ hơn sẽ đứng trước

Đối với sắp xếp mà có nhiêu tiêu chí thì bạn cứ xét tiêu chí chính trước, nếu tiêu chí chính bằng nhau thì xét đến tiêu chí phụ.

#include "stdio.h"
#include "stdlib.h"
#include "math.h"

int tong(int n){
    int ans = 0;
    while(n){
        ans += n % 10;
        n /= 10;
    }
    return ans;
}

int cmp1(const void *ptr1, const void *ptr2){
    int *x = (int*)ptr1;
    int *y = (int*)ptr2;
    if(tong(*x) != tong(*y))
        return tong(*x) - tong(*y);
    else
        return *y - *x;
}

int main(){
    int n = 10;
    int a[10] = {666, 111, 19, 876, 30000, 114, 424, 99, 20001, 10};
    printf("Sap xep tong chu so tang dan\n");
    printf("Neu 2 so cung tong chu so thi sap giam dan : \n");
    qsort(a, n, sizeof(int), cmp1);
    for(int i = 0; i < n; i++){
        printf("%d ", a[i]);
    }
    return 0;
}

Output :

Sap xep tong chu so tang dan
Neu 2 so cung tong chu so thi sap giam dan : 
10 30000 20001 111 114 424 19 666 99 876

Ví dụ 4 : Sắp xếp mảng sao cho số chẵn đứng trước, lẻ đứng sau, chẵn tăng dần và lẻ giảm dần

#include "stdio.h"
#include "stdlib.h"
#include "math.h"

int cmp1(const void *ptr1, const void *ptr2){
    int *x = (int*)ptr1;
    int *y = (int*)ptr2;
    int r1 = (*x) % 2, r2 = (*y) % 2;
    if(r1 == 0 && r2 == 0)
        return *x - *y;
    if(r1 == 1 && r2 == 1)
        return *y - *x;
    if(r1 == 0 && r2 == 1)
        return -1;
    return 1;
}

int main(){
    int n = 10;
    int a[10] = {6, 1, 2, 3, 4, 10, 9, 8, 7, 5};
    printf("Sap xep chan truoc, le sau, chan tang dan, le giam dan :\n");
    qsort(a, n, sizeof(int), cmp1);
    for(int i = 0; i < n; i++){
        printf("%d ", a[i]);
    }
    return 0;
}

Output :

Sap xep chan truoc, le sau, chan tang dan, le giam dan :
2 4 6 8 10 9 7 5 3 1

Ví dụ 5 : Sắp xếp các kí tự trong mảng ký tự theo thứ tự từ điển tăng dần

Nếu bạn chưa học chuỗi ký tự thì tham khảo nội dung đó trước nhé

#include "stdio.h"
#include "stdlib.h"
#include "string.h"

int cmp1(const void *ptr1, const void *ptr2){
    char *x = (char*)ptr1;
    char *y = (char*)ptr2;
    return *x - *y;
}

int main(){
    char c[1000] = "28tech_c_programming@@@@abcdzzzz";
    qsort(c, strlen(c), sizeof(char), cmp1);
    printf("%s\n", c);
    return 0;
}

Output :

28@@@@__aabcccdegghimmnoprrtzzzz

Ví dụ 6 : Sắp xếp sinh viên theo gpa giảm dần

Nếu bạn chưa học struct thì tham khảo nội dung đó trước nhé

#include "stdio.h"
#include "stdlib.h"
#include "string.h"

struct SinhVien{
    char ten[100];
    char lop[50];
    double gpa;
};

typedef struct SinhVien SinhVien;

int cmp1(const void *ptr1, const void *ptr2){
    SinhVien *x = (SinhVien*)ptr1;
    SinhVien *y = (SinhVien*)ptr2;
    if(x->gpa > y->gpa)
        return -1;
    else return 1;
}

int main(){
    int n; 
    printf("Nhap so luong sinh vien : ");
    scanf("%d", &n);
    SinhVien a[n];
    for(int i = 0; i < n; i++){
        getchar();
        printf("Nhap ten : ");
        gets(a[i].ten);
        printf("Nhap lop : ");
        gets(a[i].lop);
        printf("Nhap diem : ");
        scanf("%lf", &a[i].gpa);
    }
    qsort(a, n, sizeof(SinhVien), cmp1);
    printf("Danh sach sinh vien : ");
    for(int i = 0; i < n; i++){
        printf("%s %s %.2lf\n", a[i].ten, a[i].lop, a[i].gpa);
    }
    return 0;
}

Input :

3
28tech.com.vn
CNTT1
2.5
blog.28tech.com.vn
DTVT1
3.2
khoahoc.28tech.com.vn
CNTT3
2.7

Output :

blog.28tech.com.vn DTVT1 3.20
khoahoc.28tech.com.vn CNTT3 2.70
28tech.com.vn CNTT1 2.50

Xem thêm video bài giảng của mình về hàm qsort() :

JYLrHJrep2c