Last week we had a look at Kernighan’s algorithm to rotate an array position and concluded that it might not be optimal, as each element was moved twice. This week, we’ll have a look at another algorithm that moves some items more than once, but overall will do less than two exchanges per items.
To “rotate” an array position to the left (or to the right, doesn’t really matter) we could repeat times a shift of one, using only one temporary variable. This method doesn’t use much auxiliary memory but is inefficient: it will do copies if we apply it to an array of size . Surely we can do better.
Initializing large arrays of data before use is always cumbersome but it seems to be unavoidable.
The first types of solutions fill the array with a value that denotes an empty entry. While this sounds straightforward, the choice of that value is not always easy. For floating points numbers, zero may or may not be a good candidate. If convenient (as a zero floating point value is encoded as binary zeroes filling the variable) it may be difficult in some contexts to use because zero may be valid. Fortunately, there’s always the possibility to initialize the array with NaNs, which can be tested and used correctly (but you need the POSIX functions to do that).