Algorithm for in-place reordering of array [duplicate]

Question

Possible Duplicate:
Reordering of array elements
Interview test - rearrange the array

I have an array where three semantic elements (a,b,c) are stored in the form:

[a][b][c][a][b][c][a][b][c]...

This means that a b and c are not actual values. The first a might be 10, the second 1, the third 25, and so on. a b and c says that the program will give all indices where you see an "a" a certain semantic meaning, the same for b and c.

I want to reorder so it has the form:

[a][a][a]...[b][b][b]...[c][c][c]....

Is there a way to do this "in-place", meaning without the usage of a temporary "buffer" array?

An example with values:

Starting array:

[11][5][3][284][123123][841823][0][11][22]

I need to reorder it to:

[11][284][0][5][123123][11][3][841823][22]

This Wikipedia article may answer your question: In-place matrix transposition. — Evgeny Kluev
– Evgeny Kluev, Commented Nov 30, 2012 at 14:45
Most sorting algorithms, from bubblesort to quicksort, are done in place. — Sergey Kalinichenko
– Sergey Kalinichenko, Commented Nov 30, 2012 at 14:46
It's not about sorting. Perhaps I should have been more clear. The a,b and c elements are semantic elements, not the actual values inside the array. I will update the question :-) — TravisG
– TravisG, Commented Nov 30, 2012 at 14:50

mhsekhavat · Accepted Answer · 2012-11-30 15:56:28Z

0

There is an O(n.lgn) time divide-and-conquer algorithm with O(1) additional memory usage:

Assume that you want to reorder the 3n-sized array bellow:

A=[1,n+1,2n+1, 2,n+2,2n+2, ... , n,2n,3n].

Divide A into two subarrays A1 and A2, A1 including indices numbered from 1 to 3*[n/2], and A2 including indices 3*[n/2]+1 to 3n. Reorder A1 and A2 (in-place) recursively. Then, A becomes something like a 6-parted array [p1,p3,p5,p2,p4,p6] that each part is a correctly-ordered subarray of consequent elements and you can just re-order them into [p1,p2,p3,p4,p5,p6] in O(n) in-place with swap operations.

T(n)=2T(n/2)+O(n)=O(n lgn)

edited Nov 30, 2012 at 15:56

answered Nov 30, 2012 at 15:45

mhsekhavat

1,02714 silver badges20 bronze badges

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

Collectives™ on Stack Overflow

Algorithm for in-place reordering of array [duplicate]

1 Answer 1

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Linked

Related