Edit Question - KnowledgeHub

Title Body

Lets say I have an array of interlaced data, such as 1a2b3c4d5e, and I want to de-interlace it into an array that looks like 12345abcde, in place (without a temporary buffer). What would be the fastest way of doing this? What I have so far is this template<typename T> void deinterlace(T* arr, int length){ if(length<=1) return; int i = 1; for(i = 1; i*2<length; i++){ //swap i with i*2 T temp = arr[i]; arr[i] = arr[i*2]; arr[i*2] = temp; } deinterlace(arr+i, length-i); } which unfortunately doesn't work with arrays not a power of 2 in size edit : this algo fails at larger powers of 2 anyway so I guess I'm at square 0 again edit 2 : I have found an nlogn algorithm for this, given either an O(n) array rotate function, or an initial size which is a power of 2 works like so: 1a2b3c4d5e6f7g, "chunk size" = 1 initial, split into groups of chunk size *4 1a2b 3c4d 5e6f 7g swap the inner 2 chunks of each group 12ab 34cd 56ef 7g repeat with chunk size = chunk size *2 12ab34cd 56ef7g (read: 56 ef 7 g) -> 1234abcd 567efg 1234abcd567efg -> 1234567abcdefg template<typename T> void deinterlace(T* arr, int length, int group_ct = 1){ if(group_ct*2 >= length) return; for(int i = 0; i<length; i+=group_ct*4){ int rot_count = group_ct; int i1 = i + group_ct; int i2 = i+group_ct*4 - group_ct; if(i2+group_ct > length){ i2 = i1 + (length-i1)/2+group_ct/2; } rotate(arr, i1, i2, group_ct); } deinterlace(arr, length, group_ct * 2); } edit 3 I guess the correct term is deinterleave, not deinterlace

Tags (comma-separated) Cancel