insert into sorted array

Question

I want to insert an element into the right place that order maintains in the sorted list. I allocated 2*n size for the array and filled the rest with 999 since they are not used currently.

ordered_insert(int number,int array[],int size){
 int i=0;
 int temp1,temp2,index;
 while(eleman>array[i]){
   i++;}

//push the rest to right by one
index=i;

if(i<size){
    temp1=array[i];
    temp2= array[i+1];
    array[i+1]=temp1;
    array[i+2]=temp2;
    i++;
    }

array[index]=number;

}

I couldn't figure out how to overwrite 999s or is there a better way instead?

Answer 1

you can

memmove(&array[i+1], &array[i], (size - i) * sizeof array[i]);

EDIT:

The 999 trick is not needed; just record the number of used elements in size (and add appropriate boundary checks).

Answer 2

In order to move all the latter array elements one step ahead, you will have to traverse the array backwards so that you do not over-write the elements.

Once you get the index,

int i = size;
while ( i > index ) {
  array[i] = array[i-1];
  i--;
}
array[i] = number;
size++;

Answer 3

// 1. initialise i (the 'hole' index) to the last element in the array
// 2. if the preceeding array element is larger than the newValue
// 3.   move the preceeding element into the 'hole' at i, moving the hole up a position
// 4.   reverse through the array
// 5. else put the newValue into the hole and we're done 

i = ARRAY_SIZE-1;  
while (i>0 && array[i-1]>newValue) {
  array[i] = array[i-1];
  i--;
}
array[i] = newValue;                            

Answer 4

To push the rest of the array element's you should use a loop. Just be carfare you should start pushing from the last element otherwise you will assign the rest of elements with the same value

int i=size-1; // Not i=size (this is the size of the array not the last index)
while (i>index){
array[i] = array[i-1];
i--;
}
array[i] = number;

about assigning the unused elements with 999 it's not required just define a key to remember the last element and use it instead of size, then when inserting a new element just check if you reached the size of the array.