0

How do I implement the following OrderElements function? 

char chars[] = {'a', 'b', 'c', 'd', 'e'};
int want_order[] = {2, 4, 3, 0, 1};
int length = 5;
OrderElements(chars, want_order, length);

// chars now contains: c, e, d, a, b

It's easy when you can use linear extra space, but can it be done with only constant extra space, i.e., directly sorting the chars elements in-place?

P.S.: This was not an exam question; I actually need this function.

CLARIFICATION: There seems to be a misunderstanding about the desired final order of elements. The resulting array in the example should have the following elements, referring to the original chars array:

{chars[2], chars[4], chars[3], chars[0], chars[1]}

which is

{'c', 'e', 'd', 'a', 'b'}.
Improve this question
4
  • Is the shuffle done by a weight or predefined specification? Commented Sep 27, 2009 at 21:40
  • @astander: I don't understand your question. want_order specifies the order we want ... Commented Sep 27, 2009 at 21:44
  • I think you need to elaborate what you mean by auxiliary memory. If you mean "space" it's not possible because the index can't be represented in O(1) Commented Sep 27, 2009 at 21:53
  • I think you should call it "rearrange" better than "sort" Commented Sep 27, 2009 at 22:09

6 Answers 6

Reset to default
6

Strictly speaking, though, O(lg length) memory is needed to represent the list index; I'm going to ignore this for this discussion, however, since using a 64-bit i is probably big enough for anything that we can actually reorder.

for (int i = 0; i < length; i++) {
  int t = want_order[i];
  while (t < i) {
    // t has been moved already; we need to find out where the value that started there
    // went. Since we must've put it at want_order[t] before, resume looking there
    t = want_order[t];
    // once t >= i, we know we've not touched that slot more than once, and so our
    // value is there
  }
  swap(chars[i], chars[t]);
}

An intuitive explanation: For each item in the array, we put the goal value in it, storing our old value in the slot that contained our goal value. We have to take care to deal with the case that our goal value was displaced; this is handled by noting that a given slot is only swapped up to twice; once when the value in there is stolen by another value (which couldn't have happened, since this iteration is going to do that) or when the value is displaced to insert the final value (which only happens to lower indices).

An illustration of how this looks on your sample data:

 i | want_order | chars     | t
 0 |  2 4 3 0 1 | a b c d e | 2 (swap)
 1 |  2 4 3 0 1 | c b a d e | 4 (swap)
 2 |  2 4 3 0 1 | c e d a b | 3 (swap)
 3 |  2 4 3 0 1 | c e d a b | 0 (follow)
 3 |  2 4 3 0 1 | c e d a b | 3 (swap - no-op)
 4 |  2 4 3 0 1 | c e d a b | 1 (follow)
 4 |  2 4 3 0 1 | c e d a b | 4 (swap - no-op)

This algorithm uses only O(lg n) memory (for the indices), but I have not attempted to fully analyze its running time. It's obvious that it's at worst O(n^2), however I suspect it will fare better than that in practice. However, there is no real bound on the length of the chains it might have to follow, so in principle it may in fact end up using O(n^2) time with worst-case input.

Improve this answer
Sign up to request clarification or add additional context in comments.

8 Comments

This is "Bubblesort" an well known sorting algorithm
It's pretty easy to see how this works: you never touch items that are in their correct position, yet you swap the position of two items exactly as much times as there are elements that are in the wrong position. Clearly this leads to no items in the wrong position.
This is not bubblesort. Bubblesort has running time O(n^2) and is applicable to any set with a comparator function. This is O(n) and applies only to the OP's specific problem.
This is more like a Knuth Shuffle for a non-random permutation. Or just what you might call a permutation algorithm I suppose.
The result will be {'d', 'e', 'a', 'c', 'b'}, although I was looking for an algorithm that results in {'c', 'e', 'd', 'a', 'b'}. There must be some misunderstanding? If c is the original chars array and want_order is {2, 4, 3, 0, 1}, the result I wanted is {c[2], c[4], c[3], c[0], c[1]}. I will add an update to the question to make this clearer.
|
1

Impossible.

You need at least O(log (list size)) to know the index of the sorted element.

Improve this answer

2 Comments

But O(1) with fixed-width data types like in real life. Of course then the maximum allowable list size is bounded ... also like in real life.
He asks for O(1) auxiliary memory -> Bubblesort
0

This will do the job in O(n²). In each iteration of the outer loop the currently wanted element is swapped down to its correct position (first inner loop) and then the wanted order of the remaining elements is adjusted to reflect the new situation (second inner loop).

for (int i = 0; i < length; i++)
{
    for (int j = wantedOrder[i]; j > i; j--)
    {
        Swap(chars, j, j - 1);
    }

    for (int j = i + 1; j < length; j++)
    {
        if (wantedOrder[j] < wantedOrder[i])
        {
            wantedOrder[j]++;
        }
    }
}

This of course requires destroying the wanted order array. If this is not allowed, I have no idea how to solve the problem (at least at the moment).

Improve this answer

Comments

0

The post above has an error (it inadvertantly overwrites an index). Here is a corrected version:

char chars[]      = {'a', 'b', 'c', 'd', 'e'};
int  want_order[] = {2, 4, 3, 0, 1};
int  length       = 5;

OrderElements(chars, want_order, length) {
  int i, j, k;

  for(i = 0; i < length; ++i) {
    if (want_order[i] == -1) continue;

    j = startPos = want_order[i];
    c = chars[i];
    do {
      swap(c, chars[j]);
      k = want_order[j];
      want_order[j] = -1;
      j = k
    } while(j != startPos);
  }
}
Improve this answer

Comments

0

It can be done If you are allowed to change the want_order array. The algorithm is rather simple as the permutation can be decomposed into cycles. When you iterating one cycle, just mark each one being visited. And the time complexity is O(N). Pseudo code:

char chars[]      = {'a', 'b', 'c', 'd', 'e'};
int  want_order[] = {2, 4, 3, 0, 1};
int  length       = 5;

OrderElements(chars, want_order, length) {
  int i, j, k;

  for(i = 0; i < length; ++i) {
    if (want_order[i] == -1) continue;

    j = startPos = want_order[i];
    c = chars[i];
    do {
      swap(c, chars[j]);
      k = want_order[j];
      want_order[j] = -1;
      j = k
    } while(j != startPos);
  }
}
Improve this answer

Comments

-1

Sort Operation with Memory O(1) is Bubblesort, but it have an Performance O(n²)

http://en.wikipedia.org/wiki/Bubble_sort

Improve this answer

15 Comments

A sort is not required here as the elements are a dense integer array, and moreover, bubblesort is a horrible sort for large n.
Also, bubblesort requires O(lg n) memory to operate on an indexed array, to hold the index value. This is usually ignored because lg n is very small in practice.
Ok, then explain how this should work with O(1) auxiliary memory?
O(1) is impossible. However because an index pointer into any dataset you're likely to deal with is likely to fit within 64 bits, in practice one can fudge things a bit and call the size of an index pointer O(1).
Indeed I do know what O means. My point is, people tend to call these things O(1) memory, even though they're really O(lg n) memory, because it's easy to forget about the memory usage of your indices, and because in practice it really doesn't matter. Once you get to n=2^64, you would be hard pressed to do anything with all elements of that set within human timescales. So, yes, in theory, bubble sort is O(lg n). In practice, lg n is small enough that we can ignore this effect. Clear?
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.