Weaving an array

Question

In preparing this answer, one of the components was an algorithm to rearrange a sorted array in a particular way. To put it succinctly, here's the problem description:

Given an array \$A\$ with \$n\$ elements \$A = \{ A_1, A_2, A_3, \dots , A_{n-2}, A_{n-1}, A_{n} \}\$ rearrange the contents such that the resulting array is \$A' = \{ A_1, A_n, A_2, A_{n-1}, A_3, A_{n-2}, \dots \}\$

I decided to create a templated function modeled on std::reverse that only uses two bidirectional iterators. Here's the templated function:

#include <algorithm> 

template<class BidirIt>
void weave(BidirIt first, BidirIt last) {
    if ((last - first) < 3) {
        return;
    }
    for (++first; first != last; ++first) {
        std::reverse(first, last);
    }
}

This is the code in context with a short test program.

testweave.cpp

#include <utility>
#include <algorithm>
#include <iostream>
#include <vector>

std::ostream& operator<<(std::ostream& out, const std::vector<int>& v) {
    if (v.begin() == v.end()) {
        return out << "{}";
    }
    out << "{" << *v.begin();
    for (auto it = v.begin()+1; it != v.end(); ++it) {
        out << ", " << *it;
    }
    return out << "}";
}

#define SHOW(x) std::cout << # x " = " << x << '\n'

template<class BidirIt>
void weave(BidirIt first, BidirIt last) {
    if ((last - first) < 3) {
        return;
    }
    for (++first; first != last; ++first) {
        std::reverse(first, last);
    }
}

int main()
{
    std::vector<int> v;
    for (int i=0; i < 10; ++i) {
        std::cout << '\n';
        SHOW(v.size());
        SHOW(v);
        weave(v.begin(), v.end());
        SHOW(v);
        v.push_back(i);
        std::sort(v.begin(), v.end());
    }
}

I'm particularly interested in whether there is a more efficient algorithm for this.

Answer 1

Just glancing at it, this:

template<class BidirIt>
void weave(BidirIt first, BidirIt last) {
    if ((last - first) < 3) {
        return;
    }

...jumped out--although the template parameter seems to imply that you want this to work for bidirectional iterators, the subtraction will only work for a random access iterator. To work for bidirectional iterators, you'll want to use std::distance instead.

Although it's only in the test code:

std::ostream& operator<<(std::ostream& out, const std::vector<int>& v) {
    if (v.begin() == v.end()) {
        return out << "{}";
    }

...I'd prefer if (v.empty()) {

As far as the algorithm goes, yes, there's better. In particular, it looks like your current algorithm is \$O(N^2)\$, but it's possible to do the job in \$O(N)\$ (as you probably expected).

The first step would be to reverse the entire second half of your input. From there you can use an in-place shuffle algorithm. Also see an old answer on SO.

Answer 2

More efficient way

Your current algorithm runs in \$O(N^2)\$ time. At the time I started thinking about this, I did not read Jerry Coffin's link that demonstrated an \$O(N)\$ solution, so I came up with my own \$O(N \log N)\$ solution based on a divide and conquer algorithm. Basically, the way it works is to reverse the second half, and then call a function that interleaves the first half with the second half. This interleaving function does the following:

1. Divide the array into quarters
2. Swap the middle two quarters
3. Recurse on the left half and the right half

To demonstrate how this works, consider this array of size 8:

0 1 2 3 4 5 6 7

Swapping the middle quarters (2 3) with (4 5):

0 1 4 5 2 3 6 7

Recurse on left half 0 1 4 5 and right half 2 3 6 7:

0 1 4 5 -> 0 4 1 5 (swap 1 and 4)
2 3 6 7 -> 2 6 3 7 (swap 3 and 6)

Final:
0 4 1 5 2 6 3 7

There is a slight complication if the length does not divide in half evenly. This complication is explained in the comments of the code.

The code

#include <stdio.h>
#include <stdlib.h>

static void weaveHalves(int *array, int start, int len);

void printArray(int *array, int len)
{
    for (int i=0; i < len; ++i)
        printf("%d ", array[i]);
    printf("\n");
}

// Takes an array, and interleaves its first half with the reverse of the
// second half:
//
// 0 1 2 3 4 5 6 7  (First half = 0 1 2 3) (Rev 2nd half = 7 6 5 4)
// 0 7 1 6 2 5 3 4
void weave(int *array, int start, int len)
{
    int halfLen = len >> 1;
    int mid     = start + halfLen;
    int end     = len - 1;

    // First step: reverse the second half.
    while (mid < end) {
        int tmp = array[mid];
        array[mid++] = array[end];
        array[end--] = tmp;
    }

    // Next step, weave the first half with the second half.  If the length
    // of the array is odd, only weave len-1 entries because the last entry
    // is in the correct place already.
    weaveHalves(array, start, len & ~1);
}

// Takes an array, and interleaves its first half with its second half:
//
// 0 1 2 3 4 5 6 7  (First half = 0 1 2 3) (Second half = 4 5 6 7)
// 0 4 1 5 2 6 3 7
//
// Note: len must always be an even number.
static void weaveHalves(int *array, int start, int len)
{
    int halfLen    = len >> 1;
    int mid        = start + halfLen;
    int quarterLen = halfLen >> 1;

    if (len <= 2)
        return;

    if ((halfLen & 1) == 0) {
        // If the half itself is even, then we can just swap the middle
        // quarters, since the left quarter is the same size as the right
        // quarter:
        //
        // 0 1 2 3 4 5 6 7 (Left to swap: 2 3) (Right to swap: 4 5)
        // 0 1 4 5 2 3 6 7 (After swapping)
        int leftIndex  = start + quarterLen;
        int rightIndex = mid;
        for (int i = 0; i < quarterLen; i++) {
            int tmp = array[leftIndex];
            array[leftIndex++]  = array[rightIndex];
            array[rightIndex++] = tmp;
        }
        // Recurse on halves.
        weaveHalves(array, start, halfLen);
        weaveHalves(array, mid, halfLen);
    } else {
        // If the half is not even, then the left quarter will be one larger
        // than the right quarter, and we need to do a more clever swapping:
        //
        // 0 1 2 3 4 5 6 7 8 9 (Left to swap: 2 3 4) (Right to swap: 5 6)
        // 0 1 5 6 2 3 4 7 8 9 (After swapping)
        //
        // To do the swapping, we first save the end of the left half, which
        // leaves equal length sides to move:
        //
        // 0 1 2 3 - 5 6 7 8 9 (save = 4) (Left to move: 2 3) (Right: 5 6)
        //
        // Then we swap in the hole (-) with the first left entry:
        //
        // 0 1 - 3 2 5 6 7 8 9
        //
        // Then we swap the hole with the first right entry:
        //
        // 0 1 5 3 2 - 6 7 8 9
        //
        // Then we continue to swap the hole with left and right entries:
        //
        // 0 1 5 - 2 3 6 7 8 9
        // 0 1 5 6 2 3 - 7 8 9
        //
        // Finally we fill in the saved entry and we are done:
        //
        // 0 1 5 6 2 3 4 7 8 9
        //
        int leftIndex  = start + quarterLen;
        int rightIndex = mid;
        int endOfLeft  = array[rightIndex-1];

        for (int i = 0; i < quarterLen; i++) {
            // Note: the hole is always at rightIndex-1 here.
            array[rightIndex-1] = array[leftIndex];
            array[leftIndex++]  = array[rightIndex++];
        }
        array[rightIndex-1] = endOfLeft;

        // Recurse on halves, which are not the same size.
        weaveHalves(array, start, halfLen - 1);
        weaveHalves(array, mid-1, halfLen + 1);
    }
}

int main(int argc, char *argv[])
{
    int size;
    int *array;

    if (argc < 2)
        size = 10;
    else
        size = atoi(argv[1]);

    array = calloc(size, sizeof(*array));

    for (int i=0; i < size; ++i)
        array[i] = i;
    // printArray(array, size);
    weave(array, 0, size);
    // printArray(array, size);
}

The linear time solution

I implemented the \$O(N)\$ solution linked by Jerry Coffin to see whether it was measurably better than my solution. Here is the code for it:

#include <stdio.h>
#include <stdlib.h>

static void inPlaceShuffle(int *array, int len);
static inline void cyclePermute(int *array, int start, int len);
static inline void reverseArray(int *array, int start, int end);

void printArray(int *array, int len)
{
    for (int i=0; i < len; ++i)
        printf("%d ", array[i]);
    printf("\n");
}

// Takes an array, and interleaves its first half with the reverse of the
// second half:
//
// 0 1 2 3 4 5 6 7  (First half = 0 1 2 3) (Rev 2nd half = 7 6 5 4)
// 0 7 1 6 2 5 3 4
void weave(int *array, int start, int len)
{
    int halfLen = len >> 1;
    int mid     = start + halfLen;
    int end     = len - 1;

    // First step: reverse the second half.
    while (mid < end) {
        int tmp = array[mid];
        array[mid++] = array[end];
        array[end--] = tmp;
    }

    // Second step, swap the first and second half, because the shuffler
    // makes the second half go first.
    for (int i=0, mid=start + halfLen; i < halfLen; i++) {
        int tmp = array[start];
        array[start++] = array[mid];
        array[mid++]   = tmp;
    }

    // Next step, weave the second half with the second half.  If the length
    // of the array is odd, only weave len-1 entries because the last entry
    // is in the correct place already.
    inPlaceShuffle(array, len & ~1);
}

// Takes an array, and interleaves its second half with its first half:
//
// 0 1 2 3 4 5 6 7  (First half = 0 1 2 3) (Second half = 4 5 6 7)
// 4 0 5 1 6 2 7 3
//
// Note: len must always be an even number.
//
// Solution taken from this article: http://arxiv.org/pdf/0805.1598v1.pdf
static void inPlaceShuffle(int *array, int len)
{
    int k = 0;
    int m = 0;
    int n = len >> 1;

    if (len < 2)
        return;
    if (len == 2) {
        int tmp = array[0];
        array[0] = array[1];
        array[1] = tmp;
        return;
    }

    // Step 1: Find k such that 3^k <= len < 3^(k+1)
    //         Then set m = (3^k - 1) / 2
    for (m = 1; m <= len; k++, m *= 3);
    k--;
    m = ((m / 3) - 1) >> 1;

    // Step 2: Do a cyclic right shift of A[m, ..., n+m-1] by a distance m
    //         where n is len/2.
    reverseArray(array, m, n+m-1);
    reverseArray(array, m, m+m-1);
    reverseArray(array, m+m, n+m-1);

    // Step 3: For i = 0 .. k-1, do a cyclic permutation starting at 3^i-1
    for (int i = 0, start = 1, mlen = m+m; i < k; i++, start *= 3) {
        cyclePermute(array, start-1, mlen);
    }

    // Step 4: Recurse on A[2m, ..., 2n-1]
    inPlaceShuffle(array + m + m, len - m - m);
}

// Reverse array from index start to index end inclusive.
static inline void reverseArray(int *array, int start, int end)
{
    while (start < end) {
        int tmp = array[start];
        array[start++] = array[end];
        array[end--]   = tmp;
    }
}

// Starting from index start, permutes the elements in a cycle, where the
// new permutation is the shuffled permutation.
static inline void cyclePermute(int *array, int start, int len)
{
    int halfLen = len >> 1;
    int i       = start;
    int hold    = array[i];
    int next    = halfLen + (i >> 1);

    while (next != start) {
        array[i] = array[next];
        i        = next;

        // array[i] in the final array is:
        //
        // array[halfLen + i/2] if i is even
        // array[(i-1)/2]       if i is odd
        if (i & 1) {
            next = (i >> 1);
        } else {
            next = halfLen + (i >> 1);
        }
    } while (next != start);
    array[i] = hold;
}

int main(int argc, char *argv[])
{
    int size;
    int *array;

    if (argc < 2)
        size = 10;
    else
        size = atoi(argv[1]);

    array = calloc(size, sizeof(*array));

    for (int i=0; i < size; ++i)
        array[i] = i;
    //printArray(array, size);
    weave(array, 0, size);
    //printArray(array, size);
}

Results

I tested the original code and my version on an array of 200000 elements. Then I tested my version versus the linear time version on an array of 200000000 elements.

On 200000 elements:

OP code: 7.58 sec
Mine   : 0.01 sec
Linear : 0.01 sec

On 200000000 elements:

Mine   : 1.84 sec
Linear : 3.74 sec

My theory for why my solution is faster than the linear time solution is that the linear time solution's main step is a cycle permute, where it moves each item into place, leaving a hole, then filling the hole from the next correct place according to the shuffle. This part accesses the array in a non-linear order, jumping around the array, and therefore causes cache misses once the array grows bigger than the cache.

My solution swaps blocks at a time, but does so in a linear fashion. Therefore, the memory accesses are very cache friendly and shouldn't cause nearly as many cache misses. So even though my version is theoretically slower, it is practically better.