مرتب سازی هرمی (Heap Sort) در سی شارپ

سلام توسعه دهندگان گرامی در این سری از آموزش برنامه نویسی سی شارپ به آموزش مرتب سازی هرمی (Heap Sort) در سی شارپ می پردازیم از مرتب سازی بروی آرایه صورت می گیرید الگوریتم های مختلفی جهت مرتب سازی آرایه وجود دارد در ادامه مرتب سازی هرمی (Heap Sort) را شرح خواهیم داد با ما همراه باشید.

مرتب سازی هرمی (Heap Sort) چیست ؟ الگوریتم مرتب سازی هرمی

در یک max-heap (یا min-heap) بزرگترین (یا کوچکترین) مقدار بین داده‌ها همواره در ریشه‌ی درخت قرار دارد. یافتن بزرگترین (یا کوچکترین) عنصر بین عناصر، هزینه‌ی ثابت ( Ө( 1 دارد. با حذف این عنصر از درخت، بزرگترین (یا کوچکترین) عنصر بعدی مجددا در ریشه قرار می‌گیرد. به این ترتیب با حذف متوالی عناصر درخت heap و درج آنها در محل جدید، یک آرایه‌ی مرتب‌شده‌ی نزولی (یا صعودی) به دست خواهد آمد.

مراحل مرتب‌سازی هرمی به ترتیب زیر خواهد بود:

Step 0 )   min-heap: 1, 4, 5, 8, 6, 9      -    list:
Step 1 )   min-heap: 4, 6, 5, 8, 9          -    list: 1
Step 2 )   min-heap: 5, 6, 9, 8              -    list: 1, 4
Step 3 )   min-heap: 6, 8, 9                  -    list: 1, 4, 5
Step 4 )   min-heap: 8, 9                      -    list: 1, 4, 5, 6
Step 5 )   min-heap: 9                          -    list: 1, 4, 5, 6, 8
Step 6 )   min-heap:                             -    list: 1, 4, 5, 6, 8, 9

Step 0 ) min-heap: 1, 4, 5, 8, 6, 9 - list:

Step 1 ) min-heap: 4, 6, 5, 8, 9 - list: 1

Step 2 ) min-heap: 5, 6, 9, 8 - list: 1, 4

Step 3 ) min-heap: 6, 8, 9 - list: 1, 4, 5

Step 4 ) min-heap: 8, 9 - list: 1, 4, 5, 6

Step 5 ) min-heap: 9 - list: 1, 4, 5, 6, 8

Step 6 ) min-heap: - list: 1, 4, 5, 6, 8, 9

در ادامه نحوه پیاده سازی آن را در سی شارپ برای شما قرار میدهیم.

using System;
class heap
{
    int[] r = { 2,5,1,10,6,9,3,7,4,8};
    public void hsort()
    {
        int i, t;
        for (i = 5; i >= 0; i--)
        {
            adjust(i, 9);
        }
        for (i = 8; i >= 0; i--)
        {
            t = r[i + 1];
            r[i + 1] = r[0];
            r[0] = t;
            adjust(0, i);
        }
    }
    private void adjust(int i, int n)
    {
        int t, j;
        try
        {
            t = r[i];
            j = 2 * i;
            while (j <= n)
            {
                if (j < n && r[j] < r[j + 1])
                    j++;
                if (t >=r[j])
                    break;
                r[j / 2] = r[j];
                j *= 2;
            }
            r[j / 2] = t;
        }
        catch (IndexOutOfRangeException e)
        {
            Console.WriteLine("Array Out of Bounds ", e);
        }
    }
    public void print()
    {
        for (int i = 0; i < 10; i++)
        {
            Console.WriteLine("{0}", r[i]);
        }
    }
    public static void Main()
    {
        heap obj = new heap();
        Console.WriteLine("Elements Before sorting : ");
        obj.print();
        obj.hsort();
        Console.WriteLine("Elements After sorting : ");
        obj.print();
        Console.Read();
    }
}

using System;

class heap

{

int[] r = { 2,5,1,10,6,9,3,7,4,8};

public void hsort()

{

int i, t;

for (i = 5; i >= 0; i--)

{

adjust(i, 9);

}

for (i = 8; i >= 0; i--)

{

t = r[i + 1];

r[i + 1] = r[0];

r[0] = t;

adjust(0, i);

}

private void adjust(int i, int n)

{

int t, j;

try

{

t = r[i];

j = 2 * i;

while (j <= n)

{

if (j < n && r[j] < r[j + 1])

j++;

if (t >=r[j])

break;

r[j / 2] = r[j];

j *= 2;

}

r[j / 2] = t;

}

catch (IndexOutOfRangeException e)

{

Console.WriteLine("Array Out of Bounds ", e);

}

public void print()

{

for (int i = 0; i < 10; i++)

{

Console.WriteLine("{0}", r[i]);

}

public static void Main()

{

heap obj = new heap();

Console.WriteLine("Elements Before sorting : ");

obj.print();

obj.hsort();

Console.WriteLine("Elements After sorting : ");

obj.print();

Console.Read();

}

خروجی کد بالا همانند زیر خواهد بود.

Elements Before Sorting :
2
5
1
10
6
9
3
7
4
8
Elements After Sorting :
1
2
3
4
5
6
7
8
9
10

Elements Before Sorting :

Elements After Sorting :

این آموزش هم به پایان رسید.
موفق و پیروز باشید.

مطالعه بیشتر

مرتب سازی هرمی (Heap Sort) در سی شارپ

مرتب سازی هرمی (Heap Sort) چیست ؟ الگوریتم مرتب سازی هرمی

مطالب مشابه

دیدگاهتان را بنویسید لغو پاسخ

مرتب سازی هرمی (Heap Sort) چیست ؟ الگوریتم مرتب سازی هرمی

مطالب مشابه

دیدگاهتان را بنویسید لغو پاسخ

اشتراک گذاری در شبکه های اجتماعی