#c, سی شارپ, مرتب سازی در #c

مرتب سازی درجی در سی شارپ (Insertion Sort)

مرتب سازی درجی در سی شارپ

در این جلسه تیم کدگیت را با آموزش مرتب سازی درجی در سی شارپ همراهی کنید. پیش نیاز این آموزش آشنایی با آرایه و توابع هست.

مرتب سازی درجی

مرتب‌ساز درجی (Insertion Sort)  یک الگوریتم مرتب‌سازی ساده بر مبنای مقایسه است. این الگوریتم برای تعداد داده‌های زیاد، کارآمد نیست و در این موارد، الگوریتم‌های بهتری مثل مرتب‌ساز سریع، مرتب‌ساز ادغامی و مرتب‌ساز پشته وجود دارد.(ویکیپدیا)

الگوریتم

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

معمول‌ترین نسخه از این الگوریتم که روی آرایه‌ها عمل می‌کند، به این صورت است:

  1. فرض کنید یک تابع به اسم Insert داریم که داده را در بخش مرتب شده در ابتدای آرایه درج می‌کند. این تابع با شروع از انتهای سری شروع به کار می‌کند و هر عنصر را به سمت راست منتقل می‌کند تا وقتی که جای مناسب برای عنصر جدید پیدا شود. این تابع این اثر جانبی را دارد که عنصر دقیقاً بعد از بخش مرتب شده را رونویسی می‌کند.
  2. برای اعمال مرتب‌ساز درجی، از انتهای سمت چپ آرایه شروع می‌کنیم و با صدا زدن تابع insert، هر عنصر را به موقعیت درستش می‌بریم. آن بخشی که عنصر فعلی را در آن می‌کنیم، در ابتدای آرایه و در اندیس‌هایی است که آنها را قبلاً آزمایش کرده‌ایم. هر بار صدا زدن تابع insert، یک عنصر را رونویسی می‌کند، اما این مسئله مشکلی ایجاد نمی‌کند، زیرا این داده، همانی است که الان در حال درج آن هستیم(ویکیپدیا)

مرتب سازی درجی در سی شارپ

برای پیاده سازی مرتب سازی درجی در سی شارپ باید ابتدا فرآیند این الگوریتم را خوب متوجه شوید. ابتدا این الگوریتم فرض میکند ما فقط یک خانه داریم و عنصر بعدی به این یک خانه اضافه میکند و این دو خانه مرتب میشوند. حال که دو خانه مرتب شدند عنصر سوم را به دو خانه قبلی اضافه میکند و حال این 3 خانه را مرتب میکند. این کار را تا جایی ادامه میدهد که تمام عناصر ما مرتب شده باشند.

        public static void insertionSort(int[] array) {
            int n = array.Length;
            for (int j = 1; j < n; j++) {
                int key = array[j];
                int i = j - 1;
                while ((i > -1) && (array[i] > key)) {
                    array[i + 1] = array[i];
                    i--;
                }
                array[i + 1] = key;
                //            printNumbers(array);
            }
        }

        private static void printNumbers(int[] input) {
            for (int i = 0; i < input.Length; i++) {
                Console.Write(input[i] + ", ");
            }
            Console.WriteLine();
        }

توضیح کد بالا کمی دشوار است ولی توضیح کلی که در مورد کد میتوان داد این است که حلقه for برای تعداد خانه های آرایه است(همانطور که گفتیم الگوریتم تا تمامی عناصر را مرتب نکند تمام نمیشود) و حلقه دوم برای مرتب کردن عناصر از 0 تا j است.متد printnumbers برای چاپ آرایه است.

برای تست برنامه مرتب سازی درجی در سی شارپ کد زیر را بزنید.

        public static void Main (string[] args)
        {
            int[] input = { 4, 2, 9, 6, 23, 12, 34, 0, 1 };
            Console.WriteLine("befor sort");
            printNumbers(input);
            insertionSort(input);
            Console.WriteLine("after sort");
            printNumbers(input);

            Console.ReadKey ();

        }

خروجی برنامه

0, 1, 2, 4, 6, 9, 12, 23, 34,

نوشته های مشابه

1 دیدگاه در “مرتب سازی درجی در سی شارپ (Insertion Sort)

  1. majid گفت:

    ممنون بابا مطالب مفیدی که نوشتید

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *