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

مارس 24, 2024
ارسال توسط سعید غریبی

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

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

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

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

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

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

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

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

using namespace std;



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--;

    }

}



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;

}



void 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);

         }

    }

}



void printArray(int arr[], int n) {

    for (int i = 0; i < n; ++i)

         printf("%d ", arr[i]);

}



int main() {

    int arr[] = { 23, 10, 20, 11, 12, 6, 7 };

    int n = sizeof(arr) / sizeof(arr[0]);



    pancakeSort(arr, n);



    puts("Sorted Array ");

    printArray(arr, n);

    return 0;

}

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