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

مرتب سازی انتخابی در سی شارپ (Selection Sort)

مرتب سازی انتخابی در سی شارپ

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

مرتب سازی انتخابی

مرتب‌سازی انتخابی یکی از انواع الگوریتم مرتب‌سازی می‌باشد که جزو دسته  الگوریتمهای مرتب‌سازی مبتنی بر مقایسه‌است. این الگوریتم دارای پیچیدگی زمانی از درجهٔ (O(n2 است که به همین دلیل اعمال آن روی مجموعه بزرگی از اعداد کارا به نظرنمی رسدو به طور عمومی ضعیفتر از نوع مشابهش که مرتب‌ساز درجی است عمل می‌کند. این مرتب‌سازی به دلیل سادگی اش قابل توجه‌است(ویکیپدیا).

نحوه عملکرد

این الگوریتم اینگونه عمل می‌کند: ابتدا کوچکترین عنصر مجموعه اعداد را یافته با اولین عدد جابجا می‌کنیم. سپس دومین عنصر کوچکتر را یافته با دومین عدد جابجا می‌کنیم و این روند را برای n-1 عدد اول تکرار می‌کنیم. در حقیقت در هر مرحله ما لیست خود را به دو بخش تقسیم می‌کنیم. زیرلیست اول که قبلاً مرتب کرده‌ایم و سایر اعضای لیست که هنوز مرتب نشده‌است.(ویکیپدیا)

پیاده سازی مرتب سازی انتخابی در سی شارپ

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

 public static void selectionSort(int[] arr) {
            int i, j, minIndex, tmp;
            int n = arr.Length;
            for (i = 0; i < n - 1; i++) {
                minIndex = i;
                for (j = i + 1; j < n; j++)
                    if (arr[j] < arr[minIndex])
                        minIndex = j;
                if (minIndex != i) {
                    tmp = arr[i];
                    arr[i] = arr[minIndex];
                    arr[minIndex] = tmp;
                }
            }
        }

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

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

تست برنامه

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

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

            Console.ReadKey ();

        }

خروجی برنامه به صورت زیر است.

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

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

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

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