CNTT4A2 COMMUNITY

Thảo luận học tập


You are not connected. Please login or register

Go downThông điệp [Trang 1 trong tổng số 1 trang]

21/2/2012, 8:38 pm
kienhl
kienhl

1.Ý tưởng:
Nhận xét: Khi 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.
Vì lý do trên người ta tìm cách xây dựng một thuật toán sắp xếp có thể khắc phục nhược điểm này.
Mấu chôt để giải quyết vấn đề vừa nêu là phải tìm ra được một cấu trúc dữ liệu cho phép tích lũy các thông tin về sự so sánh giá trị các phần tử trong qua trình sắp xếp.
Giả sử dữ liệu cần sắp xếp là dãy số : 5 2 6 4 8 1 được bố trí theo quan hệ so sánh và tạo thành sơ đồ dạng cây như sau :


Trong đó một phần tử ở mức i chính là phần tử lớn trong cặp phần tử ở mức i+1, do đó phần tử ở mức 0 (nút gốc của cây) luôn là phần tử lớn nhất của dãy.
Nếu loại bỏ phần tử gốc ra khỏi cây (nghĩa là đưa phần tử lớn nhất về đúng vị trí), thì việc cập nhật cây chỉ xảy ra trên những nhánh liên quan đến phần tử mới loại bỏ, còn các nhánh khác được bảo toàn, nghĩa là bước kế tiếp có thể sử dụng lại các kết quả so sánh ở bước hiện tại.
Trong ví dụ trên ta có :

Loại bỏ 8 ra khỏi cây và thế vào các chỗ trống giá trị -∞ để tiện việc cập nhật lại cây :




Tiến hành nhiều lần việc loại bỏ phần tử gốc của cây cho đến khi tất cả các phần tử của cây đều là -∞, khi đó xếp các phần tử theo thứ tự loại bỏ trên cây sẽ có dãy đã sắp xếp. Trên đây là ý tưởng của giải thuật sắp xếp cây.

2. Cấu trúc dữ liệu Heap
Tuy nhiên, để cài đặt thuật toán này một cách hiệu quả, cần phải tổ chức một cấu trúc lưu trữ dữ liệu có khả năng thể hiện được quan hệ của các phần tử trong cây với n ô nhớ thay vì 2n-1 như trong ví dụ.
Khái niệm heap và phương pháp sắp xếp Heapsort do J.Williams đề xuất đã giải quyết được các khó khăn trên.
Ðịnh nghĩa Heap:
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ử ap, a2 ,... , aq thoả các quan hệ sau với mọi i thuộc [p, q]:
1/. ai >= a2i
2/. ai >= a2i+1
{(ai , a2i), (ai ,a2i+1) là các cặp phần tử liên đới }
Heap có các tính chất sau :
Tính chất 1 : Nếu ap , a2 ,... , aq là một heap thì khi cắt bỏ một số phần tử ở hai đầu của heap, dãy con còn lại vẫn là một heap.
Tính chất 2 : Nếu ap , a2 ,... , aq 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 ap , a2 ,... , aq, dãy con aj, aj+1,…, ar tạo thành một heap với j=(q div 2 +1).

Giải thuật Heapsort :
Giải thuật Heapsort trải qua 2 giai đoạ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:
Bước 1: Ðưa phần tử lớn nhất về vị trí đúng ở cuối dãy:
r = n; Hoánvị (a1 , ar );
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ừ a1 , a2 ... ar thành một heap.
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

Dựa trên 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, sau đó thêm dần các phần tử an/2, an/2-1, ., a1 ta sẽ nhân được heap theo mong muốn.
Ví dụ
Cho dãy số a:
12 2 8 5 1 6 4 15
Giai đoạn 1: hiệu chỉnh dãy ban đầu thành heap


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

thực hiện tương tự cho r=5,4,3,2 ta được:



Cài đặt


Ðánh giá giải thuật

Trong giai đoạn sắp xếp ta cần thực hiện n-1 bước mỗi bước cần nhiều nhất là log2(n-1), log2(n-2), … 1 phép đổi chỗi.
Như vậy độ phức tạp thuật toán Heap sort O(nlog2n)

Code:
#include <iostream.h>
#include <conio.h>
#define max 100
void NhapMang(int A[],int n)
   {
      for(int i=0; i<n; i++)
      {
         cout<<"nhap Phan tu thu A["<<i<<"] =";
         cin>>A[i];
      }
   }
void XuatMang(int A[],int n)
   {
      cout<<endl;
      for(int i=0; i<n; i++)
      cout<<A[i]<<"\t";
   }
void Swap(int &a,int &b)
   {
      int temp = a;
      a = b;
      b = temp;
   }
//hoan vi nut cha thu i phai lon hon nut con
void Heapify(int A[],int n, int i)
   {
      int Left = 2*(i+1)-1;
      int Right = 2*(i+1);
      int Largest;
      if(Left < n && A[Left] > A[i])
         Largest = Left;
      else
         Largest = i;
      if(Right<n && A[Right]>A[Largest])
         Largest = Right;
      if(i! = Largest)
      {
         Swap(A[i],A[Largest]);
         Heapify(A,n,Largest);
      }
   }
//xay dung Heap sao cho moi nut cha luon lon hon nut con tren cay
void BuildHeap(int A[], int n)
   {
      for(int i = n/2-1; i>=0; i--)
      Heapify(A,n,i);
   }
void HeapSort(int A[], int n)
   {
      BuildHeap(A,n);
      for(int i = n-1; i>0; i--)
      {
         Swap(A[0],A[i]);
         Heapify(A,i,0);
      }
   }   
void main()
   {
      int A[max], n;
      clrscr();
      cout<<"Nhap so phan tu:";
      cin>>n;
      NhapMang(A,n);
      cout<<"\nMang vua nhap la:";
      XuatMang(A,n);
      cout<<"\nSap xep theo Heap Sort:";
      HeapSort(A,n);
      XuatMang(A,n);
      getch();
}
http://tin4a2uneti.tk

Thích

Báo xấu [0]

Gửi một bình luận lên tường nhà kienhl

Về Đầu TrangThông điệp [Trang 1 trong tổng số 1 trang]

« Xem bài trước | Xem bài kế tiếp »

Bài viết mới cùng chuyên mục

    Bài viết liên quan với Giải thuật heapsort

      Quyền hạn của bạn:

      Bạn không có quyền trả lời bài viết