6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ The last expression could also written as array.push(*array.shift(steps)). \$\endgroup\$ – sschmeck Apr 13 '16 at 3:40
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks. I will implement your method and check back. Ruby arrays also start at 0 index. ... is exclusive range notation, so it saves me from having to do 0..array.size - 1 (notice 2 dots instead of 3). \$\endgroup\$ – Mohamad Apr 9 '16 at 14:12
  • \$\begingroup\$ Does my notation of \$T(A,S)=S(A)+S(2C)\$ make sense? Or is it nonsense? \$\endgroup\$ – Mohamad Apr 9 '16 at 14:13
  • \$\begingroup\$ @Mohamad: I guess it makes at least reasonable sense. \$\endgroup\$ – Jerry Coffin Apr 9 '16 at 14:14
  • \$\begingroup\$ Ruby array are indexed from 0, as in C, but Ruby arrays also support negative indexes, which count backwards from the end. \$\endgroup\$ – 200_success Apr 9 '16 at 19:24
  • \$\begingroup\$ Ok, I went back to basics are looked at how we reverse and rotate arrays, and I was able to understand and implement your version. It's in this Gist. I was also able to see that my own implementation was needlessly complex. I could have used array[i] = array[i + 1] (instead of array[j - 1] = array[j]) had I started my iteration at 0 instead of 1, which is easier to digest. \$\endgroup\$ – Mohamad Apr 9 '16 at 20:12
0
\$\begingroup\$

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"]
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.