مقایسه تصویری انواع الگوریتم های مرتب‌سازی

مقدمه

به نظرم اولین و مهمترین چیزی که باید بفهمیم اینه که اصلا الگوریتم های مرتب سازی چه هستند. بر اساس ویکی‌پدیا، الگوریتم مرتب سازی، الگوریتمی است که عناصر یک لیست را به ترتیب خاصی در می‌آورد. کاربردی‌ترین ترتیب ها، ترتیب‌های عددی و ترتیب‌های وابسه به حروف هستند. بعضی از الگوریتم‌ها (از جمله الگوریتم‌های جستجو و ادغام) برای اینکه بدرستی کار کنند، نیازمند لیست‌های مرتب شده می باشند؛ مرتب‌سازی مؤثر و کارآمد، برای بهینه سازی کارائی چنین الگوریتم‌هایی، مهم هستند. این اگوریتم‌ها، اغلب اوقات، برای به نظم در آوردن داده‌ها و تولید خروجی قابل خواندن برای انسان، مفید هستند.

من، در این مقاله، برخی از الگوریتم‌های مرتب‌سازی را شرح خواهم داد. همه الگوریتم هایی که در اینجا مورد بحث قرار گرفته اند، در زبان برنامه نویسی #C نوشته شده‌اند و بسیاری از ایده‌ها، بر اساس الگوریتم‌هایی است که شما می‌توانید در ویکی‌پدیا پیدا کنید.

الگوریتم‌هایی که در این مقاله با آنها آشنا خواهید شد:

• مرتب سازی حبابی دوطرفه (Bidirectional Bubble Sort)
• مرتب سازی حبابی (Bubble Sort)
• مرتب سازی سطلی (Bucket Sort)
• مرتب سازی شانه ای (Comb Sort)
• مرتب سازی چرخه‌ای (Cycle Sort)
• مرتب سازی گورزاد (Gnome Sort)
• مرتب سازی هرمی (Heap Sort)
• مرتب سازی درجی (Insertion Sort)
• مرتب سازی ادغامی (Merge Sort)
• مرتب سازی زوج-فرد (Odd-Even Sort)
• مرتب سازی لانه کبوتری (Pigeonhole Sort)
• مرتب سازی سریع (Quick Sort)
• مرتب سازی سریع با استفاده از مرتب سازی حبابی (Quick Sort with Bubble Sort)
• مرتب سازی انتخابی (Selection Sort)
• مرتب سازی شل یا پوسته ای (Shell Sort)

قصد دارم طرز کار این الگوریتم ها رو بصورت دیداری به شما نشان بدهم. کاربر می تواند، خروجی این پروژه را بصورت تصاویر متحرک GIF، با سرعت دلخواه، ذخیره کند.

طرز استفاده از برنامه

این Solution حاوی 2 پروژه است. پروژه اول (Components) ، برای ساختن تصاویر متحرک GIF ، کلاس هایی را ارائه می‌دهد. این پروژه بر اساس پروژه NGIF است. برای اطلاعات بیشتر در مورد این پروژه، به NGIF مراجعه کنید.

پروژه دوم (SortComparison) بخش اصلی Solution است. شما می‌توانید، در فرمی بنام frmMain ، نوع الگوریتم مرتب‌سازی، تعداد نمونه‌هایی که می‌خواهید مرتب کنید، سرعت مرتب‌سازی و اینکه آیا می‌خواهید یک فایل GIF متحرک بسازید را مشخص کنید. روی فرم، 2 پنل به نام‌های pnlSort1 و pnlSort2 وجود دارد که عملیات مرتب‌سازی را بصورت تصویری به نمایش در می‌آورند.

هر الگوریتم، نام مربوط به خود را دارد؛ این نام بر اساس نام الگوریتم مرتب‌سازی مربوطه انتخاب شده و یک پارامتر IList دریافت کرده و یک شیئ IList را برمیگرداند.

متد DrawSamples همه نمونه‌ها را روی پنل رسم می‌کند. این متد زمانی فراخوانی می‌شود که به تعداد کافی، نمونه‌های تصادفی تولید شده باشد. با کلیک بر روی دکمه Shuffle ، می‌توانید نمونه‌های تصادفی تولید کنید. نمونه‌ها در داخل متغیر array ذخیره خواهند شد.

private void DrawSamples()
{
    g.Clear(Color.White);
            
    for (int i = 0; i < array.Count; i++)
    {
        int x = (int)(((double)pnlSamples.Width / array.Count) * i);
                
        Pen pen = new Pen(Color.Black);
        g.DrawLine(pen, new Point(x, pnlSamples.Height), 
          new Point(x, (int)(pnlSamples.Height - (int)array[i])));
    }
}

متد Randomize ، همه نمونه‌ها را بصورت تصادفی و شانسی در متغیر array قرار می‌دهد.

public void Randomize(IList list)
{
    for (int i = list.Count - 1; i > 0; i--)
    {
        int swapIndex = rng.Next(i + 1);
        if (swapIndex != i)
        {
            object tmp = list[swapIndex];
            list[swapIndex] = list[i];
            list[i] = tmp;
        }
    }
}

در حین عمل مرتب‌سازی، وقتی چک‌باکس Create animation تیک خورده باشد، بعد از هر جابجایی در عناصر آرایۀ نمونه‌ها، تصاویر متناظر آن، تولید می‌شود. این تصاویر از 0 تا n شاخص‌گذاری شده‌اند، که n نشان‌دهنده تعداد جابجایی‌های فعلی می‌باشد.

private void SavePicture()
{
    ImageCodecInfo myImageCodecInfo = this.getEncoderInfo("image/gif"); 
    EncoderParameter myEncoderParameter = new EncoderParameter(
      System.Drawing.Imaging.Encoder.Compression, (long)EncoderValue.CompressionLZW);
    EncoderParameter qualityParam = 
      new EncoderParameter(System.Drawing.Imaging.Encoder.Quality, 0L);
    EncoderParameters myEncoderParameters = new EncoderParameters(1);

    EncoderParameters encoderParams = new EncoderParameters(2);
    encoderParams.Param[0] = qualityParam;
    encoderParams.Param[1] = myEncoderParameter;

    string destPath = 
      System.IO.Path.Combine(txtOutputFolder.Text, imgCount + ".gif");
    bmpsave.Save(destPath, myImageCodecInfo, encoderParams);
    imgCount++;
}

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

مرتب‌سازی حبابی

مرتب‌سازی حبابی (Bubble Sort) یا مرتب‌سازی غرقی (Sinking Sort)، یک الگوریتم مرتب‌سازی ساده است. این الگوریتم برای مرتب کردن لیست، مکررا لیست را پیمایش می‌کند و هر جفت‌ از عناصر مجاور هم را مقایسه کرده و در صورتی که در مکان اشتباه قرار گرفته باشند، آنها را جابجا می‌کند. این گذر کردن از لیست، تا زمانی که عناصر لیست نیاز به هیچ جابجایی نداشته باشند (که نشان دهنده مرتب شدن لیست است) ، ادامه پیدا می‌کند. این الگوریتم، نام خود را از اینجا بدست آورده که، عناصر کوچکتر، مانند "حباب" به سمت بالای لیست، حرکت می‌کنند. [و عناصر بزرگتر، مانند "غرق" شدن سنگ، به سمت پایین لیست حرکت می‌کنند]. این الگوریتم برای انجام عملیات روی عناصر لیست، فقط از "مقایسه" استفاده می‌کند، به همین علت، یک الگوریتم مقایسه‌ای است. مرتب‌سازی درجی که به سادگی مرتب‌سازی حبابی است، از کارایی بهتری نسبت به مرتب‌سازی حبابی برخوردار است، بنابراین برخی افراد پیشنهاد می‌کنند که دیگر الگوریتم مرتب‌سازی حبابی، آموزش داده نشود.

public IList BubbleSort(IList arrayToSort)
{
    int n = arrayToSort.Count - 1;
    for (int i = 0; i < n; i++)
    {
        for (int j = n; j > i; j--)
        {
            if (((IComparable)arrayToSort[j - 1]).CompareTo(arrayToSort[j]) > 0)
            {
                object temp = arrayToSort[j - 1];
                arrayToSort[j - 1] = arrayToSort[j];
                arrayToSort[j] = temp;
                RedrawItem(j);
                RedrawItem(j - 1);
                pnlSamples.Refresh();
                if (chkCreateAnimation.Checked)
                    SavePicture();
            }
        }
    }
    return arrayToSort;
}

بدترین حالت کارایی:	O(n2)
بهترین حالت کارایی:	O(n)
کارایی در حالت میانگین:	O(n2)
پیچیدگی حافظه در بدترین حالت:	کمکی O(1)

مرتب‌سازی حبابی دوطرفه (Bidirectional Bubble Sort)

مرتب‌سازی Cocktail که با نام مرتب‌سازی حبابی دوطرفه نیز شناخته شده است؛ مرتب‌سازی Cocktail Shaker، مرتب‌سازی Shaker (که به یکی از انواع مرتب‌سازی انتخابی اشاره دارد)، مرتب‌سازی موجی (Ripple)، مرتب‌سازی رفت و برگشتی (Shttle sort)، یا مرتب‌سازی Happy Hour (اینا همه شون اسم های دیگر مرتب‌سازی حبابی دوطرفه هستند)، یک نوع از مرتب‌سازی حبابی است که هم یک الگوریتم پایدار است و هم یک مرتب‌سازی مقایسه‌ای است. این الگوریتم، با مرتب‌سازی حبابی تفاوت دارد، از این جهت که در هر گذر از لیست، مرتب‌سازی را در دو طرف لیست، انجام می‌دهد. پیاده‌سازی این الگوریتم، اندکی از مرتب‌سازی حبابی سخت‌تر است، و مسأله را با همان سرعت الگوریتم مرتب‌سازی حبابی، حل می‌کند.

اولین گذر به سمت راست، بزرگترین عنصر لیست را به مکان صحیح خود (انتهای لیست)، انتقال می‌دهد و گذر سمت چپ، کوچکترین عنصر لیست را به مکان صحیح خود در ابتدای لیست، منتقل خواهد کرد. دومین گذر کامل، در این الگوریتم، کوچکترین عنصر دوم و بزرگترین عنصر دوم را به مکان صحیح خودشان منتقل خواهد کرد و همینطور الی آخر. بعد از i مین گذر، i عنصر اول و i عنصر آخر لیست، در مکان صحیح خودشان قرار می گیرند و نیازی به بررسی کردن هم نیست. با کوتاه‌سازی قسمتی از لیست که هر دفعه مرتب می‌شود، تعداد عملیات مربوط به مرتب‌سازی می‌تواند نصف شود.

public IList BiDerectionalBubleSort(IList arrayToSort) 
{
    int limit = arrayToSort.Count;
    int st = -1;
    bool swapped = false;
    do
    {
        swapped = false;
        st++;
        limit--;
                
        for (int j = st; j < limit; j++)
        {
            if (((IComparable)arrayToSort[j]).CompareTo(arrayToSort[j + 1]) > 0)
            {
                object temp = arrayToSort[j];
                arrayToSort[j] = arrayToSort[j + 1];
                arrayToSort[j + 1] = temp;
                swapped = true;
                RedrawItem(j);
                RedrawItem(j + 1);
                pnlSamples.Refresh();
                if(chkCreateAnimation.Checked)
                    SavePicture();

            }
        }
        for (int j = limit - 1; j >= st; j--)
        {
            if (((IComparable)arrayToSort[j]).CompareTo(arrayToSort[j + 1]) > 0)
            {
                object temp = arrayToSort[j];
                arrayToSort[j] = arrayToSort[j + 1];
                arrayToSort[j + 1] = temp;
                swapped = true;
                RedrawItem(j);
                RedrawItem(j + 1);
                        
                pnlSamples.Refresh();
                if (chkCreateAnimation.Checked)
                    SavePicture();

            }
        }

    } while (st < limit && swapped);

    return arrayToSort;
}

بدترین حالت کارایی:	O(n2)
بهترین حالت کارایی:	O(n)
کارایی در حالت میانگین:	O(n2)
پیچیدگی حافظه در بدترین حالت:	کمکی O(1)

مرتب‌سازی سطلی (Bucket Sort)

مرتب‌سازی سطلی یا bin sort ، یک الگوریتم مرتب سازی است که با افراز آرایه به تعدادی سطل، کار می‌کند. نهایتا هر سطل بصورت جداگانه مرتب‌سازی خواهد شد. روش مرتب‌سازی سطل ها می‌تواند با استفاده از الگوریتم‌های مرتب‌سازی دیگر باشد و یا اینکه بصورت بازگشتی، الگوریتم مرتب‌سازی سطلی را اعمال کنیم. این یک مرتب‌سازی توزیع شده، بوده و پسرعموی مرتب‌سازی Radix در اعداد بزرگتر به کوچکتر است. مرتب‌سازی سطلی، تعمیم یافتۀ مرتب‌سازی لانه کبوتری است. از آنجا که مرتب‌سازی سطلی، از نوع مرتب‌سازی مقایسه‌ای نیست، حد پایین (O(n log n غیرقابل تطبیق است. تخمین‌های پیچیدگی محاسباتی با تعداد سطل‌ها در ارتباط است.

مرتب‌سازی سطلی، بصورت زیر کار می‌کند:

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

public IList BucketSort(IList arrayToSort)
{
    if (arrayToSort == null || arrayToSort.Count == 0) return arrayToSort;

    object max = arrayToSort[0];
    object min = arrayToSort[0];


    for (int i = 0; i < arrayToSort.Count; i++)
    {

        if (((IComparable)arrayToSort[i]).CompareTo(max) > 0)
        {
            max = arrayToSort[i];
        }

        if (((IComparable)arrayToSort[i]).CompareTo(min) < 0)
        {
            min = arrayToSort[i];
        }
    }
    ArrayList[] holder = new ArrayList[(int)max - (int)min + 1];

    for (int i = 0; i < holder.Length; i++)
    {
        holder[i] = new ArrayList();
    }

    for (int i = 0; i < arrayToSort.Count; i++)
    {
        holder[(int)arrayToSort[i] - (int)min].Add(arrayToSort[i]);
    }

    int k = 0;

    for (int i = 0; i < holder.Length; i++)
    {
        if (holder[i].Count > 0)
        {
            for (int j = 0; j < holder[i].Count; j++)
            {
                arrayToSort[k] = holder[i][j];
                RedrawItem(k);
                pnlSamples.Refresh();
                if (chkCreateAnimation.Checked)
                    SavePicture();
                k++;
            }
        }
    }

    return arrayToSort;
}

بدترین حالت کارایی:	O(n2.k)
بهترین حالت کارایی:	-
کارایی در حالت میانگین:	O(n.k)
پیچیدگی حافظه در بدترین حالت:	O(n.k)

مرتب‌سازی شانه‌ای (Comb Sort)

این مقاله درحال کامل شدن هست...