zzczzzzz's blog

Maintaining Relative Order while Sorting Odd and Even Numbers
By zzczzzzz, history, 4 months ago, In English 
Given an array of integers, our goal is to rearrange its elements so that all odd numbers are on the left side and all even numbers are on the right side, while keeping the relative order of elements unchanged.
 How would you do?
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Make an auxiliary array, and loop over the given array twice.

Get all the odds on the first round and all the evens on the second.

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

in 0 based indexing, swap each ith element with (2*i)th element for first half of the array, you will get the desired arrangement

→ Reply
»
4 months ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

I would use STL:

std::stable_partition(a.begin(), a.end(), [](int x) { return x % 2 != 0; });

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Use stable partition. Stable partition rearranges in True first order. So your condition of partition should be i % 2. stable_partition(all(A), [] (int i) {return i % 2;});

→ Reply