要素をcで配列に追加し、昇順に並べ替える

Question

cでaddArray関数が必要です。これは、指定された要素を特定の配列に追加し、すべての要素が配列の正しい場所に挿入されるようにします。整数の昇順です。

• プロトタイプint ADDARRAY（int型*編曲、int型sizeofArray、int型numToAdd）
• 挿入する正しいインデックスを見つけます。
• 他の要素を移動して調整します。
• 正しいインデックスに新しい要素を格納します。
• 配列のサイズを返します。

この機能のヘルプはありますか？

int addToArray(int *array, int size, int selectedNum){ 
    //printf("Selected number is %d \n", selectedNum); 
    int indexToInsert=0; 
    if(size==0){ 
     array[indexToInsert]=selectedNum; 
     size=1; 
     indexToInsert++; 
     return size; 
    } 
    else{ 

     for(int i=size; i<=1; i--){ 
      if(selectedNum>array[i]){ 
       indexToInsert=i-1; 
       break; 
      } 
      else{ 
       } 
     } 
     if(indexToInsert>0){ 
      for(int j=size-1; j>indexToInsert; j--){ 
       array[j+1]=array[j]; 
      } 
      array[indexToInsert]=selectedNum; 
      size = size+1; 
      printf("Size incremented to %d\n", size); 
      return size; 

}

要件は次のとおりです。単純に配列とソートに要素を追加しないでください。これは、正しいindex.Thisに格納される必要があります私はこの機能のために持っている。それが正しく動作していない。メインプログラムは、負の数を入力するまでユーザにプロンプ​​トを表示し、各正の数は昇順で配列に追加されます。

Answer 1

残りの配列（挿入後）要素を+1位置で動かすと、非常に高価なになるため、挿入操作が多数ある場合や任意のランダムな位置では、配列の選択はそれほど賢明ではありません件

より良い方法：デフォルトで値を昇順で格納し、重複する値をキーとして格納するmultimapまたはpriority-queueを使用します。次に、キーを配列の先頭から最後まで繰り返して配列に格納します。

TC: O(NlogN) for insertions + O(N) for last traversal of map => O(NlogN). 

それでも挿入操作をしながらbinary search mechanismを採用し、その後、アレイと他のデータ構造を使用したい場合。

TC: O(NlogN) for insertions + O(N^2) for moving => O(N^2). 
Worst case scenario: when the input stream is in descending order, and 
        the final array is expected to be in ascending order.