別の配列の並べ替え順序を定義する配列があります。例えば、から成るアレイをソートするためにchar * data[] = {"c", "b", "a"};、sort_order配列は次のようになり{2, 1, 0}-アレイがソートされるときに、最初の要素がなければならない"c"（ありますdata[sort_order[0]]）。
（この背景には、並べ替える配列が2つありますが、2番目の配列は最初の配列と同じ並べ替え順序を使用する必要があります。したがって、基本的に{0, 1, 2}は最初の配列の値を使用して並べ替えてから、この並べ替え順序は、両方の配列の実際の値を並べ替えます。）
明らかな解決策は、配列（new_data）のコピーを作成し、並べ替え順序で定義されている正しい値をすべての要素に割り当てることです。
for (int i = 0; i < n; ++i)
{
new_data[i] = data[sort_order[i]];
}
ただし、これにはアレイのコピーを作成する必要があります。配列をコピーせずに、元の配列の要素を交換して所定の位置に並べ替える方法はありますか？
編集：「重複の可能性」は別の配列を使用しますが、これはまさに私が避けようとしていることです。
「サイクル」を回転させることにより、A []とI []の両方を並べ替えます。各ストアは適切な場所に値を配置するため、時間計算量はO（n）です。
// reorder A in place according to sorted indices in I
// tA is temp value for A
for(i = 0; i < n; i++){
if(i != I[i]){
tA = A[i];
k = i;
while(i != (j = I[k])){
A[k] = A[j];
I[k] = k;
k = j;
}
A[k] = tA;
I[k] = k;
}
}
Cを使用していることに気づきました。C++では、ラムダ比較関数を使用して、I []のインデックスに基づいてA []のメンバーを比較できます。Cの場合、インデックスI []の配列の代わりにポインタの配列P []を使用できます。
/* create array of pointers to A[] */
for(i = 0; i < n; i++)
P[i] = &A[i];
/* sort array of pointers, compare is custom compare function */
qsort(P, n, sizeof(P[0]), compare);
/* reorder A[] according to the array of pointers */
for(i = 0; i < n; i++){
if(i != P[i]-a){
tA = A[i];
k = i;
while(i != (j = P[k]-a)){
A[k] = A[j];
P[k] = &A[k];
k = j;
}
A[k] = tA;
P[k] = &A[k];
}
}
A []に整数が含まれている場合の、qsort（）のカスタム比較の例。qsort（）はcompare（）へのパラメーターとしてP []へのポインターを渡し、P []はポインターの配列であるため、compare（）に渡されるパラメーターはポインターへのポインターです。
int compare(const void *pp0, const void *pp1)
{
return( (**(int **)pp0) - (**(int **)pp1) );
}
目標がA []の並べ替えに基づいて、2番目の配列B []を並べ替えることである場合は、次のような行を追加します。
/* ... just after tA = A[i] */
tB = B[i];
/* ... just after A[k] = A[j] */
B[k] = B[j];
/* ... just after A[k] = tA */
B[k] = tB;
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加