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

دانشنامه عمومی

مرتب سازی چرخه ای جز دسته الگوریتمهای غیر مقیاس پذیر است. مرتب سازی چرخه ای بر خلاف مرتب سازی های محلی دیگر، یک مرتب سازی نسبی بوده و از لحاظ نظری مطلوب و بهینه است. در این مرتب سازی از ساختمان داده ها آرایه ( رایانه ) ای استفاده شده است. بر اساس این ایده که جایگشت می تواند عناصر را در داخل چرخه به صورت جداگانه مرتب کنند، کلیه عناصر در چرخه چرخانده شده و در نتیجه کلیه عناصر مرتب خواهند شد. برخلاف تمامی روش های مرتب سازی، در این روش عناصر در جایی دیگر از آرایه به سادگی نوشته نشده اند که بتوان آن ها را از طریق یک عملیات آن ها را به داخل آرایه وارد کرد. هر عنصر دو بار از ابتدا نوشته می شود چه در موقعیت صحیح خود باشد و چه در موقعیت صحیح خود یک بار نوشته شده باشد. این تطابق حداقل تعداد رونویسی لازم برای تکمیل مرتب سازی در محل است. به حداقل رساندن تعداد نوشتن ها در برخی مجموعه ها با داده های بزرگ که نوشتن آن ها گران تمام می شود، مفید است. مانند برخی رسانه های ذخیره سازی که با هر بار نوشتن طول عمر آن ها کاهش می یابد.
الگوریتم زیر چرخه ها و مسیر چرخش عناصر را پیدا کرده و نتیجه را به صورت مرتب شده ارائه می دهد. توجه داشته باشید که بازه ( a, b ) از a به b - 1 می رود.
. مرتب سازی محلی یک آرایه و بازگشت به تعداد راس ها* def cycleSort ( array ) : writes = ۰ . حلقه ای روی آرایه برای پیدا کردن چرخه به منظور چرخش* for cycleStart in range ( 0, len ( array ) - 1 ) : item = array . پیدا کردن محل قرار گیری عنصر* pos = cycleStart for i in range ( cycleStart + 1, len ( array ) ) : if array < item: pos += ۱ . اگر عنصر مورد نظر در حال حاضر وجود دارد، این یک چرخه نیست* if pos == cycleStart: continue . در غیر این صورت عنصر قبل از هر تکرار به درستی در محل قرار می گیرد* while item == array: pos += ۱ array, item = item, array writes += ۱ . ادامه چرخش چرخه* while pos!= cycleStart: . پیدا کردن محل قرار گیری عنصر* pos = cycleStart for i in range ( cycleStart + 1, len ( array ) ) : if array < item: pos += ۱ . عنصر قبل از هر تکرار به درستی در محل قرار گیرد* while item == array: pos += ۱ array, item = item, array writes += ۱ return writes حالت های خاص بهینه سازی هنگامی که محتویات آرایه موارد تکراری از تعداد نسبتاً کمی از عناصر است، در یک بازه پیچیدگی زمانی مناسب تابع جدول درهم سازی جایی که برای قرار دادن یک عنصر مباسب است را به سرعت پیدا کند. در این صورت زمان مرتب سازی از ( θ ( n۲ به ( θ ( n+k تغییر خواهد کرد که در اینجا K تعداد کل هش ها می باشد. مرتب شده آرایه با دستور بابع هش به پایان می رسد؛ بنابراین انتخاب یک تابع هش که دستورات مناسبی را ارائه دهد بسیار مهم است. قبل از عمل مرتب سازی یک بافت نگار ( هیستوگرام ) را که توسط توابع هش مرتب شده ایجاد کنید و تعداد مرتبه های تکرار رشته را در آرایه بشمارید. سپس یک جدول با جمع تجمعی هر ورودی در بافت نگار ایجاد کنید. توزیع احتمال حاوی موقعیت هر عنصر در آرایه خواهد شد. در این صورت محل مناسب عناصر تحت هش در زمان ثابت پیدا می شود و رجوع به جدول مجموع تجمعی در زمان خطی صورت می گیرد.
عکس مرتب سازی چرخه ای
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلف

پیشنهاد کاربران

بپرس