place a value in the sorted position immediately

I have a question for a c++ lab assignment I have. The task is to implement some function for adding values, remove values from an array and so on. I have done most of it now, however I have some problem with the insert function. The assignment requires me to insert float values to this array without using any algorithm to sort it after each insert. I may not use anything from STL either. It will assume that I insert every value in sorted position immediately

So I wonder if someone could give me any clue how this problem can be solved?

EDIT This assignment I am not going to imple开发者_如何学运维ment it with linked list. It will be for my next assignement.

I have tried to write a insert function according to your pseudo code. I did not get it correctly though. Here's the code anyway.

void array_insert(data_t list[], int& space_used, data_t value)
{

   if(space_used == 0)
   {
      list[space_used] = value;    
   }
   else
   {

      for(int i = space_used+1; i >= 0; i--)
      {
         if(value > list[i])
         {
            list[i+1] = value;
            break;
         }
         else
         {
            list[i+1] = list[i];
         }
         if(i == 0)
         {
            list[i] = value;
         }
      }
   }
   space_used++;
}

finally finished, here's the complete code. Thanks for the help from Mark and Casablanca

You have to shift all elements to make room for the new element. This is an O(n) operation. Since you can't do better than O(n) I think it is reasonable to use this simple O(n) algorithm:

• Set i to the index of the last element in the array
• If the element to insert is larger then a[i] then insert the element at index i+1 and stop.
• Otherwise set a[i+1] = a[i] then decrease i and repeat the previous step.
• If i reaches 0, insert the element at the start.

This assumes that your array has space to insert an extra element.

You can find the insert position using binary search.

Think about the separate tasks that need to be done to insert:

1. Find the index n of where the new element should be
2. move every element from last to n (inclusive) up one slot in the array (only if there is unused cells in the array, otherwise give up and report an error)
3. put the new element in array[n]

The first two steps could easily be their own functions and would help you mentally separate the tasks:

1. n = index_to_put(float new_element, float *array, int array_max, int last_used);
2. new_last_used = move_cells_up(float *array, n, int array_max, int last_used);
3. array[n] = new_element; last_used = new_last_used;