0

binary-search要素を挿入し、それを後続のes 呼び出しに並べ替える必要があるという並べ替えがあります。どのアルゴリズムを使用すればよいですか? それとも、これは時期尚早の最適化であり、要素を挿入してシェルソートを呼び出す必要があります(現在の代わりに実装します)?

この情報が役立つ場合: 要素の数は実際には大きい可能性があります。これは本当に可変であり、1 から 10 または 1 から 1000 以上の要素を保持できます。これがあまりにも多くの変数である理由に興味がある場合は、解析を書いています。

4

1 に答える 1

1

配列のサイズがこれ以上エントリに収まらない場合は、別の大きな配列を割り当て、すべてのエントリを新しいエントリが配置される位置まで移動し、そこにエントリを配置して、最後に残りのエントリを1つ上の位置に移動する必要があります。彼らよりも。その後、古いアレイと現在は小さすぎるアレイを解放して、新しいアレイを保持できます。あなたはそれを使うmemmoveかmemcpyすることができます。

これを行うには、新しい大きな配列を割り当てる必要がある場合、すぐに必要なものよりも少し大きく割り当てる必要があります（メモリページサイズの倍数が適切です）。そうしないと、すべての割り当てと解放にコストがかかります。

例：

int *array[] = malloc(3*sizeof(int));
array[0] = 0;
array[1] = 2;
array[2] = 3;

// To insert 1 for example you will have to do...
int *new_array[] = malloc(4*sizeof(int)); // Just for the example I make a tight fit, on the code you should allocate it a bit bigger if you expect more inserts to avoid unnecessary mallocs and frees

memmove(new_array,array,sizeof(int)); // Moving the 0
new_array[1] = 1; // Inserting the new element
memmove(new_array[2],array[1],2*sizeof(int)); // Moving the 2 and 3

free(array); // Get rid of the old array
array = new_array;
new_array = NULL;
于 2013-03-16T21:06:16.197 に答える