Sắp xếp vung đống (Heapsort) & Một số ứng dụng

THONGKE.TXT ghi dãy gồm n (n>106) số thực khác nhau . Kết quả: Với mỗi giá trị k (k ≤ 1000 ) cần đưa ra danh sách k số nhỏ nhất trong dãy số cho trong file THONGKE.TXT theo thứ tự giảm dần. Lập trình: Thuật toán sắp xếp vun đống Chương trình giải các bài toán Người hướng dẫn : PGS Nguyễn Đức Nghĩa Bộ môn Khoa học Máy tính , Khoa Công nghệ Thông tin, ĐHBK Hà Nội Phần I - Sắp xếp kiểu vun đống (Heapsort) 1.Đống : Đống là một cây nhị phân hoàn chỉnh đặc biệt mà giá trị lưu trữ tại mọi nút nhánh đều lớn hơn hay bằng giá trị lưu trong hai nút con của nó . 2. Vun đống Sắp xếp kiểu vun đống chia làm hai giai đoạn : Một dãy khoá k1,k2,…,kn biểu diễn của một cây nhị phân hoàn chỉnh mà ki là giả trị lưu trong nút thứ i, nút con của , nút con của nút thứ i là nút 2i và nút 2i+1, nút cha của nút thứ j là nút j div 2. Đầu tiên cây nhị phân biểu diễn bảng khoá được biến đổi sắp xếp lại dãy khoá đã cho để nó biẻu diễn một đống . Như vậy khoá ở nút gốc của đống chính là khoá lớn nhất (khoá trội) so với mọi khoá trên cây. Giai đoạn hai: là giai đoạn sắp xếp , nhiều lượt xử lý được thực hiện , mỗi lượt ứng với hai phép : - Đưa khoá trội về vị trí thực của nó bằng cách đổi chỗ cho khoá hiện đang ở vị trí đó - “Vun lại thành đống” đối với cây gồm các khoá còn lại (sau khi đã loại khoá trội ra ngoài). 3.Giải thuật: Một nút lá có thể được coi là một cây con đã thoả mãn tính chất của đống rồi .Như vậy tạo nên tạo đống hay vun đống có thể tiến hành theo kiểu từ đáy lên (botom-up) và bài toán này sẽ được quy về một phép xử lý chung như sau: chuyển đổi thành đống cho một cây mà con trái và con phải đã là đống rồi .Do đó ta cần xây dung thủ tục ADJUST nhằm thực hiện công việc này . Đối với cây nhị phân hoàn chỉnh có n nút thì nút ứng với chỉ số từ [n/2] trở xuống mới trở thành cha của nút khác nên khi tạo đống ADJUST chỉ áp đặt với nút vào với các cây mà gốc mà gốc của nó ứng với chỉ số [n/2] , [n/2] -1, …, 1.Còn vơI vun đống thì lại đơn giản hơn . thủ tục ADJUST luôn luôn áp đặt vào cây mà gốc của nó bao giờ cũng là nút đầu tiên (ứng với chỉ số 1).Vì vậy ta cần đến hai thủ tục : thủ tục ADJUST và thủ tục HEAPSORT . ADJUST coi như một chương trình con được gọi tới trong HEAPSORT. Procedure ADJUST(i,n) {giải thuật toán này thực hiện việc chỉnh lý một cây nhị phân gốc i để nó thoả mãn được điều kiện của đống .Cây con trái và cây con phải của i , nghĩa là cây với gốc 2i và 2i+1 , đã thoả mãn điều kiện của đống rồi . Không có nút nào ứng với chỉ số lớn hơn n cả} 1.{Khởi đầu } KEY := K[i] ; j := 2*i; 2.{Chọn con ứng với khoá lớn nhất trong hai con của i } While j <= n do Begin If j<n and K[j] < K[j+1] then j := j+1 ; 3. {So sánh khoá cha với khoá con lớn nhất } If KEY < K[j] then Begin K[lj/2l] := KEY ; Return End;{Khoá cha lớn hơn } K[lj/2l] := K[j] ; j := 2*j ; {Chuyển k lên trên và đi xuống } End; 4. {Đưa KEY vào vị trí của nó } K[lj/2l] := KEY; 5.return Procedure HEAPSORT(K ,n) {Tạo dống ban đầu } for i := |n/2| down to 1 do call ADJUST(1,n) {Sắp xếp } for i := n-1 down to 1 do Begin X := K[i] ; K[i] := K[i + 1] ; K[i+1] := X ; Call ADJUST(1,i) End 3.return phần ii – Một số ứng dụng 1.Các ứng dụng a) Bài toán 1: Xác định xem có bao nhiêu giá trị khác nhau trong mảng gồm n số nguyên dương . Dữ liệu: File văn bản có tên DAYSO.TXT ghi n(n> 105 ) số nguyên . Kết quả: Đưa ra số lượng các giá trị khác nhau trong file đã cho và các giá trị tương ứng theo thứ tự giảm dần. b)Bài toán 2: Tìm k phần tử nhỏ nhất của một danh sách gồm n phần tử : Dữ liệu: File văn bản có tên THONGKE.TXT ghi dãy gồm n (n>106) số thực khác nhau . Kết quả: Với mỗi giá trị k (k ≤ 1000 ) cần đưa ra danh sách k số nhỏ nhất trong dãy số cho trong file THONGKE.TXT theo thứ tự giảm dần. Nếu có một cây nhị phân hoàn chỉnh đầy đủ , ta co thể dễ dàng đánh số trên cây đó theo thứ tự lần lượt từ mức 1 trở lên , hết mức này sang mức khác từ trái qua phải đối với các nút ở mỗi mức .Con của nút thứ i là các nút thứ 2i và 2i+1 hoặc cha của nút thứ j là | j/2| . Với việc yêu cầu dùng phương pháp sắp xếp này , bảng khoá sẽ có cấu trúc cây nhị phân hoàn chỉnh và lưu trữ kế tiếp trong máy. Cài đặt thuật toán sắp xếp vun đống để áp dụng trên chương trình giải hai bài toán nói trên trên môi trường Turbo C++ 6.0. Vì vậy mà nó đóng vai trò là một thủ tục được gọi trong các chương trình giải hai bài toán . 2.Bài toán 1: Dữ liệu đầu vào của bài toán là một file văn bản ghi n số nguyên có tên DAYSO.TXT , do đó ta viết một thủ tục con Tao_file_so dùng thủ tục rand() để nhập các số nguyên . Sau khi tạo file văn bản chứa n số nguyên , tiếp đó tiến hành đọc file sau đó cài đặt thủ tục sắp xếp vun đống để sắp xếp và dùng thủ tục chuyển .Nhờ đó ta có thể tiến hành so sánh các số và đưa ra số lượng các giá trị khác nhau , đồng thời khi số lượng thay đổi thì cũng đưa ra giá trị số tương ứng .Cuối cùng , đưa ra số lượng các giá trị khác nhau và các giá trị đó từ file DAYSO.TXT nói trên theo thứ tự giảm dần. 3.Bài toán 2: Với bài toán này , dữ liệu đầu vào có tên là THONGKE.TXT cũng là một file văn bản gồm n phần tử số thực khác nhau .Tương tự với bài toán trên, ta cũng viết một thủ tục TAO_FILE_SO bằng thủ tục rand() . Nhưng với bài toán này , ta phải nhập thêm giá trị k (k<=1000) để nhằm đưa ra k giá trị nhỏ nhất theo thứ tự giảm dần từ file THONGKE.TXT nói trên. Thứ tự thủ tục Heapsort và thủ tục Chuyen có thay đổi nhằm giảm thời gian chạy chương trình khi kích thước file chứa số lớn. Phần Iii – Thực nghiệm Bài toán 1 : Trước khi sắp xếp : Ten file can tao la: DAYSO.TXT Day la so thu 1 : 41 Day la so thu 2 : 18467 Day la so thu 3 : 6334 Day la so thu 4 : 26500 Day la so thu 5 : 19169 Day la so thu 6 : 15724 Day la so thu 7 : 11478 Day la so thu 8 : 29358 Day la so thu 9 : 26962 Day la so thu 10 : 24464 So cac gia tri khac nhau la :10 Cac so khac nhau theo thu tu giam dan la: Gia tri a[10] : 29358 Gia tri a[9] : 26962 Gia tri a[8] : 26500 Gia tri a[7] : 24464 Gia tri a[6] : 19169 Gia tri a[5] : 18467 Gia tri a[4] : 15724 Gia tri a[3] : 11478 Gia tri a[2] : 6334 Gia tri a[1] : 41 Co muon chay lai chuong trinh nay khong ? An N hoac n de thoat Bài toán 2: Ten file can tao la :THONGKE.TXT Hay doc so K 10 10 so nho nhat khac nhau theo thu tu giam dan la: Gia tri a[10] : 2995 Gia tri a[9] : 2082 Gia tri a[8] : 1869 Gia tri a[7] : 1842 Gia tri a[6] : 778 Gia tri a[5] : 491 Gia tri a[4] : 292 Gia tri a[3] : 288 Gia tri a[2] : 153 Gia tri a[1] : 41 Co muon chay lai chuong trinh nay khong? An Y hoac y de thoat Phần VI – Listing chương trình nguồn Thuật toán sắp xếp vun đống void adjust(long i, long n) { long j, key; key= b[i]; j=2*i; while (j<=n) { if ((j<n)&&(b[j]<b[j+1])) j=j+1; if (key >b[j]) { b[long(floor(j/2))] =key; break; } b[long(floor(j/2))]=b[j]; j=j*2; } b[long(floor(j/2))] = key; } //------------------------------------------------------- void Heap_sort() { long i,x; for(i=long(floor(n/2));i>=1;--i) adjust(i,n); for(i=n-1;i>=1;--i) { x=b[1];b[1]=b[i+1];b[i+1]=x; adjust(1,i); } 2.Bài toán 1 #include #include #include #include const max=100, max1=3, max2=10; int a[max],b[max],d[max],n; enum boolean{F,T}; boolean c[max]; char filename[20]; void adjust(int i, int n); void Heap_sort(); void Tao_file_so(); void chuyen(); void Doc_file(); void main() { int i; char ch='y'; while ((ch!='n')&&(ch!='N')) {Tao_file_so(); Doc_file(); for(i=1;i<=max2;i++) cout<<"Day la so thu"<<i<<": "<<b[i]<<endl; chuyen(); Heap_sort(); cout<<" So cac gia tri khac nhau la: "<<n<<endl; cout<<"Cac so khac nhau theo thu tu giam dan la:"<<endl; for(i=n;i>=1;--i) cout<<"Gia tri a["<<i<<"] : "<<a[i]<<endl; cout<<" Co muon chay lai chuong trinh nay khong? An N hoac n de thoat"; cin>>ch; } } //-------------------------------------------------------- void Tao_file_so() { int i; double k; cout>filename; ofstream fout(filename); for(i=1;i<= max2;i++) { k=rand(); fout<<k<<endl; } fout.close(); } //-------------------------------------------------------- //------------------------------------------------------- void Doc_file() { int k,i; ifstream fin(filename); for(i=1;i<=max2;i++) { fin>>k; b[i]=k; } fin.close(); } //--------------------------------------------------------------------- void chuyen() { int i,j,k=1,m=0; for(i=1;i<=max2;i++) c[i]=T; for(i=1;i<=max2;i++) for(j=1;j<=max2;j++) { if((i!=j)&&(b[i]==b[j])&&c[i]) { c[j]= F; k=k+1;// Tan so lap cua tung so trong day } if ((j==max2)&&c[i]) { m=m+1;// so ca gia tri khac nhau a[m]=b[i]; d[m]=k; k=1; } } n=m; } //------------------------------------------------------- void Heap_sort() { int i,x; for(i=int(floor(n/2));i>=1;--i) adjust(i,n); for(i=n-1;i>=1;--i) { x=a[1];a[1]=a[i+1];a[i+1]=x; adjust(1,i); } } //---------------------------------------------------------- void adjust(int i, int n) { int j, key; key= a[i]; j=2*i; while (j<=n) { if ((j<n)&&(a[j]<a[j+1])) j=j+1; if (key >a[j]) { a[int(floor(j/2))] =key; break; } a[int(floor(j/2))]=a[j]; j=j*2; } a[int(floor(j/2))] = key; } 3.Bài toán 2 #include #include #include #include const max=100, max2=100; int a[max],b[max],d[max]; long n; enum boolean{F,T}; boolean c[max]; char filename[20]; void adjust(long i, long n); void Heap_sort(); void Tao_file_so(); void chuyen(); void Doc_file(); void main() { long i,k; char ch='n'; while ((ch!='y')&&(ch!='Y')) { Tao_file_so(); Doc_file(); n=max2; Heap_sort(); chuyen(); cout>k; if (k<=n) { cout<<k<<" so nho nhat khac nhau theo thu tu giam dan la:"<<endl; for(i=k;i>=1;--i) cout<<"Gia tri a["<<i<<"] : "<<a[i]<<endl; } cout<<" Co muon chay lai chuong trinh nay khong? An Y hoac y de thoat "; cin>>ch; } } //-------------------------------------------------------- void Tao_file_so() { long i; int k; cout>filename; ofstream fout(filename); for(i=1;i<= max2;i++) { k=rand(); fout<<k<<" "; } fout.close(); } //-------------------------------------------------------- //------------------------------------------------------- void Doc_file() { long k,i; ifstream fin(filename); for(i=1;i<=max2;i++) { fin>>k; b[i]=k; } fin.close(); } //--------------------------------------------------------------------- void chuyen() { long i=1,j=2,k=1,m=0; while (j<=max2+1) { do { if ((b[i]==b[j])&&(j<=max2)) { j=j+1; k=k+1; }; }while ((b[j]==b[i])&&(j<=max2)); m=m+1; i=j; j=i+1; a[m]=b[i-1]; } n=m; } //------------------------------------------------------- void Heap_sort() { long i,x; for(i=long(floor(n/2));i>=1;--i) adjust(i,n); for(i=n-1;i>=1;--i) { x=b[1];b[1]=b[i+1];b[i+1]=x; adjust(1,i); } } //---------------------------------------------------------- void adjust(long i, long n) { long j, key; key= b[i]; j=2*i; while (j<=n) { if ((j<n)&&(b[j]<b[j+1])) j=j+1; if (key >b[j]) { b[long(floor(j/2))] =key; break; } b[long(floor(j/2))]=b[j]; j=j*2; } b[long(floor(j/2))] = key; } tàI liệu tham khảo 1.Đỗ Xuân Lôi – Cấu trúc dữ liệu và giải thuật . NXB KHKT , 1997. 2.Nguyễn Đức Nghĩa , Nguyễn Tô Thành – Toán rời rạc. NXB Giáo Dục , 1997 mục lục Phần I - Sắp xếp kiểu vun đống (Heapsort)……………………………….2 1.Đống ………………………………………………………………….2 2.Vun đống ……………………………………………………………..2 3.Giải thuật………………………………………………………………2 Phần II – Một số ứng dụng………………………………………………..4 1.Các ứng dụng ………………………………………………………....4 2. Bài toán 1……………………………………………………………..4 3. Bài toán 2……………………………………………………………..4 Phần III – Thực nghiệm …………………………………………………..6 Phần VI – Listing chương trình nguồn……………………………………8 Thuật toán sắp xếp vun đống ………………………………………..8 Chương trình giải bài toán 1………………………………………....8 Chương trình giải bài toán 2………………………………………..11 Phần V – Tài liệu tham khảo…………………………………………….15 ._.