Algorithm to rotate array elements in Ruby

Question

I wrote this algorithm to rotate elements in an array. It's not very efficient, but it works. It has another disadvantage that it doesn't rotate right (it would be nice to pass it negative steps, for example).

def rotate_left!(array, steps = 1)
  for i in 0...steps
    first = array[0]
    for j in 1...array.size
      array[j - 1] = array[j]
    end
    array[-1] = first
  end
end

An aside, does this count as \$O(n^2)\$? For each step, we have to iterate over the entire array and shift positions by -1.

Let \$A\$ be the size of the array, \$S\$ be the steps, and \$C\$ be the constant operations of storing the first element then adding it to the end of the array.

$$ T(A, S) = S(A) + S(2C) $$

This notation is ad-hoc, so excuse me if it doesn't make sense.

I am aware of array#rotate, and of array#shift and array#pop. For example:

def my_rotate!(array, steps = 1)
  for i in 1..steps
    array.push(array.shift)
  end
end
# or 
array.push(array.shift(steps)).flatten!

But I'm curious if there are other ways that rely less on Array instance methods.

Answer 1

Your algorithm is \$O(N*M)\$ where:
\$N\$ = size of array
\$M\$ = steps

It's possible to do an array rotation that's \$O(N)\$, regardless of the number of steps you specify though.

Start by thinking of the array as two pieces, separated at "steps" indices into the array. For example, if you're going to rotate by 4, then mentally separate it into array[1..5] and array[5..N].

To do the rotation, start by reversing each of those pieces. Then reverse the entire array, something on this order:

for j in 1...steps/2
    temp = array[j]
    array[j] = array[steps-j+1]
    array[steps-j+1] = temp
end

for k in 1...(array.size-steps)/2
    temp = array[steps+k]
    array[steps+k] = array[array.size-k+1]
    array[array.size-k+1]=temp
end

for i in 1...array.size
    temp = array[i]
    array[i] = array[array.size-i+1]
    array[array.size-i+1] = temp
end

Note: I'm more accustomed to C-style arrays, where indexes start at 0 instead of 1. I've tried to compensate appropriately, but I haven't tested this, so I wouldn't be surprised if there were still a few off-by-one errors.

This steps through the entire array twice, regardless of the size of rotation, so it's likely to be slower than yours for steps=1, about the same speed for steps = 2, and faster for steps > 2.

Answer 2

I was not able to get @Jerry Coffin's particular implementation to work, but I used his idea to create this similar \$O(n)\$ implementation.

As he describes, we reverse the array at \$A[0..S-1]\$ and \$A[S..N-1]\$, where \$S\$ is steps and \$N\$ is the length of the array. We then reverse the entire array.

def array_rotate!(array, steps)
  for i in 0...steps / 2
    temp = array[i]
    array[i] = array[steps - i - 1]
    array[steps - i - 1] = temp
  end

  for j in steps...(array.size + steps) / 2
    temp = array[j]
    array[j] = array[array.size - 1 - (j - steps)]
    array[array.size - 1 - (j - steps)] = temp
  end

  for k in 0...array.size / 2
    temp = array[k]
    array[k] = array[array.size - 1 - k]
    array[array.size - 1 - k] = temp
  end
end

a = [*"a".."e"]
array_rotate!(a, 3)
puts a.inspect
#=> ["d", "e", "a", "b", "c"]

To illustrate this technique: Given %w[a b c d e] and \$S = 3\$ and \$5\$:

1. We reverse \$A[0..S-1]\$: %w[c b a d e]
2. We reverse \$A[S..N-1]\$: %w[c b a e d]
3. We reverse the entire array \$A[0..N-1]\$: %w[d e a b c]

This still can't rotate in both directions.

a = [*"a".."e"]
array_rotate!(a, -2)
puts a.inspect
#=> ["e", "d", "a", "b", "c"]