Sắp xếp theo kiểu : Heap Sort

Chia sẻ: Đặng Quang Hưng | Ngày: | Loại File: DOC | Số trang:16

0
310
lượt xem
68
download

Sắp xếp theo kiểu : Heap Sort

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nếu ta đánh số các node theo thứ tự từ trên xuống và từ trái qua . Bắt đầu là node root = 0 , thì ta có thể định nghĩa heap thông qua mảng một chiều , có đặc điểm là phần tử thứ k sẽ lớn hơn các phần tử thứ 2k+1 và 2k+2 . Ta có thể dễ nhận thấy là phàn tử thứ 0 sẽ tương ứng với root trong cây ở cách biểu diễn thứ 1

Chủ đề:
Lưu

Nội dung Text: Sắp xếp theo kiểu : Heap Sort

  1. Heap là một cấu trúc dữ liệu , có thể được biểu diễn thông qua 2 cách : -Dạng thứ 1: Dạng cây nhị phân có đặc điểm là node cha thì lớn hơn 2 node con trực tiếp của nó . -Dạng thứ 2: nếu ta đánh số các node theo thứ tự từ trên xuống và từ trái qua . Bắt đầu là node root = 0 , thì ta có thể định nghĩa heap thông qua mảng một chiều , có đặc điểm là phần tử thứ k sẽ lớn hơn các phần tử thứ 2k+1 và 2k+2 . Ta có thể dễ nhận thấy là phàn tử thứ 0 sẽ tương ứng với root trong cây ở cách biểu diễn thứ 1 Nguyên tắc sắp xếp của heap sort Dựa vào tính chất của heap trong cách biểu diễn thứ 1 và thứ 2 , ta có thể thấy phần tử đầu tiên trong cách biểu diễn theo mảng sẽ là phần tử lớn nhất ---> cách sắp xếp đơn giản là : ( Gọi mảng ban đầu là A ) Khởi tạo : Tạo heap từ mảng ban đầu đã cho (mảng A ) 1. Lấy phần tử đầu tiên trong mảng ra bỏ vào mảng kết quả 2. Tạo lại heap từ mảng A 3.Quay lại bước 1 VD : Ta lấy một mảng đã được tạo thành một heap : yrpdfbkac Lấy phần tử đầu tiên là y bỏ vào mảng kết quả C = { y } khi này A = r p d f b k a c Tạo heap A = r f p d c b k a Lấy phần tử đầu tiên ra là r bỏ vào mảng C = { r y } Khi này A = { f p d c b k a } Tạo heap cho A = { p f k d c b a} Lấy phần tử đầu tiên ra là p bỏ vào mảng C = { p r y } Khi này A = { f k d c b a } Tạo heap cho A = { k f b d c a} Lấy phần tử đầu tiên ra là k bỏ vào mảng C = { k p r y } Khi này A = { f b d c a } Tạo heap cho A = { f d b a c} Lấy phần tử đầu tiên ra là f bỏ vào mảng C = { f k p r y } Khi này A = { b d c a } Tạo heap cho A = { d c b a} Lấy phần tử đầu tiên ra là d bỏ vào mảng C = {d f k p r y } Khi này A = { c b a } Tạo heap cho A = { c a b } Lấy phần tử đầu tiên ra là c bỏ vào mảng C = {c d f k p r y }
  2. Khi này A = { b a } Tạo heap cho A = { b a } Lấy phần tử đầu tiên ra là b bỏ vào mảng C = {b c d f k p r y } Khi này A = { a } Tạo heap cho A = { a } Kết thúc ta có được mảng C đã có thứ tự . Cải tiến: Ta có thể hạn chế việc sử dụng thêm mảng C bằng cách tận dụng luôn mảng A ban đầu . Ta làm như sau A=yrpdfbkac Bước 1 : Lấy y ra Lấy c ra Bỏ y vào chổ của c . Bỏ c vào chỗ của y Khi ta bỏ y vào chỗ của c thì giống như ta bỏ y vảo mảng C . Khi này mảng A sẽ coi như gồm 2 phần A = c r p d f b k a ---- y Bước 2 : tạo heap cho phần đứng trước của A là c r p d f b k a Phần sau là chứa y để nguyên Ta sẽ có A mới là : r f p d c b k a -- y Quay lại bước 1 : Lấy r , a ra và swap r và a A sẽ thành A= a f p d c b k -- r y Tạo heap cho A = p f k d c b a -- r y ........... Làm tương tự đến khi kết thúc Qua VD ta thấy rằng phần quan trọng nhất là làm sao sinh ra heap từ một mảng cho trước Sau đây là phần code cho phần cải tiến Giải thuật Post Condition : Dùng để phục hồi lại heap . Pre Condition : Ta sẽ có A mới là : r f p d c b k a -- y Quay lại bước 1 : Lấy r , a ra và swap r và a A sẽ thành A= a f p d c b k -- r y Tạo heap cho A = p f k d c b a -- r y Thì khi này current chính là a
  3. low là 0 high là 7 CODE void Sortable_List::insert_heap(const Record ¤t, int low , int high ) { int large; large = 2*low+1; while ( large = entry[large] ) { break; } else { entry[low] = entry[large]; low = large; large = 2 * low + 1; } } entry[low] = current; } Tạo ra heap lúc ban đầu , lúc chưa chạy giải thuật void Sortable_List::bulidheap() { int low; for ( low = count / 2- 1; low >= 0; low -- ) { Record current = entry[low]; insert_heap(current, low, count -1); } } void Sortable_List::heapsort () { Record current; int last_unsorted; buildheap(); for ( last_unsorted = count -1; last_unsorted > 0; last_unsorted -- ) { current = entry[ last_unsorted]; entry[last_unsorted] = entry[0]; insert_heap(current,0,last_unsorted-1);
  4. } }
  5. mình đã làm xong phần Heap Sort nhưng có 1 chút rắc rối với phần tử đầu tiên a[0], vì nếu áp dụng công thức các phần tử liên đới thì với i=0 -> 2*i=0 và 2*1+1=1 !!! đáng lẻ ra phải là a[0],a[1],a[2] mới đúng. Do đó nó kô đụng chạm gì đến a[0] hết. Các bác có cao kiến gì kô : void heapSort(int a[],int n) { int end=n; MakeHeap(a,n); while (end > 0) { hoanvi(&a[end],&a[1]); ADHeap(a, 1, end-1); end--; } } void MakeHeap(int a[],int n) { int i=n/2; for(i;i>0;i--) ADHeap(a, i, n); } void ADHeap(int a[],int i,int n) { int j; while(i*2
  6. { int x,i,j; i=l; x=a[i]; j=2*i; while(j
  7. } } void xuatmang(int a[], int n) { int i; printf("/n xuat mang"); for(i=0;i0) { hoanvi(a[0],a[r]); r=r-1; createheap(a,r); } xuatmang(a,n); getch(); } ****************** #include #include void xuat(int*a,int n) { int i; printf("\n"); for(i=0;i
  8. int tam; tam=*a; *a=*b; *b=tam; } void heapsort(int*a,int n) { int i,j,tam; i=n/2; while(i>=0) { if(a[i]
  9. Heap là một cấu trúc dữ liệu , có thể được biểu diễn thông qua 2 cách : -Dạng thứ 1: Dạng cây nhị phân có đặc điểm là node cha thì lớn hơn 2 node con trực tiếp của nó . -Dạng thứ 2: nếu ta đánh số các node theo thứ tự từ trên xuống và từ trái qua . Bắt đầu là node root = 0 , thì ta có thể định nghĩa heap thông qua mảng một chiều , có đặc điểm là phần tử thứ k sẽ lớn hơn các phần tử thứ 2k+1 và 2k+2 . Ta có thể dễ nhận thấy là phàn tử thứ 0 sẽ tương ứng với root trong cây ở cách biểu diễn thứ 1 Nguyên tắc sắp xếp của heap sort Dựa vào tính chất của heap trong cách biểu diễn thứ 1 và thứ 2 , ta có thể thấy phần tử đầu tiên trong cách biểu diễn theo mảng sẽ là phần tử lớn nhất ---> cách sắp xếp đơn giản là : ( Gọi mảng ban đầu là A ) Khởi tạo : Tạo heap từ mảng ban đầu đã cho (mảng A ) 1. Lấy phần tử đầu tiên trong mảng ra bỏ vào mảng kết quả 2. Tạo lại heap từ mảng A 3.Quay lại bước 1 VD : Ta lấy một mảng đã được tạo thành một heap : yrpdfbkac Lấy phần tử đầu tiên là y bỏ vào mảng kết quả C = { y } khi này A = r p d f b k a c Tạo heap A = r f p d c b k a Lấy phần tử đầu tiên ra là r bỏ vào mảng C = { r y } Khi này A = { f p d c b k a } Tạo heap cho A = { p f k d c b a} Lấy phần tử đầu tiên ra là p bỏ vào mảng C = { p r y } Khi này A = { f k d c b a } Tạo heap cho A = { k f b d c a} Lấy phần tử đầu tiên ra là k bỏ vào mảng C = { k p r y } Khi này A = { f b d c a } Tạo heap cho A = { f d b a c} Lấy phần tử đầu tiên ra là f bỏ vào mảng C = { f k p r y } Khi này A = { b d c a } Tạo heap cho A = { d c b a} Lấy phần tử đầu tiên ra là d bỏ vào mảng C = {d f k p r y } Khi này A = { c b a } Tạo heap cho A = { c a b } Lấy phần tử đầu tiên ra là c bỏ vào mảng C = {c d f k p r y }
  10. Khi này A = { b a } Tạo heap cho A = { b a } Lấy phần tử đầu tiên ra là b bỏ vào mảng C = {b c d f k p r y } Khi này A = { a } Tạo heap cho A = { a } Kết thúc ta có được mảng C đã có thứ tự . Cải tiến: Ta có thể hạn chế việc sử dụng thêm mảng C bằng cách tận dụng luôn mảng A ban đầu . Ta làm như sau A=yrpdfbkac Bước 1 : Lấy y ra Lấy c ra Bỏ y vào chổ của c . Bỏ c vào chỗ của y Khi ta bỏ y vào chỗ của c thì giống như ta bỏ y vảo mảng C . Khi này mảng A sẽ coi như gồm 2 phần A = c r p d f b k a ---- y Bước 2 : tạo heap cho phần đứng trước của A là c r p d f b k a Phần sau là chứa y để nguyên Ta sẽ có A mới là : r f p d c b k a -- y Quay lại bước 1 : Lấy r , a ra và swap r và a A sẽ thành A= a f p d c b k -- r y Tạo heap cho A = p f k d c b a -- r y ........... Làm tương tự đến khi kết thúc Qua VD ta thấy rằng phần quan trọng nhất là làm sao sinh ra heap từ một mảng cho trước Sau đây là phần code cho phần cải tiến Giải thuật Post Condition : Dùng để phục hồi lại heap . Pre Condition : Ta sẽ có A mới là : r f p d c b k a -- y Quay lại bước 1 : Lấy r , a ra và swap r và a A sẽ thành A= a f p d c b k -- r y Tạo heap cho A = p f k d c b a -- r y Thì khi này current chính là a
  11. low là 0 high là 7 void Sortable_List::insert_heap(const Record ¤t, int low , int high ) { int large ; large = 2*low+1 ; while ( large = entry[large] ) { break ; } else { entry[low] = entry[large] ; low = large ; large = 2 * low + 1 ; } } entry[low] = current ; } Tạo ra heap lúc ban đầu , lúc chưa chạy giải thuật void Sortable_List::bulidheap() { int low ; for ( low = count / 2- 1; low >= 0 ; low -- ) { Record current = entry[low] ; insert_heap(current, low, count -1) ; } } void Sortable_List::heapsort () { Record current ; int last_unsorted ; buildheap() ; for ( last_unsorted = count -1 ; last_unsorted > 0 ; last_unsorted -- ) { current = entry[ last_unsorted] ; entry[last_unsorted] = entry[0] ; insert_heap(current,0,last_unsorted-1) ; } }
  12. include #include #include #define maxn 10 #define Hoanvi(a,b,c) {c=a;a=b;b=c;} #define fi "Heap_sort.inp" FILE *f; void Input(int *n,int *a) { //Tu nhap theo y minh } void Output(int n,int *a) { for (int i=0;i
  13. } } void Heap_sort(int n,int *a) { int right=n-1; int tam; int dem=0; puts("Cac buoc chay cua chuong trinh: "); Create_heap(n-1,a); while (right>0) { Hoanvi(a[0],a[right],tam); ++dem; --right; printf("Buoc %d:",dem); Output(n,a); Adjust(0,right,a); } } void main() { int n; int a[maxn]={0}; Input(&n,a); Heap_sort(n,a); getch(); }
  14. #include #include #include #include //#define max 10; void taomang(int *a,int n) { srand(time(NULL)); for(int i=0;i
  15. { hoanvi(&a[i],&a[2*i+1]); j=2*i+1; } } else { if(a[i]
  16. heapsort(a,i); xuat(a,n); getch(); } mình thấy rằng 1,2,3,4,5,6,7,8,9(vị trí) lúc này 4 so sánh với 8 và 9, 3 so sánh với 6 và 7, 2 so sánh với 4 và 5, 1 so sánh với 2 và 3 thấy rằng việc so sánh các phần tử liên đới sau không trùng với các phần tử liên đới trước vì thế 0,1,2,3,4,5,6,7,8,9 lúc này 4 so sánh với 8 và 9, 3 so sánh với 6 và 7, 2 so sánh với 4 và 5, 1 so sánh với 2 và 3, 0 so sánh với 1 thế là đủ rồi các bạn xem thử nha sớm có ý kiến để thi thực hành chứ.
Đồng bộ tài khoản