الگوریتم Heap Sort

Question

سلام، اگر امکانش هست، الگوریتم مرتب سازی پشته ای یا Heap Sort رو بنویسید.

همچنین در موردش مقداری توضیح هم بدید. (کدش رو ننویسید، طرز کارش رو بگید)

Answer 1

برای نوشتن heap sort  :

۱ـ از روی آرایه max heap رو میسازیم ( این جا توضیح داده شده :‌  ساخت max heap از روی آرایه )

۲ـ عنصر اول که بزرگترین عنصر هم هست رو به آخر آرایه منتقل میکنیم 

3_سایز آرایه و max heap  رو یکی کمتر در نظر می گیریم

4_ از اون جایی که عوض کردن عنصر ممکنه max heap بودن رو به هم بریزه دوباره عملیات max heap رو روی آرایه باقی مونده انجام میدیم .

۵ـ مرحله ۲ رو تا زمانی که سایز آرایه و  max heap صفر نشده دوباره انجام میدیم .

 

ساختن max heap از مرتبه logn  هستش و چون عملیات max heap ما n بار تکرار میشه در مجموع مرتبه الگوریتم nlogn میشه .

 

Answer 2

#include <iostream>
#include <conio.h>
using namespace std;
void max_heapify(int *a, int i, int n)
{
    int j, temp;
    temp = a[i];
    j = 2*i;
    while (j <= n)
    {
        if (j < n && a[j+1] > a[j])
            j = j+1;
        if (temp > a[j])
            break;
        else if (temp <= a[j])
        {
            a[j/2] = a[j];
            j = 2*j;
        }
    }
    a[j/2] = temp;
    return;
}
void heapsort(int *a, int n)
{
    int i, temp;
    for (i = n; i >= 2; i--)
    {
        temp = a[i];
        a[i] = a[1];
        a[1] = temp;
        max_heapify(a, 1, i - 1);
    }
}
void build_maxheap(int *a, int n)
{
    int i;
    for(i = n/2; i >= 1; i--)
    {
        max_heapify(a, i, n);
    }
}
int main()
{
    int n, i, x;
    cout<<"enter no of elements of array\n";
    cin>>n;
    int a[20];
    for (i = 1; i <= n; i++)
    {
        cout<<"enter element"<<(i)<<endl;
        cin>>a[i];
    }
    build_maxheap(a,n);
    heapsort(a, n);
    cout<<"sorted output\n";
    for (i = 1; i <= n; i++)
    {
        cout<<a[i]<<endl;
    }
    getch(); 
}

از نظر آنالیز کد هم میشه گفت order اون O(n*logn) و در هر حالتی (چه بهترین چه بدترین از quick sort بهتره)

Comments

quick sort , heapsort هر ۲تا بهترین حالتشون nlogn هستش
برای داده هایی که تقریبا مرتب هستن heap sort بهتر عمل می کنه (البته تا خدی به نحوه انتخاب  pivot داخل quick sort  هم بستگی داره )
ولی در مجموع خیلی وقت ها quick sort سرعت بالاتری داره .