مرتب‌سازی کلوچه‌ای در سی پلاس پلاس (Pancake Sort)

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

  1. حلقه while در سی پلاس پلاس
  2. حلقه for در سی پلاس پلاس
  3. توابع در سی پلاس پلاس
  4. آرایه در سی پلاس پلاس
  5. معکوس آرایه در سی پلاس پلاس

مرتب‌سازی کلوچه‌ای در سی پلاس پلاس

در مرتب سازی کلوچه ای شما تنها اجازه دارید که یک عملیات بر روی آرایه انجام دهید این عملیات معکوس کردن یا flip آرایه است. بر خلاف روش‌های سنتی که تلاش می‌کردند مرتب‌سازی را با کمترین تعداد مقایسه انجام دهند، در این رویه هدف مرتب کردن دنباله با کمترین تعداد ممکن معکوس‌سازی است.

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

  1. اندیس عنصر ماکزیمم در آرایه arr[0..curr_szie-1] را پیدا کرده و آن را mi نام گذاری می‌کنیم.
  2. آرایه را از اندیس صفر تا mi معکوس می‌کنیم.
  3. آرایه را از اندیس صفر تا Curr_size-1 معکوس می‌کنیم.

پیاده‌سازی مرتب‌سازی کلوچه‌ای در سی پلاس پلاس

برای پیاده‌سازی الگوریتم مرتب‌سازی کلوچه‌ای ما سه تابع اصلی می‌نویسیم. اولین تابع FindMax است که اندیس عنصر ماکزیمم را در محدوده 1 تا n مشخص می‌کند. تابع دوم flip است که آرایه را از خانه اول تا n معکوس می‌کند. آخرین تابع Pancakesort است که با استفاده دو تابع اول آرایه ما را مرتب می‌کند.

پیاده سازی توابع بالا به صورت زیر است:

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

مرتب‌سازی کلوچه‌ای در جاوا

خروجی کد بالا به صورت زیر می‌باشد:

پسورد: www.codegate.ir

دسته : آموزش ++c, زبان c++

دیدگاه بگذارید

نظر شما چیست؟

مطلع کردن شما از
avatar

wpDiscuz