مرتب‌سازی کلوچه‌ای در جاوا (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 است که با استفاده دو متد اول آرایه ما را مرتب می‌کند.

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

class PancakeSort {



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

     }



     public static void main(String[] args) {

          int arr[] = { 45, 21, 40, 30, 33, 20, 15 };

          int n = arr.length;



          pancakeSort(arr, n);



          System.out.println("Sorted Array: ");

          System.out.println(Arrays.toString(arr));

     }

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

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

Sorted Array:

[15, 20, 21, 30, 33, 40, 45]