مرتب سازی کلوچه ای ( به انگلیسی: Pancake sorting ) از انواع روش های مرتب سازی است که در آن معکوس کردن عضوهای بعضی از پیشوندهای یک دنباله تنها کار قابل اجرا می باشد. برخلاف روش های سنتی که تلاش می کردند مرتب سازی را با کمترین تعداد مقایسه انجام دهند، در این رویه هدف مرتب کردن دنباله با کمترین تعداد ممکن معکوس سازی است. این عمل را می توان همانند پشته ای از کلوچه ها در نظر گرفت؛ که می توانیم k کلوچهٔ اول را برداریم و به آن ضربه بزنیم. نوع دیگر مسئله با کلوچه های سوخته سروکار دارد؛ که یک طرف هر کلوچهٔ سوخته است. در نهایت با رو قرار گرفتن سرِ سوختهٔ کلوچه ها پایان می پذیرد.
حداکثر تعداد تلنگر ( واژگون سازی ) مورد نیاز برای مرتب سازی هر پشته شامل n کلوچه مقداری بین 15/14n و 18/11n نشان داده شده است، اما مقدار دقیق آن به دست نیامده است. [ ۱]
ساده ترین الگوریتم مرتب سازی کلوچه ای حداکثر نیاز به 2n−۳ تلنگر دارد. در این الگوریتم، یک نوع مرتب سازی انتخابی، بزرگترین کلوچهٔ مرتب نشده را روی پشته با یک تلنگر ( واژگون سازی ) قرار می دهیم؛ و سپس با یک تلنگر ( واژگون سازی ) دیگر آن را به مکان نهایی منتقل می کنیم؛ و این فرایند را برای کلوچه های باقی مانده نیز تکرار می کنیم. به این نکته باید توجه کرد که زمان صرف شده برای پیدا کردن کلوچه ها در نظر گرفته نمی شود. تنها عامل مهم تعداد تلنگرها ( واژگون سازی ) ست. به منظور پیاده سازی ماشینی که بتواند این رویه را در زمان خطی انجام دهد باید واژگون سازی پیشوندها و پیدا کردن بیشینه محدوده ازاعداد متوالی دار دنباله در زمان ثابت اجرا شود. در ۱۷ سمپتامبر سال ۲۰۰۸ گروهی از محققان در دانشگاه تگزاس در دالاس به رهبری بنیان گذار هال سودبرو[ ۲] پذیرفته شدن یک روش بهینه تر از آن چیزی که گیتس و پپدیمیتریو برای مراتب سازی کلوچه ای ارائه داده بودند را توسط مجلهٔ علوم کامپیوتر نظری اعلام کردند. [ ۳] [ ۴] در ۲ نوامبر سال ۲۰۱۱ یک مقاله به ارخیو ارائه شد که اثبات می کرد که مسٔله ان پی سخت است، در نتیجه در پاسخ به سؤال باز برای بیش از سه دهه. [ ۱]
در یک نوع پیچیده تر که مرتب سازی کلوچه سوخته نامید می شود که زمانی پایان می پذیرد که طرف سوختهٔ همهٔ کلوچه ها روی به پایین قرار گیرد. در سال ۲۰۰۸ گروهی از دانشجویان یک رایانه باکتریایی ( bacterial computer ) ساختند که می توانست مسئله سادهٔ مرتب سازی کلوچه سوخته را با استفاده از برنامه نویسی E. coliحل کند. [ ۵] [ ۶]
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفحداکثر تعداد تلنگر ( واژگون سازی ) مورد نیاز برای مرتب سازی هر پشته شامل n کلوچه مقداری بین 15/14n و 18/11n نشان داده شده است، اما مقدار دقیق آن به دست نیامده است. [ ۱]
ساده ترین الگوریتم مرتب سازی کلوچه ای حداکثر نیاز به 2n−۳ تلنگر دارد. در این الگوریتم، یک نوع مرتب سازی انتخابی، بزرگترین کلوچهٔ مرتب نشده را روی پشته با یک تلنگر ( واژگون سازی ) قرار می دهیم؛ و سپس با یک تلنگر ( واژگون سازی ) دیگر آن را به مکان نهایی منتقل می کنیم؛ و این فرایند را برای کلوچه های باقی مانده نیز تکرار می کنیم. به این نکته باید توجه کرد که زمان صرف شده برای پیدا کردن کلوچه ها در نظر گرفته نمی شود. تنها عامل مهم تعداد تلنگرها ( واژگون سازی ) ست. به منظور پیاده سازی ماشینی که بتواند این رویه را در زمان خطی انجام دهد باید واژگون سازی پیشوندها و پیدا کردن بیشینه محدوده ازاعداد متوالی دار دنباله در زمان ثابت اجرا شود. در ۱۷ سمپتامبر سال ۲۰۰۸ گروهی از محققان در دانشگاه تگزاس در دالاس به رهبری بنیان گذار هال سودبرو[ ۲] پذیرفته شدن یک روش بهینه تر از آن چیزی که گیتس و پپدیمیتریو برای مراتب سازی کلوچه ای ارائه داده بودند را توسط مجلهٔ علوم کامپیوتر نظری اعلام کردند. [ ۳] [ ۴] در ۲ نوامبر سال ۲۰۱۱ یک مقاله به ارخیو ارائه شد که اثبات می کرد که مسٔله ان پی سخت است، در نتیجه در پاسخ به سؤال باز برای بیش از سه دهه. [ ۱]
در یک نوع پیچیده تر که مرتب سازی کلوچه سوخته نامید می شود که زمانی پایان می پذیرد که طرف سوختهٔ همهٔ کلوچه ها روی به پایین قرار گیرد. در سال ۲۰۰۸ گروهی از دانشجویان یک رایانه باکتریایی ( bacterial computer ) ساختند که می توانست مسئله سادهٔ مرتب سازی کلوچه سوخته را با استفاده از برنامه نویسی E. coliحل کند. [ ۵] [ ۶]
wiki: مرتب سازی کلوچه ای