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

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

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

  1. الگوریتم از انتهای آرایه تا سومین خانه از آرایه را بررسی می‌کند.
  2. هربار بایستی ایندکس بیشترین یا ماکزیمم مقدارِ درون آرایه، تا ایندکس فعلی پیدا شود. یعنی فقط محدوده‌ی 0 تا ایندکس فعلی بررسی می‌شود.
  3. اگر خود ایندکس ماکسیمم، کوچک‌تر از خود ایندکس یک خانه‌ی پایین‌تر باشد، عملیات معکوس‌سازی بایستی رخ دهد.
    این عملیات:

    1. یک بار عملیات معکوس‌سازی تا ایندکس خانه‌ی ماکسیمم صورت می‌گیرد.
    2. یک بار دیگر تا یک ایندکس پایین‌تر از ایندکس خانه‌ی فعلی انجام می‌شود.

پیاده‌سازی الگوریتم

در ابتدا کد کامل را در نظر بگیرید:

using System;

namespace ConsoleApp1
{
    class Program
    {

        static void Main(string[] args)
        {
            
            int[] sampleArray = { 85, 1, -9, 20, 9, 5, 0, 14, 74 };
            Console.WriteLine("Sample Array = [{0}]", string.Join(", ", sampleArray));
            
            PancakeSort(sampleArray, sampleArray.Length);
            Console.WriteLine("Sorted Array = [{0}]", string.Join(", ", sampleArray));
            
            Console.ReadKey();

        }

        static int FindMax(int[] arr, int n)
        {
            int i, max;
            for (i = 0, max = 0; i < n; ++i) if (arr[i] > arr[max]) max = i;
            return max;
        }

        static void Reverse(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 PancakeSort(int[] arr, int n)
        {
            
            for (int currentSize = n; currentSize > 1; --currentSize)
            {
                int max = FindMax(arr, currentSize);

                if (max != currentSize - 1)
                {
                    Reverse(arr, max);

                    Reverse(arr, currentSize - 1);
                }
            }

            return 0;

        }

    }
}
  • تابع FinMaxIndex: با دریافت آرایه و طول بازه (محدوده)، ایندکس بزرگترین خانه را در آن بازه پیدا می‌کند.
  • تابع Reverse: با دریافت آرایه و طول بازه (محدوده)، آرایه را از خانه اول تا طول بازه معکوس می‌کند.
  • تابع PancakeSort: عملیات کلی الگوریتم را انجام می‌دهد؛ که در آن، از دو تابع بالا استفاده شده است.

در اینجا مشاهده می‌شود که هربار ایندکس بزرگترین خانه، در محدوده‌ی مورد نظر پیدا شده و سپس در ابتدا با عملیات معکوس‌سازی در خانه‌ی اول قرار گرفته و بار دیگر با عملیات معکوس‌سازی، به انتهای خانه منقل شود. تصویر زیر، یک فرآیند را نمایش می‌دهد:

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

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد.

cp-codfk

نظرات ثبت شده بدون دیدگاه

توضیحات پیشنهادی نظرات اشتراک