بررسی الگوریتم مرتب سازی سریع و حبابی در سی شارپ

فرشاد مراحم

بررسی الگوریتم مرتب سازی سریع و حبابی در سی شارپ

در این مقاله قصد داریم تا الگوریتم های مرتب سازی سریع(Quick Sort)  و حبابی (Bubble Sort) را مورد بررسی قرار دهیم و سورس کد مربوط به آنها را به طور کامل تشریح کنیم تا با کاربردهای الگوریتم های مرتب سازی بیشتر آشنا شویم.

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

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

 class quicksort
    {
       public int[] array = new int[20];
       public int len;

        public void QuickSort()
        {
            sort(0, len - 1);
        }

        public void sort(int left, int right)
        {
            int pivot, leftend, rightend;

            leftend = left;
            rightend = right;
            pivot = array[left];

            while (left < right)
            {
                while ((array[right] >= pivot) && (left < right))
                {
                    right--;
                }

                if (left != right)
                {
                    array[left] = array[right];
                    left++;
                }

                while ((array[left] <= pivot) && (left < right))
                {
                    left++;
                }

                if (left != right)
                {
                    array[right] = array[left];
                    right--;
                }
            }

            array[left] = pivot;
            pivot = left;
            left = leftend;
            right = rightend;

            if (left < pivot)
            {
                sort(left, pivot - 1);
            }

            if (right > pivot)
            {
                sort(pivot + 1, right);
            }
        }
       
     

الگوریتم مرتب سازی حبابی (Bubble Sort) : یکی از روش های ساده و پر کاربرد در بحث مرتب سازی عناصر می باشد.این الگوریتم هر بار دو خانه مجاور را باهم مقایسه کرده، اگر ترتیب آن‌ها درست نبود، جای آن‌ها را عوض می‌کند و یک خانه جلو می‌رود. به این ترتیب پس از یک بار پیمایش آرایه یک خانه در جای درست خود قرار می‌گیرد و این کار تا زمانی که لیست کاملاً مرتب شود ادامه می‌یابد. دلیل نام‌گذاری آن نیز از این روست که حرکت یک کلید به سمت مکان نهایی آن شبیه پویش حباب به بالای مایع است.

 int[] a = { n1, n2, n3, n4, n5 };
                int t;
              
                for (int i = 0; i < a.Length; i++)
                {
                    Console.WriteLine(a[i]);
                }
                for (int j = 0; j <= a.Length - 2; j++)
                {
                    for (int i = 0; i <= a.Length - 2; i++)
                    {
                        if (a[i] > a[i + 1])
                        {
                            t = a[i + 1];
                            a[i + 1] = a[i];
                            a[i] = t;
                        }
                    }
                }
                foreach (int array in a)
                    richTextBox1.Text += array+"\n";
            }
        }

مقایسه دو روش نسبت به یکدیگر :

1) الگوریتم مرتب سازی حبابی برای مجموعه داده‌های بزرگ مناسب نیست، زیرا پیچیدگی زمانی آن در حالت میانگین و بدترین حالت برابر با (Ο(n2 است، که در آن n تعداد کل عناصر مجموعه داده محسوب می‌شود.تا جایی که تحقیقات نشان می‌دهد مرتب‌سازی حبابی در عمل ۵ برابر کند تر از مرتب‌سازی درجی و ۴۰ درصد کندتر از مرتب‌سازی انتخابی می‌باشد.

2) الگوریتم مرتب سازی سریع پیچیدگی زمانی اجرای الگوریتم در بهترین حالت (Ο(nlogn و در بدترین حالت (Ο(n2 است. با استفاده محاسبات ریاضی می‌توان نشان داد در حالت متوسط نیز مرتبه‌ی اجرا (Ο(nlogn است. این الگوریتم یک مرتب‌سازی درجا است. یعنی میزان حافظه‌ی مصرفی الگوریتم مستقل از طول آرایه است.

3) الگوریتم سریع در عمل برای مرتب‌سازی آرایه‌های نسبتا کوچک اصلا مناسب نیست. به علاوه بخش تقسیم‌بندی آرایه نیز مشکل بزرگی در زمان اجرا می‌باشد. به همین دلیل پیشنهاد می‌شود برای ۷ داده یا کمتر از انواع دیگر مرتب‌سازی مثل مرتب‌سازی درجی استفاده شود.