3

Possible Duplicate:
In-place array reordering?

I have original unsorted array with structures such as:

{D, A, B, E, C}

and array of indexes of original array in sorted order:

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

How can I simply rearranged the originial array by an index array?

I can't create new array and insert elements by index-position.

Community
  • 1
  • 1
Peter K.
  • 151
  • 2
  • 13
  • People, **he's not looking to sort the array.** he want to rearrange it by index-value from the second array without an intermediate array. – WhozCraig Oct 27 '12 at 17:13
  • Note C uses 0-based indexing, so the index array should be `{1,2,4,0,3}` – wildplasser Oct 27 '12 at 17:15
  • This was actually a fun homework assignment when I had it - have any classmates to throw ideas about this? –  Oct 27 '12 at 17:30
  • **The question has been asked and answered many times before.** I posted a link above, but there are many other answers as well. – AnT stands with Russia Oct 27 '12 at 17:34
  • Is it homework or actual project? If it is the project, this is design failure because if two arrays are associated, you should have made a struct holding both index and value, and then you will be able to use qsort. If it is an assignment, look into qsort implementation, and swap both values in both array at the same time. – SwiftMango Oct 27 '12 at 17:34
  • 2
    @texasbruce: No, it isn't. On the contrary, cramping unrelated and/or temporary data together into a struct would be a design failure. What is requested here is used, for example, in a classic approach when several independent arrays have to be sorted by one specific key array. The proper approach is to generate the sorting permutation from the key array (i.e. kinda "extract" the ordering information from the key array) and then "apply" that permutation to all other arrays. The OP's question is about proper technique for "applying" permutations. That's a classic programming problem. – AnT stands with Russia Oct 27 '12 at 17:35
  • The standard `qsort()` could very well be used here. In `qsort()`s comparsion function one calculates the index of the two elements to be compared via pointer differences to the array base and then one pulls the sort index from aside to do the actual comparsion. Not nice but straight forward. – alk Oct 27 '12 at 19:33

4 Answers4

5

My 5 cents:

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]);
    }
}
panda-34
  • 4,089
  • 20
  • 25
  • 1
    The question is tagged [tag:c] not [tag:c++]. – Olaf Dietsche Oct 27 '12 at 17:45
  • 1
    Well, std::swap function is trivial, so consider this a pseudocode algorithm instead of executable code. – panda-34 Oct 27 '12 at 17:52
  • 1
    This is actually a very compact (and, apparently, correct) implementation of the standard cycle-following algorithm. The implementations given in the older thread linked above are less compact but more optimized (i.e. they copy array elements instead of swapping them), but the main principle is the same. As all such implementations, it destroys the index array (or requires additional memory for a "flag" array). – AnT stands with Russia Oct 27 '12 at 17:56
  • This does seem both correct and optimal, I hope the OP changes the accepted answer to this. – hyde Oct 28 '12 at 06:18
  • this in not the solution for the question...and anyway "new_i = index_arr[i]-1" causes new_i to become -1 ... – Asylum May 12 '15 at 20:55
2

O(N^2) solution:

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;
    }
  }
}
hyde
  • 60,639
  • 21
  • 115
  • 176
  • 1
    The indexes are there to reduce the complexity, not raise. Without any additional information the array is sortable in O(nlogn). Clearly, the solution needs to be better than that. – SomeWittyUsername Oct 27 '12 at 17:24
  • Yes, but question said "simply" :). Anyway, in-place sort which would use given swap and compare functions would work, I hope somebody bothers to write one as an answer. – hyde Oct 27 '12 at 17:30
  • @icepack At least it *works*. That's why I upvoted it :) – P.P Oct 27 '12 at 17:36
  • @KingsIndian no need to be sarcastic, I know to accept my misdoings :) But accepting O(n^2) for such a question is clearly not the required answer – SomeWittyUsername Oct 27 '12 at 17:38
  • The "sortedness" of the final result has absolutely noting to do with this question. The question is about in-place reordering in accordance with an arbitrary permutation. The fact that the result happens to be "sorted" in this case is noting more than a random property of an arbitrary permutation given as an example. – AnT stands with Russia Oct 27 '12 at 17:42
  • @icepack I am really not being sarcastic. Working solution should be higher up than not-working ones. OP hasn't mentioned any time complexity either. If a better one comes up later, I'll upvote that too and many others will also upvote and it'll beat this one. – P.P Oct 27 '12 at 17:45
0

Here's a version that works, but note that it does invalidate the indices variable:

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]);
    }
}
ryanpattison
  • 6,151
  • 1
  • 21
  • 28
Richard J. Ross III
  • 55,009
  • 24
  • 135
  • 201
  • 1
    The indexes are there to reduce the complexity, not raise. Without any additional information the array is sortable in O(nlogn). Clearly, the solution needs to be better than bubble-sort. – SomeWittyUsername Oct 27 '12 at 17:29
  • @icepack this is much better than a bubble sort. It only iterates as far as it needs to. best case scenario is O(N), worst case is O(2N) – Richard J. Ross III Oct 27 '12 at 17:30
  • 2
    @RichardR.RossIII that's a typical bubble sort running at O(n^2) – SomeWittyUsername Oct 27 '12 at 17:32
  • @icepack look again, I encourage you. I only iterate through a second time as far as I need too, and not a second full loop which would turn into O(n^2). Worst case scenario is reversing the array, which has performance of O(2n). – Richard J. Ross III Oct 27 '12 at 17:34
  • 1
    That's a typical optimized bubble-sort. There are many examples on the net of such things. It's still O(n^2) – SomeWittyUsername Oct 27 '12 at 17:41
  • Even if inner loop is always much fewer iterations than N (average 0.25 * N, says my instinct without thinking too much), that's still N*0.25*N, which is O(N^2), just like my answer. To be better, you have to follow the chain of final positions, so you never have to do an unnecessary swap. – hyde Oct 28 '12 at 06:15
  • it isn't O(n^2) but it's not O(2n) either :D For a 11 element array the worst case scenario gave me 41 iterations. – Asylum May 12 '15 at 20:51
0
#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;
}

Update: fixed end of chain condition (ugly!)

wildplasser
  • 43,142
  • 8
  • 66
  • 109