c - Cのインデックス配列で配列をソートする

Question

重複の可能性:
インプレース配列の並べ替え?

次のような構造を持つ元のソートされていない配列があります。

{D, A, B, E, C}

およびソートされた順序での元の配列のインデックスの配列:

{2, 3, 5, 1, 4} // Edited. Then I get {A, B, C, D, E}.

元の配列をインデックス配列で単純に再配置するにはどうすればよいですか?

新しい配列を作成できず、インデックス位置で要素を挿入できません。

Answer 1

私の5セント：

int new_i;
for (int i = 0; i < arr_size-1; ++i)
{
    while ((new_i = index_arr[i]-1) != i)
    {
        std::swap(struct_arr[i], struct_arr[new_i]);
        std::swap(index_arr[i], index_arr[new_i]);
    }
}

Answer 2

O(N^2) 解:

struct S[] = {D, A, B, E, C};
int o[] = {2, 3, 5, 1, 4};
int len = 5;

for (int i=1;i<=len;++i) {
  for(int j=i-1; j<len;++j) {
    if(o[j]==i) {
      if (i!=j+1) {
        swapSArrayItems(S, j, i-1);
        swapIntArrayItems(o, j, i-1);
      }
      break;
    }
  }
}

Answer 3

indices動作するバージョンは次のとおりですが、変数が無効になることに注意してください。

void sortItemsBasedOnIndices(char *items[], int indices[], size_t num)
{
    // sort them
    for (int i = 0; i < num; i++)
    {
        int newIndex = indices[i];

        // take out the item at the specified index
        char *newItem = items[newIndex];

        // take out the item in that current position
        char *oldItem = items[i];

        // swap the two items
        items[i] = newItem;
        items[newIndex] = oldItem;

        // now, tell the sorted indices the location of the old item after swap
        for (int j = i; j < num; j++)
        {
            if (indices[j] == i)
            {
                indices[j] = newIndex;
                break; // we only need the first one, so then we're done
            }
        }
    }
}

int main()
{
    char *items[] = { "D", "B", "E", "A", "C" };
    int sortedIndices[] = { 3, 1, 4, 0, 2 }; // 0-based

    int size = 5;
    sortItemsBasedOnIndices(items, sortedIndices, size);

    for (int i = 0; i < size; i++)
    {
        puts(items[i]);
    }
}

Answer 4

#include <stdio.h>

void shuffle( char **arr, int *offs, size_t cnt);

void shuffle( char **arr, int *offs, size_t cnt)
{
unsigned idx,src,dst;

for (idx=0; idx < cnt; idx++) offs[idx] -= idx;

for (idx=0; idx < cnt; idx++) {
        if (offs[idx] == 0) continue;
        char *tmp;
        tmp = arr[idx];

        for(dst = idx; offs[dst] ; dst=src) {
                src = dst+offs[dst] ;

                arr[dst] = arr[src];
                offs[dst] = 0;
                if (offs[src] == 0 ) break;
                }

        arr[dst]=tmp;
        }
}


int main (void)
{
unsigned idx;
char *array[5] = {"D","A","B","E","C"};
int index[5] =  {1,2,4,0,3};

fprintf(stdout, "Original:\n");
for (idx=0; idx < 5; idx++) {
        fprintf(stdout, "[%u]:%s\n", idx, array[idx] );
        }

fprintf(stdout, "Shuffle:\n");
shuffle( array, index, 5);

fprintf(stdout, "After shuffle:\n");
for (idx=0; idx < 5; idx++) {
        fprintf(stdout, "[%u]:%s\n", idx, array[idx] );
        }

return 0;
}

更新: チェーンの終わりの状態を修正 (醜い!)