مرتب‌سازی کلوچه‌ای در سی شارپ (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