Declaring Array of variable size in C

Question

I have been going through Introduction to Algorithms and am trying to implement the pseudo-code presented for merge-sort using C programming language.

This is the pseudo-code presented for the MERGE procedure:

While I understand this procedure, I am struggling to implement in C when arriving at the 3rd line. My compiler is giving an error (and rightly so after C99) expression must have a constant value.

Error is occurring on line 3 of the pseudo-code or at int L[n1]; in code posted below

How can I create an array which holds n1 and n2 values which are constantly changing from one iteration to the next? Any suggestions would be appreciated.

I also came across https://www.geeksforgeeks.org/merge-sort/ to see how it might be done, and the website is using the same syntax as I am, but without any compiler warnings. Is this because of an older compiler version (C99?) or am I missing something from my end?

My code is below:

/* C program for Merge Sort */
#include<stdlib.h>
#include<stdio.h>

#define infinite 9999;      //Used for sentinels

void MERGE(A, p, q, r);
void printArray(Arr, size);
void MERGE_SORT(A, p, r);

int main(void)
{
   int A[] = { 12, 11, 13, 5, 6, 7, 2, 9 };
   int arr_size = sizeof(A) / sizeof(A[0]);

   MERGE_SORT(A, 1, arr_size);

   printf("\nSorted array is \n");
   printArray(A, arr_size);

   return 0;
 }

 void MERGE(int A[], int p, int q, int r)
 {
   int i = 0;
   int j =0;
   int n1 = q - p + 1;      //Computing length of sub-array 1
   int n2 = r - q;          //Computing length of sub-array 2
   int L[n1];               //Creating Left array
   int R[n2];               //Creating Right array

   for (int i = 1; i < n1; i++) {
       L[i] = A[p + i - 1];
   }
   for (int j = 1; j < n2; j++) {
       L[j] = A[q + j];
   }

   L[n1] = 99;  //Placing Ssentinel at the end of array
   R[n2] = 99;

   i = 1;
   j = 1;

   /*Prior to the first iteration k = p, so the subarray is empty.
   Both L[i] and R[j] are the smallest elements of their arrays and have not 
   been copied back to A*/
   for (int k = p; k < r; k++) {
       if (L[i] <= R[j]) {
           A[k] = L[i];
           i++;
       }
       else if (A[k] = L[i])
           j++;
   }

}

void MERGE_SORT(int A[], int p, int r)
{
   //During first iteration p = 1 & r = 8
   if (p < r) {
       int q = (p + r) / 2;
       MERGE_SORT(A, p, q);
       MERGE_SORT(A, q + 1, r);
       MERGE(A, p, q, r);
   }
}

EDIT

Code for MERGE updated as follows thanks to suggestions from answer and comments below. Even though the code below presents no syntax or run-time errors, the output is still not correct. This is out of the scope of the question, however. Another question was asked here: Writing Merge Sort Pseudo-Code Procedure in C

 void MERGE(int A[], int p, int q, int r)
 {
   int i = 0;
   int j =0;
   int n1 = q - p + 1;                      
   int n2 = r - q;                          
   int *L = malloc((n1+1) * sizeof(*L));        //Creating Left array
   int *R = malloc((n2+1) * sizeof(*R));            //Creating Right array

   for (int i = 1; i < n1; i++) {
       L[i] = A[p + i - 1];
   }
   for (int j = 1; j < n2; j++) {
       L[j] = A[q + j];
   }

   L[n1] = 99;  //<-- Some modification must be carried out here to allocate 
   R[n2] = 99;  //`99` to the end of array

   i = 1;
   j = 1;

   for (int k = p; k < r; k++) {
       if (L[i] <= R[j]) {
           A[k] = L[i];
           i++;
       }
       else if (A[k] == L[i])
           j++;
   }

   free(L);
   free(R);  //Freeing both pointers at the end of iteration
}

Error was at the 3rd line. Mentioned in my question but it may not have been clear. Will edit. — rrz0, Mar 18 '18 at 08:23
You probably want `else if (A[k] == L[i])` instead of `else if (A[k] = L[i])`. If your compiler does not issue a warning about this you need to enable (more) warnings. — August Karlstrom, Mar 18 '18 at 09:07
Just saw that there are no warnings. You are absolutely correct. I am using Visual Studio 2017 and might need to alter some settings from within. — rrz0, Mar 18 '18 at 09:10

Stephen Docy · Accepted Answer · 2018-03-18T08:58:18.640

3

To create an array with size computed at runtime, use malloc()

int *L = malloc(n1 * sizeof(*L));
if (L == NULL) {
    // handle error
}

The code you linked to is using Variable Length Arrays which is supported by some but not all C compilers. See :

Passing array to a function (and why it does not work in C++)

This is accessing past the end of the array

L[n1] = 99;  //<-- Some modification must be carried out here to allocate 
R[n2] = 99;  //`99` to the end of array

Remember, with an array containing n elements, valid indices are 0 - n-1

edited Mar 18 '18 at 08:58

answered Mar 18 '18 at 07:58

Stephen Docy

4,738
7
18
31

Thanks for your answer, this helps! Does one need to proceed by: `free(ptr);` and `ptr = NULL;` in this case or is it not necessary? – rrz0 Mar 18 '18 at 08:10
Use `free` after you are done working with the memory. – Marco Mar 18 '18 at 08:11
You need to `free()` once you are done with the pointer. You should not `free()` before unless it points to some other memory segment you previously allocated for it. You do not need to set it to `NULL`, after the `malloc()` call it will either point to valid memory for you to use, or it will be `NULL`. – Stephen Docy Mar 18 '18 at 08:13
I am currently experiencing no errors with the above modification to the code, but struggle to use `free()` when I am done with the pointer. Since this is a recursive technique I want to free the pointer after an iteration through `MERGE` procedure. Therefore I am freeing the pointer after the `for` loop at the end of this function. Is this good practice? Many thanks for your help. – rrz0 Mar 18 '18 at 08:30
1

Once you have copied all elements of your subarrays back to the original array is a good time to free the subarrays. In this case, it looks like that would be at the very end of `MERGE()`. – Stephen Docy Mar 18 '18 at 08:33
1

Note that `ptr = NULL` is not needed, it's just a good habit to avoid dangling pointers. – Iharob Al Asimi Mar 18 '18 at 08:51
With the changes mentioned in this answer, as edited in the question I am getting a `Heap Corruption Detected`, meaning that I am writing into unallocated memory, damaging the data structures used to make the memory allocator work. I do not get any line number where this is happening, since this is a run-time error. – rrz0 Mar 18 '18 at 08:54
@StephenDocy I believe hist first comment question "Does one need to `free...` and `ptr = NULL;`" is only partially addressed. Make sure you let the OP know that after your call to `free` the value of the pointer is not automatically set `NULL`, so if there is any possibility of a subsequent test of the pointer, then it is advisable to set `ptr = NULL;`. If the pointer will simply go out of scope without further use, then there is no need. – David C. Rankin Mar 18 '18 at 08:54
@Rrz0 can you update the question with your current code? – Stephen Docy Mar 18 '18 at 08:56
@StephenDocy, question is updated with `MERGE` procedure, right after the **EDIT**. That is the only place where I made some changes. Is this visible from your end? – rrz0 Mar 18 '18 at 08:56
@StephenDocy Seeing the edit to your answer, I understand this, and that is why I want to create the initial arrays `int *L = malloc(n1 * sizeof(*L));` to be 1 size greater than `n1`, thus allowing me to add the sentinel at the end. Something like `int *L = malloc(n1+1 * sizeof(*L));`?? – rrz0 Mar 18 '18 at 09:05
1

Yep, that's perfectly fine...just make sure you get your parentheses correct – Stephen Docy Mar 18 '18 at 09:05
Many thanks for the answer and all those who commented above. I am still getting an erroneous output, but I guess that is out of the scope of this question. – rrz0 Mar 18 '18 at 09:58

Declaring Array of variable size in C

1 Answers1