Heap Sort

Thuật toán Heap Sort

1.      Ý tưởng:

Việc sắp xếp lại các phần tử của một mảng ban đầu sao cho nó trở thành đống được gọi là vun đống

Sắp xếp vun đống (heapsort) là một trong các phương pháp sắp xếp chọn. Ở mỗi bước của sắp xếp chọn ta chọn phần tử lớn nhất (hoặc nhỏ nhất) đặt vào cuối (hoặc đầu) danh sách, sau đó tiếp tục với phần còn lại của danh sách. Thông thường sắp xếp chọn chạy trong thời gian O(n²). Nhưng heapsort đã giảm độ phức tạp này bằng cách sử dụng một cấu trúc dữ liệu đặc biệt được gọi là đống (heap). Đống là cây nhị phân mà trọng số ở mỗi đỉnh cha lớn hơn hoặc bằng trọng số các đỉnh con của nó. Một khi danh sách dữ liệu đã được vun thành đống, gốc của nó là phần tử lớn nhất, thuật toán sẽ giải phóng nó khỏi đống để đặt vào cuối danh sách.

2.      Thuật toán:

Algorithm heapsort(A, n)

            Input:

                        A: mảng có n phần tử

            Output:

                        Mảng A đã được sắp xếp

            m ß 0

            for k ß 1 to n do

                        insert(A, m, A[k])

            for k ß n downto 1 do

                        A[k] = remove(A, m)

3.      mã nguồn bằng C:

#include<stdio.h>   

#include<conio.h>

      Void  heap()

{

Int r,q,x;

q=n/2+1;

r=n-1;

while(r>0)

{

X=a[0];

A[0]=a[n];

A[n]=x;

r--;

while (q>=0)

{

            Sift(q,r);

q--;

}

q=0;

r=n-1;

sift(q,r);

}

}

Void sift (int q,int r);

{

      Int I,j,x;

I=q;

J=2*i+1;

X=a[i];

While (j<=r)

{

if (i<r)

if(a[i]<a[j+1])

J++;

If(x>a[j]

Break;

A[i]=a[j];

I=j;

J=2*j+1;

}

A[i]=x;

}