در این قسمت تیم کدگیت را با آموزش مرتب‌سازی کلوچه‌ای در سی شارپ (Pancake Sort) همراهی کنید. در ابتدای این آموزش مرتب‌سازی کلوچه‌ای را معرفی و الگوریتم آن را توضیح خواهیم داد. در انتها این جلسه این الگوریتم را با هم پیاده‌سازی خواهیم کرد. همچنین پیشنهاد می‌کنیم قبل از مطالعه این جلسه، آموزش‌های زیر را مطالعه کنید:
مرتب‌سازی کلوچه‌ای در سی شارپ
در مرتب سازی کلوچه ای شما تنها اجازه دارید که یک عملیات بر روی آرایه انجام دهید این عملیات معکوس کردن یا flip آرایه است. بر خلاف روش‌های سنتی که تلاش می‌کردند مرتب‌سازی را با کمترین تعداد مقایسه انجام دهند، در این رویه هدف مرتب کردن دنباله با کمترین تعداد ممکن معکوس‌سازی است.
مرتب‌سازی کلوچه‌ای مانند مرتب‌سازی انتخابی، درون آرایه عنصر ماکزیمم را پیدا کرده و آن را در آخر آرایه قرار می‌دهد و سایز آرایه برای مرتب سازی یک واحد کاهش می‌دهیم. الگوریتم مرتب‌سازی کلوچه‌ای در سی شارپ به صورت زیر می‌باشد(Curr_Size در ابتدا به اندازه طول آرایه است که در هر مرحله یکی کم می‌شود):
- اندیس عنصر ماکزیمم در آرایه [arr[0..curr_szie-1 را پیدا کرده و آن را mi نام گذاری می‌کنیم.
- آرایه را از اندیس صفر تا mi معکوس می‌کنیم.
- آرایه را از اندیس صفر تا Curr_size-1 معکوس می‌کنیم.
پیاده‌سازی مرتب‌سازی کلوچه‌ای در سی شارپ
برای پیاده‌سازی الگوریتم مرتب‌سازی کلوچه‌ای ما سه تابع اصلی می‌نویسیم. اولین تابع FindMax است که اندیس عنصر ماکزیمم را در محدوده 1 تا n مشخص می‌کند. تابع دوم flip است که آرایه را از خانه اول تا n معکوس می‌کند. آخرین تابع Pancakesort است که با استفاده دو تابع اول آرایه ما را مرتب می‌کند.
پیاده سازی توابع بالا به صورت زیر است:
namespace Pancake_Sort
{
class MainClass
{
public static void Main (string[] args)
{
int[] arr = { 45, 21, 40, 30, 33, 20, 15 };
int n = arr.Length;
pancakeSort(arr, n);
Console.WriteLine("Sorted Array: ");
printNumbers (arr);
Console.ReadKey ();
}
private static void printNumbers(int[] input) {
for (int i = 0; i < input.Length; i++) {
Console.Write(input[i] + ", ");
}
Console.WriteLine();
}
/* Reverses arr[0..i] */
static void flip(int[] arr, int i) {
int temp, start = 0;
while (start < i) {
temp = arr[start];
arr[start] = arr[i];
arr[i] = temp;
start++;
i--;
}
}
static int findMax(int[] arr, int n) {
int mi, i;
for (mi = 0, i = 0; i < n; ++i)
if (arr[i] > arr[mi])
mi = i;
return mi;
}
static int pancakeSort(int[] arr, int n) {
for (int curr_size = n; curr_size > 1; --curr_size) {
int mi = findMax(arr, curr_size);
if (mi != curr_size - 1) {
flip(arr, mi);
flip(arr, curr_size - 1);
}
}
return 0;
}
}
}
به طور کلی کاری که انجام داده‌ایم بدین صورت است که بزرگترین خانه آرایه را پیدا کرده و با عملیات معکوس کردن آن را در خانه اول قرار دهیم. اگر بار دوم آرایه را معکوس کنیم بزرگترین عنصر آرایه در انتها قرار می‌گیرد(دقیقا در جای خودش) سپس برای مابقی آرایه همین کار را تکرار می‌کنیم.
خروجی کد بالا به صورت زیر می‌باشد:
Sorted Array 15, 20, 21, 30, 33, 40, 45,
