مرتب‌سازی چرخه‌ای

مرتب‌سازی چرخه ای جز دسته الگوریتمهای غیر مقیاس پذیر است. مرتب‌سازی چرخه‌ای بر خلاف مرتب‌سازی‌های محلی دیگر، یک مرتب‌سازی نسبی بوده و از لحاظ نظری مطلوب و بهینه‌است. در این مرتب‌سازی از ساختمان داده‌ها آرایه (رایانه) ای استفاده شده‌است. بر اساس این ایده که جایگشت می‌تواند عناصر را در داخل چرخه به صورت جداگانه مرتب کنند، کلیه عناصر در چرخه چرخانده شده و در نتیجه کلیه عناصر مرتب خواهند شد. برخلاف تمامی روش‌های مرتب‌سازی، در این روش عناصر در جایی دیگر از آرایه به سادگی نوشته نشده‌اند که بتوان آن‌ها را از طریق یک عملیات آن‌ها را به داخل آرایه وارد کرد. هر عنصر دو بار از ابتدا نوشته می‌شود چه در موقعیت صحیح خود باشد و چه در موقعیت صحیح خود یک بار نوشته شده باشد. این تطابق حداقل تعداد رونویسی لازم برای تکمیل مرتب‌سازی در محل است. به حداقل رساندن تعداد نوشتن‌ها در برخی مجموعه‌ها با داده‌های بزرگ که نوشتن آن‌ها گران تمام می‌شود، مفید است. مانند برخی رسانه‌های ذخیره‌سازی که با هر بار نوشتن طول عمر آن‌ها کاهش می‌یابد.

مرتب‌سازی چرخه‌ای

تجسم مرتب‌سازی چرخه‌ای یک فهرست از ارقام تصادفی.
رده	الگوریتم‌های مرتب‌سازی
ساختمان داده	آرایه
کارایی بدترین حالت	${\displaystyle \Theta (n^{2})}$
کارایی بهترین حالت	${\displaystyle \Theta (n^{2})}$
کارایی متوسط	${\displaystyle \Theta (n^{2})}$
پیچیدگی فضایی	${\displaystyle \Theta (n)}$ کل، ${\displaystyle \Theta (1)}$ کمکی

الگوریتم

الگوریتم زیر چرخه‌ها و مسیر چرخش عناصر را پیدا کرده و نتیجه را به صورت مرتب شده ارائه می‌دهد. توجه داشته باشید که بازه(a,b) از a به b-1 می‌رود.

                . مرتب‌سازی محلی یک آرایه و بازگشت به تعداد راس ها*
def cycleSort(array):
  writes = ۰

             . حلقه‌ای روی آرایه برای پیدا کردن چرخه به منظور چرخش*
  for cycleStart in range(0, len(array) - 1):
    item = array[cycleStart]

                                    . پیدا کردن محل قرار گیری عنصر*
    pos = cycleStart
  for i in range(cycleStart + 1, len(array)):
    if array[i] <item:
      pos += ۱

       . اگر عنصر مورد نظر در حال حاضر وجود دارد، این یک چرخه نیست*
    if pos == cycleStart:
      continue

. در غیر این صورت عنصر قبل از هر تکرار به درستی در محل قرار می‌گیرد*
  while item == array[pos]:
    pos += ۱
    array[pos], item = item, array[pos]
    writes += ۱

                                                 . ادامه چرخش چرخه*
  while pos!= cycleStart:

                                    . پیدا کردن محل قرار گیری عنصر*
    pos = cycleStart
  for i in range(cycleStart + 1, len(array)):
    if array[i] <item:
      pos += ۱

                  . عنصر قبل از هر تکرار به درستی در محل قرار گیرد*
  while item == array[pos]:
    pos += ۱
    array[pos], item = item, array[pos]
    writes += ۱

return writes

حالت‌های خاص بهینه‌سازی

هنگامی که محتویات آرایه موارد تکراری از تعداد نسبتاً کمی از عناصر است، در یک بازه پیچیدگی زمانی مناسب تابع جدول درهم‌سازی جایی که برای قرار دادن یک عنصر مباسب است را به سرعت پیدا کند. در این صورت زمان مرتب‌سازی از(θ(n^۲ به(θ(n+k تغییر خواهد کرد که در اینجا K تعداد کل هش‌ها می‌باشد. مرتب شده آرایه با دستور بابع هش به پایان می‌رسد؛ بنابراین انتخاب یک تابع هش که دستورات مناسبی را ارائه دهد بسیار مهم است. قبل از عمل مرتب‌سازی یک بافت نگار (هیستوگرام) را که توسط توابع هش مرتب شده ایجاد کنید و تعداد مرتبه‌های تکرار رشته را در آرایه بشمارید. سپس یک جدول با جمع تجمعی هر ورودی در بافت نگار ایجاد کنید. توزیع احتمال حاوی موقعیت هر عنصر در آرایه خواهد شد. در این صورت محل مناسب عناصر تحت هش در زمان ثابت پیدا می‌شود و رجوع به جدول مجموع تجمعی در زمان خطی صورت می‌گیرد.

منابع

• Cycle-Sort: A Linear Sorting Method, The Computer Journal (1990) 33 (4): 365-367
• Cycle sort
• Algorithm-Optimizing a cycle sort implementation
• process of cycling sort (cycle sort) algorithm.. ?HELP

پیوند به بیرون

• Original source of unrestricted variant