I have written a program for an algorithms class which takes integer arrays as an argument and finds the subarray with its sum being closest to zero. The program compiles and runs. The results are correct most of the time it's ran, but seemingly randomly it will print zeros for the subarray's sum and indices values. The sets of data which print the zero's for their results are always the same sets when the error does occur. I can't figure out why this would happen, maybe a memory issue of some kind. It would make sense if the results were always incorrect or correct, but, since no variables are changing, I am stumped. Any help would be very appreciated.
#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
#include <string.h>
struct Numbers
{
int num;
int index;
};
struct Sums
{
int sum;
int indice_i;
int indice_j;
} ClosestToZero_default={INT_MAX,INT_MAX,INT_MAX};
typedef struct Sums ClosestToZero;
int struct_cmp(const void *a, const void *b)
{
struct Numbers *ia=(struct Numbers*)a; // magic
struct Numbers *ib=(struct Numbers*)b;
return (int)(ia->num-ib->num);
}
void print_result(int result,int indice_i,int indice_j)
{
printf("Sum of Subarray Closest to Zero: %d\nStart Index: %d End Index: %d\n\n",result,indice_i,indice_j);
}
struct Sums findMiddle(struct Numbers* array,int start_index,int end_index)
{
ClosestToZero result=ClosestToZero_default;
int i,j;
int n=end_index-start_index+1;
int size_left=(n+1)/2;
int size_right=n-size_left;
struct Numbers left_array[size_left];
struct Numbers right_array[size_right];
int sum=0;
j=size_left-1;
for(i=start_index+size_left-1;i>=start_index;i--,j--)
{
left_array[j]=array[i];
left_array[j].num+=sum;
sum+=array[i].num;
}
sum=0;
j=start_index+size_left;
for(i=0;i<size_right;i++,j++)
{
right_array[i]=array[j];
right_array[i].num+=sum;
sum+=array[j].num;
}
qsort(left_array,size_left,sizeof(struct Numbers),struct_cmp);
qsort(right_array,size_right,sizeof(struct Numbers),struct_cmp);
i=0;
j=size_right-1;
while(1)
{
if(left_array[i].num>0||right_array[j].num<0) break;
if(abs(left_array[i].num+right_array[j].num)<result.sum)
{
result.sum=abs(left_array[i].num+right_array[j].num);
result.indice_i=left_array[i].index;
result.indice_j=right_array[j].index;
}
if(abs(left_array[i].num)>abs(right_array[j].num)) i++;
else j--;
}
while(i<size_left&&j>=0)
{
if(left_array[i].num<0)
{
i++;
continue;
}
if(right_array[j].num>0)
{
j--;
continue;
}
if(abs(left_array[i].num+right_array[j].num)<result.sum)
{
result.sum=abs(left_array[i].num+right_array[j].num);
result.indice_i=left_array[i].index;
result.indice_j=right_array[j].index;
}
if(abs(left_array[i].num)>abs(right_array[j].num)) j--;
else i++;
}
return result;
}
struct Sums algorithm2(struct Numbers* array,int start_index,int end_index)
{
int i,j;
ClosestToZero result_left;
ClosestToZero result_right;
ClosestToZero result_mid;
if(end_index==start_index)
{
result_mid.sum=abs(array[start_index].num);
result_mid.indice_i=result_mid.indice_j=array[start_index].index;
return result_mid;
}
if(end_index-start_index==1)
{
int a=abs(array[start_index].num);
int b=abs(array[end_index].num);
int c=abs(array[start_index].num+array[end_index].num);
if(a<b&&a<c)
{
result_mid.sum=a;
result_mid.indice_i=result_mid.indice_j=array[start_index].index;
}
else if(b<a&&b<c)
{
result_mid.sum=b;
result_mid.indice_i=result_mid.indice_j=array[end_index].index;
}
else
{
result_mid.sum=c;
result_mid.indice_i=array[start_index].index;
result_mid.indice_j=array[end_index].index;
}
return result_mid;
}
int mid_index=(start_index+end_index)/2;
result_left=algorithm2(array,start_index,mid_index);
result_right=algorithm2(array,mid_index+1,end_index);
result_mid=findMiddle(array,start_index,end_index);
if(result_left.sum<result_right.sum&&result_left.sum<result_mid.sum)
return result_left;
if(result_right.sum<result_left.sum&&result_right.sum<result_mid.sum)
return result_right;
return result_mid;
}
int closestZeroSum(int* arr,int n)
{
int i;
struct Numbers array[n];
for(i=0;i<n;i++)
{
array[i].num=arr[i];
array[i].index=i;
}
struct Sums result=algorithm2(array,0,n-1);
print_result(result.sum,result.indice_i,result.indice_j);
return 0;
}
int main(int argc,int argv[])
{
int arr1[]={499228, 21572, -323857, 288186, -451707, -228193, -443913, -313419, 236065, -52692, 42198, -169000, 418130, 246890, 16091, 201633, 124538, 418432, -385986, 154610, 85740, 211439, -169332, 104064, 162438, 251, -179159, 136801, -187420, 189088, 67512, -74248, -150024, -467850, -235169, 214345, 455041, 453804, -467983, -56033, 479772, 494760, -168594, 10655, 437440, 157697, 407151, 466806, -168368, 74531, 214696, -35099, -344876, -377398, -392111, 236400, 93324, 155484, -110424, 440427, -220568, -147152, -330916, 419883, 332187, 314146, 379534, -351921, -374375, 301787, -18693, -88397, 68640, -90075, -165441, 7676, -49795, -358864, 110334, 3909, 51923, -350801, 211367, 178221, -48033, 173907, 137308, 454152, 334786, 247404, 261047, 122729, -439424, -318938, -367503, 379156, -170671, -154459, -395737, -193401};
int arr1_size=sizeof(arr1)/sizeof(int);
int arr2[]={386521, -426105, -51327, -479314, 266939, -483585, 5174, -26325, -174507, 420884, 16180, 349704, 60431, -345921, 402022, 139333, -132008, 72744, -102568, -46460, 450996, -371577, -488895, 58007, -235653, 297566, -325213, -257872, 93030, 3737, -166953, -32082, -149683, -359092, -414417, 78794, 61943, 223186, 79294, -170009, -32876, 412168, -199555, 488317, 432080, 448046, 98065, 304298, -183989, -72475, -148109, 397536, 482222, 374665, -389837, -220047, -474078, -345931, -180385, -136260, 427174, 417819, 318218, 83008, 239618, 496199, 195442, -346491, -182687, -12742, -315836, 129197, -165305, 13224, -63483, 461599, 118305, -136678, 252502, 304408, 192900, -384603, -49832, -225063, -388805, 30286, -58632, 224370, -212093, -214778, 227535, -263757, 430684, 318599, 21355, 52281, -73725, -486957, -118220, 62683};
int arr2_size=sizeof(arr2)/sizeof(int);
int arr3[]={258821, 306066, -231500, -436295, 306425, 241361, 68153, 216106, -353968, 425757, 438111, -65653, -90992, -408188, -319437, 151786, -356247, -424078, -230531, 51863, 371945, 439278, -98784, 445010, -8235, 177337, 123174, 375508, -308068, 420045, 410467, 344006, 272623, 226552, -198151, -38586, 233206, -479137, -64701, -185958, 17319, 9237, -451752, 28414, 45946, -99873, -451984, 325519, -372670, 330385, 26093, 331932, 66849, -346808, 105535, 313619, -437154, 489421, -294743, -82994, -328806, 425808, -4951, 380292, -284245, -263289, 99328, -136943, 334475, -488275, 45777, 462572, -105101, -268580, 445742, 228270, -386481, -311534, -493956, -465020, 414547, -407161, 62069, -258371, 442358, 170609, -337386, 316532, -247616, 281311, -327522, -472093, -418488, 45369, -122124, 356880, 392005, -228005, -404684, -315306};
int arr3_size=sizeof(arr3)/sizeof(int);
int arr4[]={-214717, 361303, 416397, -60197, 324864, -330864, 269005, 24278, -212135, 328504, 444353, -286586, 168424, -101904, -316543, -423435, -255180, 287940, 445395, 115632, -253558, 147979, -152719, 365455, -495117, -276957, -198353, 407462, 72712, -363120, -290174, -21743, -273045, 447738, -391003, 322787, 130778, 266059, -215648, 335540, 379559, -409427, -434836, -326577, -56499, 299815, 154620, 407297, -481496, 59677, 229793, 495171, 498055, -339219, 271951, 487629, -396570, -424726, 309446, 320962, 362817, -89534, 82070, 146429, -145523, 356977, 286852, -436864, 237388, -211029, 395540, 330818, 299266, 453390, -184790, 187741, -242354, -151414, -416877, 384540, 341533, 415449, 294444, 257065, 230018, 240416, -317276, -306150, -162259, -135509, -32091, 77089, -231556, -134644, 11163, 320983, 443832, -393703, -384938, -20882};
int arr4_size=sizeof(arr4)/sizeof(int);
int arr5[]={-210333, -203574, -29420, -375363, -393800, 421046, -244507, 354795, -489162, 163316, 108146, -130364, 189343, -265580, -104608, -354593, -196407, -83326, -259045, 91954, 102741, -374334, -195592, -328131, -128635, -145780, -268674, -206437, 168629, -496691, 83207, 464554, -184084, -409403, -445299, 41312, 234004, -459966, -127733, -427338, -311021, -449664, 85188, -482381, -21829, -381143, -158807, -317729, -181146, 102318, -112927, 493008, 333608, 187402, -201813, 288212, -262296, -306723, -220246, 479108, 415186, -372438, -246269, -353105, 333361, 394104, 482347, -23831, 168611, -207283, 38343, 314168, -281553, 281228, -474763, 332710, -198532, 321268, -344461, 483687, 31910, 90240, 435233, 466993, -389003, 67743, 454699, 76577, 204593, 13466, 362508, -68273, -187942, -363061, -485642, 409273, 285247, 411904, 80985, 324690};
int arr5_size=sizeof(arr5)/sizeof(int);
int arr6[]={368944, 321652, -362363, -234897, 105687, 65523, -404365, 176408, 182830, 338002, -290518, 166771, -365419, -271724, -127480, -322735, -378171, -39266, -435294, 476897, 499179, 157601, 198607, 491320, -389158, -303347, -472691, 100100, -14174, -29001, 421124, 270487, -376761, 481298, 36273, 459798, 358359, -63152, -206361, 117190, 185374, 41951, -124229, -73667, -214465, -182715,-215614, -476948, 315622, 64995, 497534, -12914, 415459, -52916, 460256, 400891, 183325, 429259, -153934, -180787, -21403, -193158, 272599, -136778, -368140, -279420, -250377, -220183, -439302, 464769, 214400, -120020, 374103, 128886, 381712, -3005, 487535, 39729, 148154, 446269, -312541, -78711, 97321, 152678, -438171, 60025, -390485, -363629, 17071, 356450, -189293, -157489, -146602, -219611, 427199, -446551, -490620, 325541, 210627, 384613};
int arr6_size=sizeof(arr6)/sizeof(int);
printf("\n\nExpected Output is: 251, 25, 25\n");
printf("algorithm2--------------------------\n");
closestZeroSum(arr1,arr1_size);
printf("Expected Output is: 89, 94, 96\n");
printf("algorithm2--------------------------\n");
closestZeroSum(arr2,arr2_size);
printf("Expected Output is: 3, 3, 96\n");
printf("algorithm2--------------------------\n");
closestZeroSum(arr3,arr3_size);
printf("Expected Output is: 576, 3, 47\n");
printf("algorithm2--------------------------\n");
closestZeroSum(arr4,arr4_size);
printf("Expected Output is: 325, 72, 73\n");
printf("algorithm2--------------------------\n");
closestZeroSum(arr5,arr5_size);
printf("Expected Output is: 271, 68, 96\n");
printf("algorithm2--------------------------\n");
closestZeroSum(arr6,arr6_size);
return 0;
}
I have some testing and have found some interesting results; I can't make sense of them though. When I put print statements in base cases for the result_mid.num value prior to it being returned, I received a segmentation fault. I also added an extra base case for when there were only 3 elements left to compare. With the set of test data I have posted, this will work, but with the actual data, which is a must larger set, I still get the same type of error. This time the error occurs in sets of data which previously were always correct.
Why might the results of some sets of data randomly, and incorrectly, produce zeros?
Random data is a good hint that array access is out-of-bounds.
Algorithmic error leads to access of right_array[-1]
while (1) {
if (!(j >= 0 && j < size_right)) {
printf("!1 %d %d\n", j, size_right);
exit(0);
}
if (!(i >= 0 && j < size_left)) {
printf("!2 %d %d\n", j, size_left);
exit(0);
}
if (left_array[i].num > 0 || right_array[j].num < 0) break;
Outputs
Expected Output is: 251, 25, 25
algorithm2--------------------------
!1 -1 1
Suspect while (1) should be
while (j >= 0)
Other minor issues.
struct_cmp()
// return (int) (ia->num - ib->num);
return (ia->num - ib->num) - (ia->num < ib->num);
size_t for array indexes. INT_MAX --> SIZE_MAX for index types.
abs(int + int) a problem in 2 ways: sum overflow and INT_MIN
Overall, code would benefit with some comments.