An array A contains integers that first increase in value and then decrease in value. It is unknown at which point the numbers start to decrease. Write efficient code to copy the numbers in A to another array B so that B is sorted in ascending order.
for example:
#include <stdio.h>
int Bsearch(int A[], int size, int low);
int main()
{
int A[]={17,24,31,44,49,36,29,20,18,13};
int sizea = sizeof(A)/sizeof(A[0]);
int B[sizea], k=0, m=sizea-1, count=0;
for(int i=0; i<sizea; i++)
printf("%d\t", A[i]);
printf("\n");
int pivot = Bsearch(A, sizea, 0);
if (pivot == -1) {
printf("invalid logic");
return 0;
}
else
printf("pivot index %d\n", pivot);
//copy the array
while (k<pivot && m>pivot) {
if (A[k] <= A[m]) {
B[count++] = A[k];
k++;
}
else {
B[count++] = A[m];
m--;
}
}
while (k<pivot) {
B[count++] = A[k];
k++;
}
while (m>pivot) {
B[count++] = A[m];
m--;
}
B[count++] = A[pivot];
//print array
printf("\nArray B\n");
for(int i=0; i<sizea; i++)
printf("%d\t", B[i]);
printf("\n");
return 0;
}
int Bsearch(int A[], int size, int low)
{
int high = size-1;
int mid;
while (low <= high) {
mid = (low + high)/2;
//value before & after mid shd be less than mid
if ((A[mid] > A[mid+1]) && (A[mid] > A[mid-1]))
return mid;
//if mid is less than mid+1, increment low
else if (A[mid] < A[mid+1])
low = mid+1;
else if (A[mid-1] > A[mid])
high = mid-1;
}
return -1;
}
Output:
pivot = 5
Array B
13,17,18,20,24,29,31,36,39,44,49
Comments
Post a Comment