مرتب سازی دایره ای ( به انگلیسی: 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 # Find where to put the item. pos = cycleStart for i in range ( cycleStart + 1, len ( array ) ) : if array < 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 += 1 array, item = item, array 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 < item: pos += 1 # Put the item there or right after any duplicates. while item == array: pos += 1 array, item = item, array writes += 1 return writes منابع [ ۱] [ ۲]
↑ ↑ Oxford Journals | Mathematics & Physical Sciences | Computer Journal
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفبر خلاف تمام الگوریتم های نزدیک به آن، داده ها در جای دیگر آرایه به سادگی نوشته نمی شوندتا آن ها را از عملیات خارج کنیم. هر مقداردهی در زمان صفر صورت می گیرد اگر در آن زمان در مکان درست خودش موجود باشد، ویا در جای درس در یک زمان نوشته می شود. این مسابقه نیازمند دوباره کاری کمتری برای مرتب سازی درجا است. کم کردن تعداد نوشتن ها زمانی که تعداد زیادی از داده ها را قرار است که ذخیره کنیم بسیار سودمند است، مانند 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 # Find where to put the item. pos = cycleStart for i in range ( cycleStart + 1, len ( array ) ) : if array < 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 += 1 array, item = item, array 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 < item: pos += 1 # Put the item there or right after any duplicates. while item == array: pos += 1 array, item = item, array writes += 1 return writes منابع [ ۱] [ ۲]
↑ ↑ Oxford Journals | Mathematics & Physical Sciences | Computer Journal
wiki: مرتب سازی دایره ای