Ở đây ta sẽ xem khác biệt giữa qsort() trong C và sort() trong C++.
C cung cấp qsort() để sắp xếp mảng. Cú pháp:
void qsort(void *base, size_t num, size_t size, int (*comparator)(const void*, const void*));
Nhận địa chỉ cơ sở mảng, số phần tử, kích thước mỗi phần tử, và hàm so sánh.
C++ cung cấp sort() trong STL. Cú pháp:
void sort(T first, T last, Compare c);
Thứ tự phần tử trùng lặp không được bảo toàn. Để bảo toàn, dùng stable_sort.
Bảng so sánh
| qsort() trong C | sort() trong C++ |
|---|---|
| Sử dụng thuật toán quicksort. | Sử dụng introsort (thuật toán lai). GNU C++ STL dùng introsort, quicksort, insertion sort kết hợp. |
| Chuẩn C không quy định độ phức tạp. | C++11 đảm bảo O(n log n) worst case. Phiên bản cũ O(n²) worst case, trung bình O(n log n). |
| Thời gian chạy lớn hơn sort(). | Thời gian chạy nhỏ hơn qsort(). |
| Không linh hoạt cho nhiều kiểu dữ liệu. | Linh hoạt: sắp xếp mảng C, vector, deque, container khác. |
| Kém an toàn kiểu: dùng con trỏ void không an toàn. | An toàn kiểu hơn: không cần con trỏ void. |