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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
مرتب‌سازی دایره‌ای
نمونهٔ مرتب‌سازی دایره‌ای که یک فهرست از ارقام تصادفی را مرتب می‌کند.

نمونهٔ مرتب‌سازی دایره‌ای که یک فهرست از ارقام تصادفی را مرتب می‌کند.
کلاس الگوریتم مرتب‌سازی
داده ساختار آرایه
بدترین زمان اجرا \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 ‑ 1.

# 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

منابع[ویرایش]

http://stackoverflow.com</ref>[۱]

پیوند به بیرون[ویرایش]