Scribd
Upload
12 views4 pages

Sort Array by Merge Sort

Perform a "merge sort" of the array and then find the two elements in the array whose sum is closest to a given value.

Uploaded by

Dương Gia Bình
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
12 views4 pages

Sort Array by Merge Sort

Perform a "merge sort" of the array and then find the two elements in the array whose sum is closest to a given value.

Uploaded by

Dương Gia Bình
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

#include <stdio.

h>

#include <limits.h>

// Hàm trộn hai mảng con của mảng

void merge(int arr[], int l, int m, int r) {

int n1 = m - l + 1;

int n2 = r - m;

int L[n1], R[n2];

int i, j, k;

for (i = 0; i < n1; i++)

L[i] = arr[l + i];

for (j = 0; j < n2; j++)

R[j] = arr[m + 1 + j];

i = 0;

j = 0;

k = l;

while (i < n1 && j < n2) {

if (L[i] <= R[j]) {

arr[k] = L[i];

i++;

} else {

arr[k] = R[j];
j++;

k++;

while (i < n1) {

arr[k] = L[i];

i++;

k++;

while (j < n2) {

arr[k] = R[j];

j++;

k++;

// Hàm thực hiện merge sort

void mergeSort(int arr[], int l, int r) {

if (l < r) {

int m = l + (r - l) / 2;

mergeSort(arr, l, m);

mergeSort(arr, m + 1, r);
merge(arr, l, m, r);

// Hàm tìm hai phần tử có tổng gần nhất với giá trị cho trước

void findClosestPair(int arr[], int n, int target) {

int i, j;

int l = 0, r = n - 1;

int closest_sum = INT_MAX;

int closest_pair[2] = {0, 0};

while (l < r) {

int current_sum = arr[l] + arr[r];

if (abs(target - current_sum) < abs(target - closest_sum)) {

closest_sum = current_sum;

closest_pair[0] = arr[l];

closest_pair[1] = arr[r];

if (current_sum < target)

l++;

else

r--;
}

printf("Pair closest to %d: %d and %d\n", target, closest_pair[0], closest_pair[1]);

int main() {

int arr[] = {10, 22, 28, 29, 30, 40};

int n = sizeof(arr) / sizeof(arr[0]);

int target = 54;

mergeSort(arr, 0, n - 1);

findClosestPair(arr, n, target);

return 0;

You might also like