مرتب‌سازی دایره‌ای

مرتب‌سازی دایره‌ای

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

مرتب‌سازی دایره‌ای (به انگلیسی: Cycle sort) یا مرتب‌سازی درجا یا الگریتم مرتب‌سازی ناپایدار، یک مرتب‌سازی مقایسه‌ای که تئوری خوبی از نظر تعداد عناصر نوشته‌شده در آرایهٔ اصلی است، بر خلاف تمام الگوریتم‌های مرتب‌سازی. این بر اساس ایده‌ای است که جایگشت می‌تواندفاکتوری برای مرتب‌سازی باشد، که به صورت جداگانه چرخش برای بدست آمدن نتیجه ایجاد شود.

بر خلاف تمام الگوریتم‌های نزدیک به آن، داده‌ها در جای دیگر آرایه به سادگی نوشته نمی‌شوندتا آن‌ها را از عملیات خارج کنیم. هر مقداردهی در زمان صفر صورت می‌گیرد اگر در آن زمان در مکان درست خودش موجود باشد، ویا در جای درس در یک زمان نوشته می‌شود. این مسابقه نیازمند دوباره کاری کمتری برای مرتب‌سازی درجا است. کم کردن تعداد نوشتن‌ها زمانی که تعداد زیادی از داده‌ها را قرار است که ذخیره کنیم بسیار سودمند است، مانند EEPROMها یا Flash memory که نوشتن عمر مفید دستگاه را کاهش می‌دهد. الگوریتم: الگوریتم زیر پیدا می‌کند با چرخش و دوراندن آن و نتیجهٔ مرتب شده را به ما می‌دهد. توجه داشته‌باشید که range(a, b) از مقدار a تا b – 1 است.

الگوریتم

الگوریتمالگوریتم زیر دوایر را پیدا کرده و آن‌ها را می‌چرخاند و جواب مرتب‌سازی را به ما می‌دهد. نقطه‌ای در فاصله(a, b) هستند از a تاb ‑ ۱.

# Sort an array in place and return the number of writes.
def cycleSort(array):
  writes = 0

  # Loop through the array to find cycles to rotate.
  for cycleStart in range(0, len(array) - 1):
    item = array[cycleStart]

    # Find where to put the item.
    pos = cycleStart
    for i in range(cycleStart + 1, len(array)):
      if array[i] <item:
        pos += 1

    # If the item is already there, this is not a cycle.
    if pos == cycleStart:
      continue

    # Otherwise, put the item there or right after any duplicates.
    while item == array[pos]:
      pos += 1
    array[pos], item = item, array[pos]
    writes += 1

    # Rotate the rest of the cycle.
    while pos!= cycleStart:

      # Find where to put the item.
      pos = cycleStart
      for i in range(cycleStart + 1, len(array)):
        if array[i] <item:
          pos += 1

      # Put the item there or right after any duplicates.
      while item == array[pos]:
        pos += 1
      array[pos], item = item, array[pos]
      writes += 1

  return writes