/* Given an array A[] and a number x, check for pair in A[] with sum as x */
#include <stdio.h>
void quickSort(int*, int, int);
void printSumPair(int A[], int arr_size, int sum) {
int l, r;
// sort in increasing order
quickSort(A, 0, arr_size - 1);
l = 0;
r = arr_size-1;
while (l < r) {
if (A[l] + A[r] > sum)
r --;
else if (A[l] + A[r] < sum)
l++;
else {
printf("%d + %d equals %d\n", A[l], A[r], sum);
break;
}
}
}
int main() {
int arr[] = {1,4,45,6,10,8}; // sorted would be : {1,4,6,8,10,45}
int x = 16;
int arr_size = sizeof(arr)/sizeof(arr[0]);
printSumPair(arr, arr_size, x);
return 0;
}
void exchange (int *a, int *b) {
int temp;
temp = *a;
*a = *b;
*b = temp;
}
int partition (int A[], int si, int ei ) {
int x = A[ei];
int i = si - 1;
int j;
for (j = si; j <= ei - 1; j++) {
if(A[j] <= x) {
i++;
exchange (&A[j], &A[i]);
}
}
exchange (&A[i+1], &A[ei]);
return (i+1);
}
void quickSort (int A[], int si, int ei) {
int pi;
if (si < ei ) {
pi = partition(A, si, ei);
quickSort(A, si, pi-1);
quickSort(A, pi+1, ei);
}
}
#include <stdio.h>
void quickSort(int*, int, int);
void printSumPair(int A[], int arr_size, int sum) {
int l, r;
// sort in increasing order
quickSort(A, 0, arr_size - 1);
l = 0;
r = arr_size-1;
while (l < r) {
if (A[l] + A[r] > sum)
r --;
else if (A[l] + A[r] < sum)
l++;
else {
printf("%d + %d equals %d\n", A[l], A[r], sum);
break;
}
}
}
int main() {
int arr[] = {1,4,45,6,10,8}; // sorted would be : {1,4,6,8,10,45}
int x = 16;
int arr_size = sizeof(arr)/sizeof(arr[0]);
printSumPair(arr, arr_size, x);
return 0;
}
void exchange (int *a, int *b) {
int temp;
temp = *a;
*a = *b;
*b = temp;
}
int partition (int A[], int si, int ei ) {
int x = A[ei];
int i = si - 1;
int j;
for (j = si; j <= ei - 1; j++) {
if(A[j] <= x) {
i++;
exchange (&A[j], &A[i]);
}
}
exchange (&A[i+1], &A[ei]);
return (i+1);
}
void quickSort (int A[], int si, int ei) {
int pi;
if (si < ei ) {
pi = partition(A, si, ei);
quickSort(A, si, pi-1);
quickSort(A, pi+1, ei);
}
}
No comments:
Post a Comment