Hướng dẫn này minh họa việc sắp xếp các mảng bằng cách sử dụng qsort() chức năng trong C và cũng giúp bạn hiểu nó bằng mã ví dụ C.
qsort() trong C
Thư viện chuẩn C tạo điều kiện cho chúng tôi với qsort() chức năng được sử dụng đơn giản để sắp xếp các mảng. Đây là một chức năng cực kỳ tối ưu và nhanh chóng, có thể hoạt động với bất kỳ mảng kiểu dữ liệu nào.
Header-File sử dụng qsort() trong C
Các qsort() phương thức được định nghĩa bên trong stdlib.h tệp tiêu đề, phải được xác định trước khi triển khai qsort() trong một chương trình C.
#include
Khai báo qsort()
Tuyên bố của qsort() chức năng như sau:
khoảng trống qsort ( khoảng trống * căn cứ , number_of_elements , size_of_element , so sánh_hàm )
Các tham số của hàm qsort()
Các thông số của qsort() chức năng là:
căn cứ: Con trỏ tới phần tử đầu tiên của mảng cần sắp xếp.
số_phần_tử: Số phần tử trong mảng cần sắp xếp.
size_of_element: Kích thước tính bằng byte của từng phần tử trong mảng.
so sánh_chức năng: Con trỏ tới một hàm so sánh xác định thứ tự của các phần tử.
Chức năng so sánh trong qsort() là gì
Hàm so sánh nhận hai tham số, cả hai đều thuộc loại const void*, trỏ đến các phần tử được so sánh. Hàm sẽ trả về một số nguyên nhỏ hơn, bằng hoặc lớn hơn 0, tùy thuộc vào việc phần tử đầu tiên sẽ được sắp xếp tương ứng trước, ở cùng vị trí hay sau phần tử thứ hai.
Cách thức hoạt động của qsort trong C
Các qsort() chức năng hoạt động theo cách sau:
Ghi chú: Ở đây chúng tôi đang xem xét một int arr[] = {5, 2, 8, 3, 1, 9};
1: Ban đầu, hàm qsort sẽ được gọi với các tham số sau:
qsort ( mảng , 6 , kích thước của ( int ) , so sánh_hàm ) ;trong đó arr là con trỏ tới mảng, 6 là số phần tử trong mảng, sizeof(int) là kích thước của từng phần tử trong mảng và hàm so sánh là hàm xác định thứ tự sắp xếp các phần tử.
2: Hàm qsort chọn một phần tử trục. Giả sử nó chọn 3 như trục xoay.
3: Hàm qsort phân vùng mảng thành hai mảng con: {2, 1} và {5, 8, 9}. Mảng con đầu tiên chứa các phần tử nhỏ hơn hoặc bằng trục và mảng con thứ hai chứa các phần tử lớn hơn trục.
4: Hàm qsort gọi đệ quy chính nó trên mỗi mảng con.
5: Hàm qsort chọn các trục cho từng mảng con. Giả sử nó chọn 1 và 8 làm trục.
6: Hàm qsort phân vùng từng mảng con thành hai mảng con khác và tự gọi đệ quy chính nó trên từng mảng con này.
7: Hàm qsort kết hợp các mảng con đã sắp xếp lại thành một mảng được sắp xếp duy nhất: {1, 2} và {5, 8, 9} trở thành {1, 2, 5, 8, 9}.
số 8: Toàn bộ mảng đã sắp xếp được trả về.
Triển khai qsort trong lập trình C
Đoạn mã sau đây cho thấy việc thực hiện qsort hàm trong lập trình C.
#include#include
int so sánh ( hằng số khoảng trống * a1 , hằng số khoảng trống * b1 )
{
trở lại ( * ( int * ) a1 - * ( int * ) b1 ) ;
}
int chủ yếu ( )
{
int Tôi = 0 , trên một = 6 ;
int mảng [ ] = { 5 , 2 , số 8 , 3 , 1 , 9 } ;
qsort ( mảng , trên một , kích thước của ( int ) , so sánh ) ;
bản inf ( 'Các phần tử được sắp xếp của mảng sử dụng qsort() là:' ) ;
vì ( Tôi = 0 ; Tôi < trên một ; Tôi ++ ) {
bản inf ( '%d' , mảng [ Tôi ] ) ; }
trở lại 0 ;
}
Trong đoạn mã trên, trước tiên, một hàm so sánh được tạo với hai tham số a1 Và b1 . Sau đó, quá trình thực thi bắt đầu từ hàm main(). Trong phần chính, chúng ta khởi tạo hai biến số nguyên là i=0 và num=6. Sau đó, chúng tôi khai báo một mảng có sáu phần tử là {5, 2, 8, 3, 1, 9} . Sau đây qsort() có ba tham số kiểu mảng, tham số num cho biết tổng các phần tử của một mảng, kích thước của (int) đề cập đến tổng kích thước của mảng và so sánh được sử dụng để so sánh từng phần tử mảng. Sau đó in ra mảng đã sắp xếp bằng cách sử dụng printf() chức năng trong C
đầu ra
Phần kết luận
qsort là một chức năng mạnh mẽ trong lập trình C để sắp xếp các mảng thuộc bất kỳ loại nào. Nó sử dụng thuật toán quicksort để sắp xếp các phần tử theo thứ tự tăng dần hoặc giảm dần dựa trên hàm so sánh. Hướng dẫn trên chỉ cho bạn một cách dễ dàng để triển khai qsort trong lập trình C với cách làm việc từng bước của qsort thuật toán.