Rotate, Reverse, Block Swap, Repeat.

mgcadmin 26-11-2023

I was reading through a paper about block merge sort and in the article was a list of helper functions that the algorithm utilizes during its execution. This list was kind of a "who's who" of array manipulation algorithms. These algorithms are useful for a whole lot more than just block merge sort, and so I though It would be fun to implement different array manipulation algorithms and see what can be done with them, besides their obvious intended use.

Amongst the algorithms listed as helper functions were some you would expect to find in an optimized sorting algorithm, such as swap(), insertion_sort(), and even binary_search(). What really piqued my interest though were some of less common algorithms: rotate(), reverse(), floorPowerOf2(). And these got me thinking about what some other useful array manipulation algorithms, such as block_swap(), partition(), and rotate_left().

So without further, ado lets play with some arrays.

The Humble Swap

The act of exchanging the values of two variables is fundamental to a great many algorithms, and as such it has gotten its share of attention. Interestingly, the most straight forward "naïve" approach to swapping to values, also happens to be the best way to accomplish this task, an attribute shared by very few algorithms.

//the humble swap algorithm
template <class T>
void exch(T a[], int l, int r) {
     T tmp = a[l]; a[l] = a[r]; a[r] = tmp;
}

Many people write the algorithm using references instead of passing the array as an argument, extending the algorithm for use on any two values, not just two in the same array:

template <class T>
void exch(T& l, T& r) {
     T tmp = l; l = r; r = tmp;
} 

//or using pointers
template <class T>
void exch(T* a, T* b) {
     T tmp = *a; *a = *b; *b = tmp;
}

And of course, there is std::swap. Of interest, but not of practical use, is swapping without the use of extra storage, which can be done using bitwise operations such as xor swapping, or even good old fashioned addition and subtraction:

//using xor to swap two values
x = x ^ y;
y = y ^ x;
x = x ^ y;
//using addition and subtraction:
a = a + b;
b = b - a;
a = a - b;

The last two methods will only work when the values aren't equal. It is of some debate whether it is worthwhile to check for equality before swapping using the traditional methods as well, as it may be more costly to check for equality than to swap unneccisarily.

Block Swap and Reverse

Building directly from swap comes our next two algorithms, block swap, which is used to swap ranges of equal size, and reverse which reverse the order of values in an array.

template <class T>
void block_swap(T a[], int l1, int r1, int l1, int r2) {
     for (int i = l1, j = l2; i < r1 && j < r2; i++, j++)
         exch(a, i, j);
}

Block swap was the impetus that launched on a rabbit hole of O(log N) array reverse algorithms, but I will get into that in more detail below. For now when it comes to reversing arrays, the following O(N) solution will suffice:

template <class T>
void reverse(T a[], int l, int r) {
     while (r > l)
         exch(a, l++, --r);
}

Now, I said it will have to suffice, because our next algorithm makes clever use of reverse() to accomplish it's task.

Rotate & Rotate Middle Left

A rotation in an array, preserves the overall ordering of the elements but shifts their position N steps to the right or left. It sounds straight forward, but without reading any further, I implore you to try implementing an array rotation algorithm that utilizes O(1) extra space. It's not as easy a task it sounds, which is part of what makes the following algorithm interesting:

template <class T>
void rotate(T a[], int l, int r, int k) {
    reverse(a, l, r);
    reverse(a, l, l+k);
    reverse(a, l+k, r);
} 

Rotation through reversal works by making three calls to reverse(), the first call reverses the entire array, the next two following calls use the reversal amount - k - similar to the pivot in quicksort, to "un-reverse" the values, while placing them in their shifted position. It then follows that if we can come up with a O(log N) reverse() algorithm, then we can implement an O(log N) rotate algorithm as well.

The above algorithm rotates the elements of an array K positions to the right. std::rotate from the C++ standard library functions much differently, and in my opinion, is poorly named. While std::rotate does perform a rotation, it performs a very specific rotation: It rotates a range (first, last) to the left, so that the value that was in (first+last)/2 is now in the first position and all other values have been re-positioned accordingly.

//produces same ordering as std::rotate
template <class T>
void stl_rotate(T a[], int l, int r) {
    int m = (l+r)/2;
    int n = m;
    while (l != n) {
        exch(a, l++, n++);
        if (n == r) n = m;
        else if (l == m) m = n;
    }
} 

---