memory copy dynamically allocated array

Question

I am currently found out a interesting and simple sorting algorithm, so I implemented it in with dynamically allocated array. Here is my code.

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

void positiveIntSort(int *array,int size);
void printArray(int array[],int size);

int main() {
    int bigNum = 99999;
    int *array = (int *) malloc (bigNum*sizeof(int));
    int i,index,size;
    printf("Enter the size of array: ");
    scanf("%d",&size);
    printf("Enter each element for array: ");
    for(i = 0; i < size; i++) {
        scanf("%d",&index);
        array[index] = 1;
    }
    positiveIntSort(array,size);
    printArray(array,size);
}

int positiveIntSort(int *array,int size) {
    int i,j = 0;
    int sortedArray[size];
    for(i = 0; i < 99999,j < size; i++) {
        if(array[i] == 1)
            sortedArray[j++] = i;
    }
    memcpy(array,sortedArray,size);
    printArray(sortedArray,size);
}

void printArray(int array[],int size) {
    int i;
    for(i = 0; i < size; i++) {
        printf("%d\t",array[i]);
    }
    printf("\n");
}

So, basically what I am doing is if user input a number : a, I go to corresponding index, which is a in this case, and assign 1 to this array[a]. So I traverse again and print all the index with value 1. This way gives me a sorted array.

However, I have some trouble with the dynamically allocated array. Here is a sample output I have:

Enter the size of array: 5
Enter each element for array:23 12 45 63 38
12       23      38      45     63
12       1845015 0       0      0

So sorting is definitely working. However when I return the sorted array to the dynamically allocated array, the result messed up. I could not find the reason? Is the way I use memcpy incorrect?

Besides, is the complexity of this algorithm O(n). Is there anyway to make this algorithm better?

What's the point of the dynamic allocation here? Also providing at least the name of the algorithm (let alone the description) would be appropriate. — Eugene Sh.
– Eugene Sh., Commented Mar 27, 2018 at 21:13
You never initialized any of the elements that the user didn't enter. Some of them might contain 1. — Barmar
– Barmar, Commented Mar 27, 2018 at 21:13
You have not checked that the input value index is within the bounds of the array, and if it is, any other element not specifically set to 1 has an indeterminate value, since malloc does not initialise the memory allocated. You should also allocate the memory after you input the number of elements size, so bigNum is irrelevant. Moreover what is the magic number for in i < 99999? Did you intend i < bigNum (although not in scope)? — Weather Vane
– Weather Vane, Commented Mar 27, 2018 at 21:23

sg7 · Accepted Answer · 2018-03-28 23:52:54Z

However, I have some trouble with the dynamically allocated array.

In your code you have allocated room for the array :

   int *array = (int *) malloc (bigNum*sizeof(int));

with exactly this many bytes: bigNum * sizeof(int).

(BTW: There is no need to cast result of malloc in C language. It is recommended to check if allocation was successful and non NULL result of malloc was returned.)

Instead of dynamically allocating the array (you forgot to free the array memory) you could declare it after obtaining the size of the array:

   //int *array = (int *) malloc (bigNum*sizeof(int));
   int i,index,size,bigNum;
   printf("Enter the size of array: ");
   scanf("%d",&bigNum );
   int array[bigNum];
   printf("Enter the number of elements: ");
   scanf("%d",&size);

This also problem what to do with uninitialized array elements.

Symmetrically in int positiveIntSort(int *array,int size){

you have to copy all the bytes belonging to the array. The number of bytes in this array is equal to number or array elements times the size of the element. In your case the size of the element if equal to sizeof(int).

Therefore the line

   memcpy(array,sortedArray,size);

should be replaced by:

   memcpy(array,sortedArray,size* sizeof(int));

I will not comment on the logic of the your algorithm which does not seem to handle duplicates and negative values.

Different sorting algorithms have different time complexities:

If you need faster sorting time than yours you may consider other algorithms.

You do realize how that algorithm works, right? array is not supposed to store the input data in a sequential way. It's size is not size, it is supposed to be at least as big as the largest input value, as it uses values as array indices in order to sort. So, int array[size]; is not correct.
@KyrSt Thanks! You are right! I should say int array[bigNum]; Correcting.

kyriakosSt · Accepted Answer · 2018-03-27 21:46:15Z

Your problem is the size argument in memcpy() call inside positiveIntSort.
It should be:

memcpy(array,sortedArray,size*sizeof(int));

As memcpy() needs as a third argument the number of bytes for copying (not the number of elements of the array).

Also note that you have conflicting types of positiveIntSort() with one returning void and the other int, which is also ignored by the implementation.

Now about making the algorithm better:

There is no need for arbitrary size on your array. (or else: arbitrary max value). Store the user input in a temp array and find the maximum and minimum values . Then allocate space for (max-min+1) integers in array. And for each value d, insert it in the d-min position of the array. You will need an extra loop but the time complexity remains O(n) (*) and not only you don't have unnecessary constrains, but also you can decrease the memory overhead.
What about duplicate input values? Right now your algorithm cannot handle duplicates. You could just add 1 to the corresponding cell of your initial array instead of setting to 1 for each number. This way, if you put some extra effort in your sorting function you can locate and sort correctly all duplicates.
What about negative values? A way would be to perform two different sortings (one for negatives and one for positives) and concatenate them at the end (even better if you do it in place).

Finally, as it is mentioned in the comments, you also need to initialize your values in the array, as some could be 1 (use calloc() to make your life easier).

(*): To be exact your complexity is now Θ(max{n, nmax-nmin}), where nmax and nmin are the largest and smallest values of your input. (or the size of your array, as you will loop through it)

Collectives™ on Stack Overflow

memory copy dynamically allocated array

2 Answers 2

2 Comments

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Linked

Related