arrayscfor-loopcs50memory-access

Problem with value assignment inside a for loop


There is silly bug in my code. I would appreciate to any help. I know this is language (C) specific (because I have some experience with Python & JS). I'm trying to split source array into two parts. When I try to assign value of current index of source array to another array, it works fine but only until the end of for loop. After loop completion these arrays turns out with completely different values. Please check out my code below:

#include <stdio.h>
//#include <cs50.h>

int merge_sort(int unsorted_array[], int size_of_arr);

int main(void)
{
    int unar[] = {9, 8, 7, 6, 5, 4, 3, 2, 1};     // unsorted array
    int len_of_arr = sizeof(unar) / sizeof(int);  // finding lenght of array
    merge_sort(unar, len_of_arr);                 
}

int merge_sort(int unsorted_array[], int size_of_arr)
{
    // dividing
    int ls_len; // lenght of left side of an array
    int rs_len; // lenght of right side of an array

    if (size_of_arr % 2 == 0) // if lenght of an array is even then lenght of each half equals: lenght of arr / 2
    {
        ls_len = size_of_arr / 2;
        rs_len = size_of_arr / 2;
    }
    else                      // else lenght of arr / 2 and right half++
    {
        ls_len = size_of_arr / 2;
        rs_len = size_of_arr / 2 + 1;
    }

    int unsorted_ls[ls_len]; // unsorted_array_length // 2
    int unsorted_rs[rs_len]; // if array_len is odd ? array_len / 2 + 1 : array_len / 2
    printf("left half len: %i\nRight half len: %i\n", ls_len, rs_len);

    for (int i = 0; i < size_of_arr; i++)
    {
        if (i < ls_len)
        {
            unsorted_ls[i] = unsorted_array[i];
            printf("Current value of original array: %i\n", unsorted_array[i]);
            printf("Currently assigned value of left half: %i\n\n", unsorted_ls[i]);       // current
        } else
        {
            unsorted_rs[i] = unsorted_array[i];
            printf("Current value of original array: %i\n", unsorted_rs[i]);
            printf("Currently assigned value of right half: %i\n\n", unsorted_array[i]);
        }
    }

    printf("Left half outside of for loop: ");
    for (int i = 0; i < ls_len; i++)
    {
        printf("%i", unsorted_ls[i]);
    }
    printf("\n");

    printf("Right half outside of for loop: ");
    for (int i = 0; i < rs_len; i++)
    {
        printf("%i", unsorted_rs[i]); 
    } 
    printf("\n"); 

    // sorting                                                       // not implemented yet
    // int sorted_left_side[] = merge_sort(unsorted_left_half); 
    // int sorted_right_side[] = merge_sort(unsorted_right_half); 
    
    // merging                                                       // not implemented yet
    // // for (int i = 0; )

    // return sorted_array;
    return 0;
}

Solution

  • This assignment statement

    unsorted_rs[i] = unsorted_array[i];
    

    invokes undefined behavior because there is an attempt to access memory beyond the array unsorted_rs when the value of the index i is greater than or equal to ls_len.

    You should write

    unsorted_rs[i - ls_len] = unsorted_array[i];
    

    Pay attention to that instead of this if-else statement

    if (size_of_arr % 2 == 0) // if lenght of an array is even then lenght of each half equals: lenght of arr / 2
    {
        ls_len = size_of_arr / 2;
        rs_len = size_of_arr / 2;
    }
    else                      // else lenght of arr / 2 and right half++
    {
        ls_len = size_of_arr / 2;
        rs_len = size_of_arr / 2 + 1;
    }
    

    you could just write

    ls_len = size_of_arr / 2;
    rs_len = size_of_arr - ls_len;