Thuật toán HeapSort

Ý tưởng:

Để tìm phần tử nhỏ nhất ở bước i, phương pháp sắp xếp chọn trực tiếp đã không tận dụng được các thông tin đã có được do các phép so sánh ở bước i-1. Phương pháp Heap Sort khắc phục được nhược điểm này.

 Giả sử xét trường hợp sắp xếp tăng dần, khi đó Heap được định nghĩa là một dãy các phần tử al,..,ar thoã các quan hệ sau với mọi  i  thuộc (r,l)

 ai , a2i

 ai  ,  a2i+1      (ai,a2i), (ai,a2i+1) là các cặp phần tử liên đới

o   Tính chất của heap:

 Tính chất 1: Nếu al,.,ar là một Heap thì khi cắt bỏ một số phần tử ở hai đầu của Heap thì dãy con còn lại vẫn là một Heap .

 Tính chất 2: Nếu các phần tử a1,..,an là một Heap thì phần tử a1 (đầu heap) luôn là  phần tử lớn nhất trong Heap.

 Tính chất 3: Mọi dãy al,al+1,…,ar với  2l > r là một Heap

Thuật toán:

  Giai đoạn 1:    Hiệu chỉnh dãy số ban đầu thành Heap

Giai đoạn 2:    Sắp xếp dãy số dựa trên Heap

o   Bước 1:Đưa phần tử lớn nhất về vị trí đứng ở cuối dãy

  r = n;

 Hoán vị (a1,ar)

o   Bước 2: Loại bỏ phần tử lớn nhất ra khỏi Heap r=r-1;

  Hiệu chỉnh phần còn lại của dãy từ al đến ar thành một Heap.

o   Bước 3:Nếu r >1 ( heap còn phần tử) : lặp lại bước 2

  Ngược lại: dừng

o   Dựa vào tính chất 3, ta có thể thực hiện giai đoạn 1 bằng cách bắt đầu từ heap mặc nhiên an/2+1, an/2+2,…,an,  lần lượt thêm vào các phần tử an/2, an/2-1,…,a1. ta sẽ nhận được Heap theo mong muốn. Như vậy giải đoạn 1 tương đương với n/2 lần thực hiện bước 2 của giai đoạn 2.

o   Cài đặt

o   Để cài đặt Heap sort cần xây dựng một số thủ tục phụ trợ:

1. Thủ tục hiệu chỉnh một dãy al,ar thành heap

o   Giả sử có al,al+1,…ar, trong đó đoạn al+1,…ar, đã là một heap.  ta cần xây dựng al,al+1,…,ar thành một heap. để làm điều này ta lần lượt xét quan hệ của một phần tử ai nào đó với các phần tử liên đới của nó trong dãy là a2i và a2i+1,  nếu nó vi phạm quan hệ của heap  thì đổi chổ ai với phần tử liên đới thich hợp của nó – việc đổi này có thể gây phản ứng dây chuyền.

2. Hiệu chỉnh ao,..,an-1 thành heap.

  Cho một dãy bất kỳ al,…,ar ,  theo tính chất 3 ta có dãy an/2+1, an/2+2,…,an đã là một heap. Ghép thêm phần tử an/2  vào bên trái của heap hiện hành và hiệu chỉnh lại dãy an/2,an/2+1,..,ar thành heap.

Cài đặt thuật toán:

void heap_sort(int a[], int n)
{
 int i,j,size=n-1,k,tg,tg2; //Gioi han dan cac phan tu van vun
 while(size>0)
  {
  k=(int)(size-1)/2; //Vun cac phan tu mang thanh dong
  while(k>=0)
   {
  i=k; //Vun phan tu lon nhat len nut tren
   while(i*2<size)
    {
    j=2*i+1;
    if ((j+1<=size)&&(a[j]<a[j+1])) 
    j=j+1;
    if (a[i]<a[j]) 
     {
     tg=a[i];
     a[i]=a[j];
     a[j]=tg;
     i=j;
     }
    else break;
    }
   k--;
   }
  tg2=a[0];
  a[0]=a[size];
  a[size]=tg2;
  size--;
  }
}