تعریف مسئله و هدف الگوریتم

• ورودی:
  • یک آرایه ( A ) با طول ( n ).
  • یک عدد صحیح غیرمنفی ( k ) (تعداد گام چرخش به راست).
• خروجی:
  • آرایه‌ای که در آن هر عنصر، ( k ) خانه به سمت راست جابه‌جا شده و اگر از انتها خارج شود، از ابتدای آرایه وارد می‌شود.
• قیود:
  • زمان ( O(n) ).
  • فضای اضافی ( O(1) )، یعنی بدون آرایهٔ کمکی متناسب با n.

مثال:
( A = [1,2,3,4,5,6,7], k = 3 ) → خروجی: ( [5,6,7,1,2,3,4] ).

ایده شهودی Reversal Algorithm

ایدهٔ اصلی این است که به جای «جابجایی مستقیم هر عنصر به مکان جدیدش»، آرایه را به‌صورت چند بلاک در نظر بگیری و با سه بار وارون کردن (reverse) این بلاک‌ها، همان نتیجهٔ چرخش را بسازی.

برای چرخش به راست به اندازهٔ ( k ) در آرایه با طول ( n ):

1. نرمال‌سازی: ( k = k \bmod n ).
   • چرخش به اندازهٔ ( k ) و ( k + m n ) یکسان است، چون هر ( n ) بار چرخش، آرایه را به حالت اولیه برمی‌گرداند.
2. تفکیک مفهومی به دو بلاک:
   • بلاک ( B = ) آخرین ( k ) عنصر: ( A[n-k \dots n-1] ).
   • بلاک ( C = ) اولین ( n-k ) عنصر: ( A[0 \dots n-k-1] ). در چرخش به راست، در خروجی باید به ترتیب ( B ) سپس ( C ) قرار بگیرند و ترتیب داخلی هر بلاک حفظ شود.
3. ترفند: چطور بدون جابه‌جایی بلاکی مستقیم و فقط با reverse به این هدف برسیم؟
   • اگر کل آرایه را وارونه کنیم، ترتیب بلاک‌ها معکوس می‌شود (اول C برعکس، بعد B برعکس).
   • اگر بعد از آن هربلاک را جداگانه دوباره وارونه کنیم، ترتیب داخلی‌شان درست می‌شود و در عین حال جای بلاک‌ها عوض نمی‌شود.

بنابراین تو تنها به یک primitive نیاز داری:
تابع reverse که یک زیرآرایه را درجا وارونه می‌کند.

توالی گام‌های الگوریتم (چرخش به راست)

برای چرخش به راست به اندازهٔ ( k ):

1. ( k = k \bmod n ).
   • اگر ( k = 0 ) یا ( n \le 1 )، هیچ کاری لازم نیست.
2. وارون‌سازی کل آرایه:
   • reverse(A, 0, n-1)
   • حالا آخرین ( k ) عنصر به ابتدای آرایه آمده‌اند، ولی هم آن‌ها و هم بقیه، هر دو وارونه شده‌اند.
3. وارون‌سازی اولین ( k ) عنصر:
   • reverse(A, 0, k-1)
   • این کار ترتیب داخلی بلاک جلویی (که همان بلاک B است) را تصحیح می‌کند.
4. وارون‌سازی بقیهٔ عناصر از اندیس ( k ) تا ( n-1 ):
   • reverse(A, k, n-1)
   • این کار ترتیب داخلی بلاک عقبی (که همان بلاک C است) را تصحیح می‌کند و آرایه نهایی دقیقا معادل چرخش به راست است.

همین توالی سه‌تایی reverse همان چیزی است که در بسیاری از پیاده‌سازی‌های رسمی LeetCode 189 پیشنهاد می‌شود.

اثبات درستی به زبان الگوریتمیک (شُبه‌ریاضی)

برای سادگی، اندیس‌ها را صفرمبنا بگیر و طول آرایه را ( n ) و چرخش به راست به اندازهٔ ( k ) (پس از نرمال‌سازی) در نظر بگیر.

1. وضعیت مطلوب بعد از چرخش:
   • هر عنصر ( A[i] ) باید به اندیس جدید
     [ j = (i + k) \bmod n ]
     منتقل شود.
   • معادل بلاکی:
     • عناصر با اندیس ( n-k \dots n-1 ) به اندیس‌های ( 0 \dots k-1 ) می‌آیند (بلاک B).
     • عناصر با اندیس ( 0 \dots n-k-1 ) به اندیس‌های ( k \dots n-1 ) می‌آیند (بلاک C).
2. بعد از گام ۲ (reverse کل آرایه):
   • عنصر در اندیس ( i ) به اندیس ( n-1-i ) می‌رود.
   • بلاک‌های اولیه:
     • B: ( [n-k, \dots, n-1] )
     • C: ( [0, \dots, n-k-1] )
   • پس از reverse:
     • B به بازهٔ ( [0, \dots, k-1] ) منتقل می‌شود ولی به‌صورت وارونه.
     • C به بازهٔ ( [k, \dots, n-1] ) منتقل می‌شود ولی به‌صورت وارونه.[10]
3. بعد از گام ۳ (reverse بازهٔ ( [0, k-1] )):
   • در این بازه، که دقیقا حاوی عناصر B است، دوباره وارون‌سازی انجام می‌دهی، بنابراین ترتیب B درست می‌شود.
4. بعد از گام ۴ (reverse بازهٔ ( [k, n-1] )):
   • این بازه دقیقا حاوی عناصر C است (که در گام ۲ وارونه شده‌اند).
   • با وارون‌سازی دوباره، ترتیب C نیز به حالت اصلی برمی‌گردد.

در این مرحله، تو دقیقا ( B ) سپس ( C ) را با ترتیب داخلی اصلی‌شان داری؛ که همان خروجی مدنظر چرخش به راست است.[10]

پیاده‌سازی مفهومی تابع reverse

تابع reverse یک زیرآرایه را با دو اشاره‌گر ابتدا–انتها درجا وارونه می‌کند:

• ورودی: آرایهٔ ( A )، اندیس شروع ( l )، اندیس پایان ( r ) (شامل هر دو).
• تا وقتی ( l < r ):
  • ( A[l] ) و ( A[r] ) را swap کن.
  • ( l++ ), ( r– ).

این تابع:

• زمان ( \Theta(r - l + 1) ) دارد چون هر بار دو عنصر را عوض می‌کند و حداکثر حدود نصف طول بازه تکرار می‌شود.
• فضای اضافی ( \Theta(1) ) دارد چون فقط چند متغیر موقت (مثلا یک متغیر برای swap) لازم است.[11]

تحلیل زمانی و فضایی الگوریتم چرخش با reverse

اگر طول آرایه را ( n ) در نظر بگیریم:[12]

• این الگوریتم سه بار reverse صدا می‌زند:
  • reverse(0, n-1) → هزینه حدود ( n ).
  • reverse(0, k-1) → هزینه حدود ( k ).
  • reverse(k, n-1) → هزینه حدود ( n-k ).

• مجموع زمان:
  [ T(n) = n + k + (n-k) = 2n = O(n) ]
  بنابراین زمان، خطی نسبت به اندازهٔ آرایه است.

• فضا:
  • به جز متغیرهای ساده مانند اندیس‌ها و یک temp برای swap، هیچ ساختار داده‌ای وابسته به n استفاده نمی‌شود.
  • پس فضای اضافی ( O(1) ) است.[11]

این باعث می‌شود Reversal Algorithm از نظر تئوری و عملی، یکی از بهینه‌ترین روش‌ها برای مسئلهٔ چرخش آرایه باشد و در منابع مختلف به‌عنوان «best choice» برای چرخش in‑place معرفی شده است.[12]