موضوع مقاله: مرتب‌سازی کلوچه‌ای | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # مرتب‌سازی کلوچه‌ای | مقدمه: مرتب‌سازی کلوچه‌ای از انواع روش‌های مرتب‌سازی است که در آن معکوس کردن عضوهای بعضی از پیشوندهای یک دنباله تنها کار قابل اجرا می‌باشد. | ## بخش 1: مرتب‌سازی کلوچه‌ای | برخلاف روش‌های سنتی که تلاش می‌کردند مرتب‌سازی را با کمترین تعداد مقایسه انجام دهند، در این رویه هدف مرتب کردن دنباله با کمترین تعداد ممکن معکوس‌سازی است. این عمل را می‌توان همانند پشته‌ای از کلوچه‌ها در نظر گرفت؛ که می‌توانیم کلوچهٔ اول را برداریم و به آن ضربه بزنیم. مسئله‌های کلوچه‌ای مسئله اصلی حداکثر تعداد تلنگر (واژگون سازی) مورد نیاز برای مرتب‌سازی هر پشته شامل n کلوچه مقداری بین 15/14n و 18/11n نشان داده شده‌است، اما مقدار دقیق آن به دست نیامده‌است.Bulteau, L. در این الگوریتم، یک نوع مرتب‌سازی انتخابی، بزرگترین کلوچهٔ مرتب نشده را روی پشته با یک تلنگر (واژگون سازی) قرار می‌دهیم؛ و سپس با یک تلنگر (واژگون سازی) دیگر آن را به مکان نهایی منتقل می‌کنیم؛ و این فرایند را برای کلوچه‌های باقی‌مانده نیز تکرار می‌کنیم. به این نکته باید توجه کرد که زمان صرف شده برای پیدا کردن کلوچه‌ها در نظر گرفته نمی‌شود. به منظور پیاده‌سازی ماشینی که بتواند این رویه را در زمان خطی انجام دهد باید واژگون‌سازی پیشوندها و پیدا کردن بیشینه محدوده ازاعداد متوالی دار دنباله در زمان ثابت اجرا شود. | ## بخش 2: مرتب‌سازی کلوچه‌ای | در ۲ نوامبر سال ۲۰۱۱ یک مقاله به ارخیو ارائه شد که اثبات می‌کرد که مسٔله ان‌پی سخت است، در نتیجه در پاسخ به سؤال باز برای بیش از سه دهه. مسئله کلوچه سوخته در یک نوع پیچیده‌تر که مرتب‌سازی کلوچه سوخته نامید می‌شود که زمانی پایان می‌پذیرد که طرف سوختهٔ همهٔ کلوچه‌ها روی به پایین قرار گیرد. بالا بودن تعداد باکتریها در این روش شالودهٔ گسترده‌ای از محاسبات موازی را فراهم می‌کند. در حالی که "رشته‌هاً دنباله‌هایی هستند که نمدها می‌توانند بیش از یک بر در آن‌ها تکرار شوند. (۲۰۰۷) (.Hurkens et al)جداگانه نشان دادند که پیچیدگی تبدیل یک رشتهٔ سازگار را به رشته‌ای دیگر با استفاده از وژگون‌سازی پیشوندها ان‌پی کامل است. تاریخچه اگر چه اغلب به عنوان یک وسیله آموزشی دیده می‌شود، مرتب‌سازی کلوچه‌ای در برنامه‌های کاربردی در شبکه‌های پردازنده موازی نیز دیده می‌شود، که می‌تواند الگوریتم مؤثر مسیریابی بین پردازنده فراهم کند. | ## بخش 3: مرتب‌سازی کلوچه‌ای | این مسئله به عنوان تنها مقالهٔ ریاضیات مشهور که تاکنون توسط بنیانگذار مایکروسافت بیل گیتس (به عنوان ویلیام گیتس)، تحت عنوان «مرزهای برای دسته‌بندی بر اساس واژگونی پیشوند» در سال ۱۹۷۹ منتشر شده‌است، قابل توجه‌است؛ که یک الگوریتم کارآمدرا برای مرتب‌سازی کلوچه‌ای توصیف می‌کند.Gates, W. علاوه بر این، قابل توجه‌ترین مقاله منتشر شده توسط فوتوراما فوتوراما همکار دیوید کوهن دیوید اکس. همکاران آن‌ها کریستوس پاپادیمیتریو (سپس در دانشگاه هاروارد، در حال حاضر در برکلی) و مانوئل بلومManuel Blum (سپس در برکلی، در حال حاضر در دانشگاه کارنگی ملون دانشگاه کارنگی ملون)، بودند. مشکلات به هم پیوستهٔ مراتب‌سازی علامتدار با استفاده از وژگون‌سازی و مراتب‌سازی با استفاده از وژگون‌سازی اخیراً بیشتر مورد مطالعه قرار گرفته‌اند. در حالی که الگوریتم بهینه برای مراتب‌سازی با استفاده از وژگون‌سازی پیدا شده‌است. توالی‌های عدد صحیح مرتبط + تعداد پشته‌ها با ارتفاع داده شده که به n تلنگر برای مرتب شدن نیاز دارند. | ## جمع‌بندی | ارتفاع N ۰ ۱ ۲ ۳ ۴ ۵ ۶ ۷ ۸ ۹ ۱۰ ۱۱ ۱۲ ۱۳ ۱۴ ۱ ۱ ۲ ۱ ۱ ۳ ۱ ۲ ۲ ۱ ۴ ۱ ۳ ۶ ۱۱ ۳ ۵ ۱ ۴ ۱۲ ۳۵ ۴۸ ۲۰ ۶ ۱ ۵ ۲۰ ۷۹ ۱۹۹ ۲۸۱ ۱۳۳ ۲ ۷ ۱ ۶ ۳۰ ۱۴۹ ۵۴۳ ۱۳۵۷ ۱۹۰۳ ۱۰۱۶ ۳۵ ۸ ۱ ۷ ۴۲ ۲۵۱ ۱۱۹۱ ۴۲۸۱ ۱۰۵۶۱ ۱۵۰۱۱ ۸۵۲۰ ۴۵۵ ۹ ۱ ۸ ۵۶ ۳۹۱ ۲۲۷۸ ۱۰۶۶۶ ۳۸۰۱۵ ۹۳۵۸۵ ۱۳۲۶۹۷ ۷۹۳۷۹ ۵۸۰۴ ۱۰ ۱ ۹ ۷۲ ۵۷۵ ۳۹۶۳ ۲۲۸۲۵ ۱۰۶۴۶۱ ۳۷۷۸۶۳ ۹۱۹۳۶۵ ۱۳۰۹۷۵۶ ۸۱۴۶۷۸ ۷۳۲۳۲ ۱۱ ۱ ۱۰ ۹۰ ۸۰۹ ۶۴۲۹ ۴۳۸۹۱ ۲۵۲۷۳۷ ۱۱۷۴۷۶۶ ۴۱۲۶۵۱۵ ۹۹۸۱۰۷۳ ۱۴۲۵۰۴۷۱ ۹۱۲۳۶۴۸ ۹۵۶۳۵۴ ۶ ۱۲ ۱ ۱۱ ۱۱۰ ۱۰۹۹ ۹۸۸۳ ۷۷۹۳۷ ۵۳۳۳۹۷ ۳۰۶۴۷۸۸ ۱۴۱۴۱۹۲۹ ۴۹۳۳۷۲۵۲ ۱۱۸۴۲۰۰۴۳ ۱۶۹۳۳۲۲۱۳ ۱۱۱۰۵۰۰۶۶ ۱۳۰۳۲۷۰۴ ۱۶۷ دنباله‌ها از: The Online Encyclopedia of Integer Sequences of Neil Sloane – بیشینه تعداد تلنگرها – تعداد پشته‌های که بیشینه تعداد تلنگرها را نیاز دارد – تعداد بیشینهٔ تلنگرها برای یک پشتهٔ سوخته – بیشترین تعداد تلنگر برای پشتهٔ مراتب شده که طرف سوختهٔ کلوچه‌ها روی به بالاست.