This code finds the smallest and largest element in an array using divide and conquer:
#include<stdio.h>
#include<stdlib.h>
#define MAX(a, b) ((a>=b)?a:b)
#define MIN(a, b) ((a<=b)?a:b)
void printarr(int *arr, int base, int height){
int i;
for (i = base; i <=height; i++){
printf("arr[%d] = %d \n", i, arr[i]);
}
}
//This function divides the array into partition recursively until a partition of 1 / 2 element(s) is reached
//and then compares the elements
int* partition(int *arr, int base, int height){
printf("\n\n");
printarr(arr, base, height);
int mid = (base + height)/2;
//The local array holds the largest and smallest elements
//of the partition in max_min[0] and max_min[1] respectively
int max_min[2];
//The next two integer pointers will point to the base
//address of the array returned(max_min[2]) by next recursive call
//Please continue reading to get it
int *max_min_temp;
int *max_min_temp_1;
//The if block is executed when the partition holds exactly one
//element the largest and the smallest elements are the same
if(base == height){
max_min[0] = arr[base];
max_min[1] = arr[height];
//The max_min[0] and max_min[1] holds the same element
printf("%d %d\n", max_min[0], max_min[1]);
//The base address of the array is now returned
return max_min;
}
//This else if block is executed when the there's exactly two elements
//In the partition and a simple comparison is done to find the minimum
//and maximum elements of the partition and store in max_min[1] and max_min[0]
//respectively
else if((height - base) == 1){
max_min[0] = MAX(arr[base], arr[height]);
max_min[1] = MIN(arr[base], arr[height]);
printf("%d %d\n", max_min[0], max_min[1]);
//The base address of the array is now returned
return max_min;
}
//This block is executed when more than two elements are there in the partition
else{
//Now the local partition is divided into two partition from the middle
//The max_min of the first half of the partition is pointed by max_min_temp
max_min_temp = partition(arr, base, mid);
//The max_min of the second half of the partition is pointed by max_min_temp_1
max_min_temp_1 = partition(arr, mid+1, height);
//----------------------THE PROBLEM ARISES HERE----------------------------//
//The max_min_temp and max_min_temp_1 act as if they point to the same array
// and hence compares the same elements
max_min[0] = MAX(max_min_temp[0], max_min_temp_1[0]);
max_min[1] = MIN(max_min_temp[1], max_min_temp_1[1]);
//It can be seen here in the following printf statement
printf("\nCHECKPOINT #1 - %d %d %d %d\n",max_min_temp[0], max_min_temp[1],max_min_temp_1[0], max_min_temp_1[1]);
//Check the corresponding output of the printf statement
printf("\nCHECKPOINT #2 - %d %d\n", max_min[0], max_min[1]);
return max_min;
}
}
/*int main(int argc, int *argv[]){
int i;
int arr[argc-1];
int *max_min;
for(i=1; i<argc; i++)
sscanf(argv[i],"%d",&arr[i-1]);
max_min = partition(arr, 0, argc-2);
printf("\nMax = %d Min = %d\n", max_min[0], max_min[1]);
return 0;
}*/
int main(){
int arr[] = {20, 30, 5, 10};
int *max_min = partition(arr, 0, 3);
printf("\nMax = %d Min = %d\n", max_min[0], max_min[1]);
return 0;
}
The Output is :
arr[0] = 20
arr[1] = 30
arr[2] = 5
arr[3] = 10
arr[0] = 20
arr[1] = 30
30 20
arr[2] = 5
arr[3] = 10
10 5
CHECKPOINT #1 - 10 5 10 5
CHECKPOINT #2 - 10 5
Max = 10 Min = 5
Which is not correct.
Now if I replace the else block with the following else block, It works fine.
else{
max_min_temp = partition(arr, mid+1, height);
max_min[0] = max_min_temp[0];
max_min[1] = max_min_temp[1];
max_min_temp_1 = partition(arr, base, mid);
max_min[0] = MAX(max_min[0],max_min_temp_1[0]);
max_min[1] = MIN(max_min[1],max_min_temp_1[1]);
//printf("%d %d\n", max_min[0], max_min[1]);
return max_min;
}
Now the Output is:
arr[0] = 20
arr[1] = 30
arr[2] = 5
arr[3] = 10
arr[2] = 5
arr[3] = 10
10 5
arr[0] = 20
arr[1] = 30
30 20
Max = 30 Min = 5
which is the desired one.
Seem that both the local pointer is holding the same array... But how? Please help. Thank you
The array max_min is returning a local address which is resulting same every time. The possible solution is to do Dynamic memory allocation.
int *max_min;
max_min = (int*)malloc(sizeof(int)*2);
Replace the line int* max_min[2] with above 2 lines.