立即将值置于排序位置 [英] place a value in the sorted position immediately

问题描述

我有一个问题的c ++实验室分配我有。任务是实现一些功能，用于添加值，从数组中删除值等。我现在做了大部分，但是我有一些问题与插入函数。该赋值要求我在不使用任何算法在每次插入之后对其排序的情况下将浮点值插入到此数组。我可能不会使用STL的任何东西。它会假设我立即在排序位置插入每个值

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
这个任务我不会用链表实现它。这将是我的下一次分配。

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

终于完成了，这里是完整的代码。感谢Mark和Casablanca的帮助

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

推荐答案

您必须移动所有元素才能为新元素腾出空间。这是一个O（n）操作。由于你不能比O（n）做得更好，我认为使用这个简单的O（n）算法是合理的：

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:

• i到数组中最后一个元素的索引


• 如果要插入的元素大于a [i]，则在索引i + 1插入元素并停止。


• 否则设置a [i + 1] = a [i]，然后减少i并重复上一步。


• 如果i达到0，

• 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.

这篇关于立即将值置于排序位置的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！