place a value in the sorted position immediately

Question

Hello, 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 implement 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

Answer 1

You can find the insert position using binary search.

Answer 2

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.

Answer 3

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;