Triển khai (phần 2)
Bài học 6 trên 9 trong khóa học Merge Sort: loạt bài về DSA của Coddy.
Bây giờ, chúng ta kết hợp việc chia và trộn thành thuật toán hoàn chỉnh.
Thử thách
DễGiờ hãy kết hợp tất cả thành thuật toán hoàn chỉnh.
Viết một hàm (function) có tên mergeSort, nhận vào một mảng số nguyên và trả về mảng đã được sắp xếp theo thứ tự tăng dần.
Chia mảng thành hai nửa, sắp xếp từng nửa bằng cách gọi mergeSort cho nửa đó (đệ quy), rồi gộp hai nửa đã sắp xếp lại với nhau. Mảng có 0 hoặc 1 phần tử đã được sắp xếp, vì vậy hãy trả về mảng đó nguyên trạng.
Bạn có thể dùng lại logic gộp từ bài học trước.
Tự làm thử
#include <stdlib.h>
int* mergeSort(int* arr, int arr_size, int* returnSize) {
// Viết code ở đâ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 Merge Sort: loạt bài về 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 thời gian và không gianTự luyện tập: Trình biên dịch C online