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?

Answer 1

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:

1. 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.

2. 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.

3. 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)

Answer 2

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:

• Time Complexities of all Sorting Algorithms.

• Best, worst and average case - Wikipedia

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