Đề bài
Cho 2 mảng đã sắp xếp. Viết hàm để gộp hai mảng đã sắp xếp cho trước thành một mảng.
Arr1[] = {10,15, 17, 20} Arr2[] = {5, 9, 13, 19} Result[] = {5, 9, 10, 13, 15, 17, 19, 20}
Thuật toán
1. Duyệt cả hai mảng 1.1. Nếu arr1[i] < arr2[j] 1.1.1. Thêm arr[i] vào mảng mới 1.1.2. Tăng 'i' và chỉ số mảng kết quả 'k' 1.2. Nếu arr2[i] < arr1[j] 1.2.1. Thêm arr[j] vào mảng mới 1.2.2. Tăng 'j' và chỉ số mảng kết quả 'k' 2. Lặp lại thủ tục cho đến khi cả hai mảng hết 3. Trả về mảng kết quả
Ví dụ
#include <iostream> #define SIZE(arr) (sizeof(arr) / sizeof(arr[0])) using namespace std; void mergeSortedArrays(int *arr1, int n1, int *arr2, int n2, int *result){ int i, j, k; i = 0; j = 0; k = 0; while (i < n1 && j < n2) { if (arr1[i] < arr2[j]) { result[k] = arr1[i]; ++k; ++i; } else { result[k] = arr2[j]; ++k; ++j; } } while (i < n1) { result[k] = arr1[i]; ++k; ++i; } while (j < n2) { result[k] = arr2[j]; ++k; ++j; } } void dispalyArray(int *arr, int n){ for (int i = 0; i < n; ++i) { cout << arr[i] << " "; } cout << endl; } int main(){ int arr1[] = {10, 15, 17, 20}; int arr2[] = {5, 9, 7, 13, 19}; int result[SIZE(arr1) + SIZE(arr2)]; cout << "First sorted array:" << endl; dispalyArray(arr1, SIZE(arr1)); cout << "Second sorted array:" << endl; dispalyArray(arr2, SIZE(arr2)); mergeSortedArrays(arr1, SIZE(arr1), arr2, SIZE(arr2), result); cout << "Final sorted array:" << endl; dispalyArray(result, SIZE(result)); return 0; }
Kết quả
Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau:
First sorted array: 10 15 17 20 Second sorted array: 5 9 7 13 19 Final sorted array: 5 9 7 10 13 15 17 19 20