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.
array.push(*array.shift(steps))
. \$\endgroup\$