Adjusting position in array to maintain increasing order

Question

I have undergone one problem in C in logic creation.What i have to do is:

1)I have array a[215] = {0,1,2,3,4,5}.Now i have to add two minimum elements of this array and then position the newly element obtained in the same array such that it will maintain the increasing order of the array(a[],which was already sorted array).

(2)I also have to take care that the two minimum added elements must not participate in sorting and addition again, they must be fixed at their position once if they are already added, but the newly obtained element by addition can participate in addition and sorting again. eg: we add two minimum element 0 and 1, 0+1=1, so "1" is the result obtained by addition, now this "1" must be positioned in a[] such that still there should be increasing order. so :

0 1 1(added here) 2 3 4 5

Now we have to again find the minimum two nodes (please read the comment (2) again to understand well) .We cannot add 0 abnd 1 again because they have already participated in in the addition. so this time we will add 1 and 2(this one is at index three, please don't get confused wwith the one at index two). so we get 1+2=3

0 1 1 2 3 3 4 5 we again positioned 3 to maintain increasing order. we repeat again: for element at index 4 and 5(because we have already done addition for element at index 0,1 and 2,3) we will get 3+3=6, again position it in a[].

0 1 1 2 3 3 4 5 6 this time 6 is greater then 4 and 5 so it will appear after 5 to maintain increasing order.

At last we will get a[] like this:
a[ ]= [0 1 1 2 3 3  4 5 6 9 15].

so the addition held was between index 0,1 and 2,3 and 4,5 and 6, 7 and 8,9 and at last we have 15 which is last one, so here we stops.

Now coming to how much i have already implemented : I have implemented this addition part, which do addition on array a[ ] = [0 1 2 3 4 5]. And puts the newly obtained element at last index(which is dataSize in my code, please see data[dataSize++]=newItem).

Each time i call the function PositionAdjustOfNewItem(data,dataSize); giving the array(which also contains the newly obtained element at last index)as first argument and the newly obtained size as second argument.Here is the code below:

for(i=0;i<14;i++)
   for(j=1;j<15;j++)
   { 
      // This freq contains the given array (say a[]=[0 1 2 3 4 5] in our case and
      // it is inside the struct Array { int freq}; Array data[256]; )
      newItem.freq = data[i].freq + data[j].freq;
      data[dataSize++]=newItem;
      PositionAdjustOfNewItem(data,dataSize);  // Logic of this function I am not able to develop yet. Please help me here
      i=i+2; 
      j=j+1;
   }

I am not able to implement the logic of function PositionAdjustOfNewItem(), which pass the array data[], which contains all the elements and the newly added element at last index and in second argument i pass the newly obtained size of array after putting the newly obtained element at last index. Each time when i add two elements i call this PositionAdjustOfNewItem() passing the newly added elements at last and newly obtained size. which is supposed to be sorted by this function PositionAdjustOfNewItem().

This PositionAdjustOfNewItem() have as least complexity as possible.The part above the code was just to make you aware of mechanish i am using to add elements, You have nothing to do there, I need your help only in getting the logic of PositionAdjustOfNewItem(). (Even i already done it with qsort() but complexity is very high). so need any other way?

Answer 1

How about something like this:

NOTE: In your example, you are dealing with an array of some structure which has freq as a field. In my example, I am using simple integer arrays.

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

int a[] = {0,1,2,3,4,5};

int main(void) {
  int i,j;
  // Initialize a new array big enough to hold the result.
  int* array = new int[15];
  memcpy(array, a, 6*sizeof(int));
  int length=6;

  // Loop over consecutive indeces.
  for (i=0; i+1<length; i+=2) {
    // Get the sum of these two indeces.
    int sum=array[i]+array[i+1];

    // Insert the sum in the array, shifting elements where necessary.
    for (j=length-1; j>i+1; j--) { 
      if (sum >= array[j]) {
        // Insert here
        break;
      } else {
        // Shift
        array[j+1]=array[j];
      }
    }
    array[j+1]=sum;
    // We now have one more element in the array
    length++;
  }

  // Display the array.
  printf("{ ");
  for (j=0; j<length; j++) {
    printf("%d ", array[j]);
  }
  printf("}\n");
}

To insert the sum, what is done is we traverse the array from the end to the front, looking for the spot it belongs. If we encounter a value less then the sum, then we simply insert it after this value. Otherwise (i.e. value is greater than the sum), we need to insert it before. Thus, the value needs to be shifted one position higher, and then we check the previous value. Continue until we find the location.

If you only need the PositionAdjustNewItem method, then this is what it would look like:

void PositionAdjustOfNewItem(int* array, int length) {
  int newItem = array[length-1];
  for (int j=length-2; j>i+1; j--) { 
    if (sum >= array[j]) {
      // Insert here
      break;
    } else {
      // Shift
      array[j+1]=array[j];
    }
  }
  array[j+1]=sum;
}

When you run it, it produces the output you expect.

$ ./a.out
{ 0 1 1 2 3 3 4 5 6 9 15 }