Triển khai (phần 1)
Bài học 5 trên 9 trong khóa học Sắp xếp đếm, chuỗi DSA của Coddy.
Chúng ta sẽ xây dựng thuật toán Counting Sort, bắt đầu từ giai đoạn đếm.
Thử thách
DễGiai đoạn đầu tiên của Counting Sort là đếm số lần mỗi giá trị xuất hiện. Hãy cùng xây dựng hàm đó.
Viết một hàm (function) tên là countOccurrences, nhận một mảng (array) gồm các số nguyên không âm arr (mọi giá trị đều nằm trong khoảng từ 0 đến k - 1) và một số nguyên k, rồi trả về một mảng có độ dài k, trong đó vị trí v lưu số lần v xuất hiện trong arr.
Ví dụ, countOccurrences([1, 3, 1, 2, 0], 4) trả về [1, 2, 1, 1].
Tự làm thử
#include <stdlib.h>
int* countOccurrences(int* arr, int arr_size, int k, int* returnSize) {
// Viết code vào đây
*returnSize = arr_size;
return arr;
}
Tự kiểm traBài học này có một bài trắc nghiệm ngắn. Bắt đầu bài học để trả lời và theo dõi tiến độ.
Tất cả bài học trong Sắp xếp đếm, chuỗi DSA
2Thuật toán
Cách hoạt động?Mã giảTriển khai (phần 1)Triển khai (phần 2)
Độ phức tạp về thời gian và không gianTự luyện tập: Trình biên dịch C online