Rotating an array
Arrays keep items in a row, so moving one item means shifting others. To rotate right by k, reverse the whole array, then reverse the first k items and the rest separately. Every item lands k places along, using only swaps.
12345678
Move every item 3 places to the right, wrapping the end round to the front. Press play to start.
1function rotate(a, k) {2 if (a.length === 0) return;3 k = k % a.length;4 reverse(a, 0, a.length - 1);5 reverse(a, 0, k - 1);6 reverse(a, k, a.length - 1);7}89function reverse(a, lo, hi) {10 while (lo < hi) {11 swap(a, lo, hi);12 lo++; hi--;13 }14}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | n | every k: the first reversal touches every item |
| average | n | about n swaps in total |
| worst | n | shifting one place at a time instead costs n · k |
| space | 1 | in place, no second array |
Where it breaks
- Shifting one place k times. Each single shift moves all n items, so the obvious loop costs n · k. Three reversals cost about n whatever k is.
- k bigger than the array. Rotating 8 items by 8 puts everything back where it started. Pick Right by 11: the code reduces it to 11 % 8 = 3 first. Skip that and the reversals read past the end.
- An empty array.
k % 0is NaN in JavaScript and an error in Python. That is why the function checks for an empty array before anything else.