немедленно поместить значение в отсортированную позицию

Question

У меня вопрос к лабораторному заданию на c ++. Задача состоит в том, чтобы реализовать некоторую функцию для добавления значений, удаления значений из массива и так далее. Я сделал большую часть этого сейчас, однако у меня есть некоторые проблемы с функцией вставки. Присвоение требует, чтобы я вставил значения с плавающей точкой в ​​этот массив без использования какого-либо алгоритма для его сортировки после каждой вставки. Я не могу использовать что-либо из STL либо. Предполагается, что я сразу вставлю каждое значение в отсортированную позицию

Так вот, мне интересно, кто-нибудь может подсказать, как решить эту проблему?

EDIT Это задание я не собираюсь реализовывать с помощью связанного списка. Это будет для моего следующего назначения.

Я попытался написать функцию вставки в соответствии с вашим псевдокодом. Я не понял это правильно, хотя. Вот код в любом случае.

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++;
}

наконец-то закончил, вот полный код. Спасибо за помощь от Марка и Касабланки

Answer 1

Вы должны сдвинуть все элементы, чтобы освободить место для нового элемента. Это операция O (n). Поскольку вы не можете добиться большего успеха, чем O (n), я думаю, что разумно использовать этот простой алгоритм O (n):

• Установить i в индекс последнего элемента в массиве
• Если элемент для вставки больше, чем a [i], вставьте элемент с индексом i + 1 и остановитесь.
• В противном случае установите a [i + 1] = a [i], затем уменьшите i и повторите предыдущий шаг.
• Если я достигну 0, вставить элемент в начале.

Предполагается, что в вашем массиве есть место для вставки дополнительного элемента.

Answer 2

Подумайте об отдельных задачах, которые необходимо выполнить для вставки:

1. Найдите индекс n того, где новый элемент должен быть
2. переместить каждый элемент с последнего на n (включительно) вверх на один слот в массиве (только если в массиве есть неиспользуемые ячейки, в противном случае сдаться и сообщить об ошибке)
3. поместите новый элемент в array[n]

Первые два шага могут легко быть их собственными функциями и помогут вам мысленно разделить задачи:

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;

Answer 3

Вы можете найти позицию вставки, используя бинарный поиск .