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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
مرتب‌سازی چرخه‌ای
تجسم مرتب‌سازی چرخه‌ای
تجسم مرتب‌سازی چرخه‌ای یک فهرست از ارقام تصادفی.
کلاس الگوریتم‌های مرتب‌سازی
ساختمان داده‌ها آرایه
عملکرد بدترین حالت
عملکرد بهترین حالت
عملکرد حالت متوسط
پیچیدگی فضایی بدترین حالت کل، کمکی

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

الگوریتم[ویرایش]

الگوریتم زیر چرخه‌ها و مسیر چرخش عناصر را پیدا کرده و نتیجه را به صورت مرتب شده ارائه می‌دهد. توجه داشته باشید که بازه(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 تعداد کل هش‌ها می‌باشد. مرتب شده آرایه با دستور بابع هش به پایان می‌رسد؛ بنابراین انتخاب یک تابع هش که دستورات مناسبی را ارائه دهد بسیار مهم است. قبل از عمل مرتب‌سازی یک بافت نگار (هیستوگرام) را که توسط توابع هش مرتب شده ایجاد کنید و تعداد مرتبه‌های تکرار رشته را در آرایه بشمارید. سپس یک جدول با جمع تجمعی هر ورودی در بافت نگار ایجاد کنید. توزیع احتمال حاوی موقعیت هر عنصر در آرایه خواهد شد. در این صورت محل مناسب عناصر تحت هش در زمان ثابت پیدا می‌شود و رجوع به جدول مجموع تجمعی در زمان خطی صورت می‌گیرد.

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

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