Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- using namespace std;
- void nhap(int a[], int n){
- for(int i = 0; i<n; i++){
- cout<<"a["<<i<<"]= ";cin>>a[i];
- }
- }
- void xuat(int a[], int n){
- for(int i = 0; i<n; i++){
- cout<<a[i]<<"\t";
- }
- }
- void doicho(int &x, int &y){
- int temp;
- temp = x; x = y; y = temp;
- }
- void shift(int a[], int l, int r){
- //Ham hieu chinh day a[l] -> a[r] thanh heap
- int x, i, j;
- i = l; j = 2*i+1; x = a[i];
- while(j<=r){
- if(j < r)
- if(a[j] < a[j+1])
- j++;
- if(a[j]<=x) return;
- else{
- a[i] = a[j];
- a[j] = x;
- i = j;
- j = 2*i+1;
- x=a[i];
- }
- }
- }
- void createHeap(int a[], int n){
- //ham tao heap
- int l;
- l = n/2-1;
- while(l>=0){
- shift(a,l,n-1);
- l=l-1;
- }
- }
- void heapSort(int a[],int n){
- //Thuat toan heapSort
- int r;
- createHeap(a,n);
- r = n-1;
- while(r>0){
- doicho(a[0], a[r]);
- r--;
- if(r>0) shift(a,0,r);
- }
- }
- int main(){
- int a[20],n;
- cout<<"Nhap so phan tu n cua day: ";cin>>n;
- cout<<"Nhap gia tri cho tung phan tu cua day: "<<endl; nhap(a, n);
- cout<<"Day vua nhap: "<<endl; xuat(a, n);
- cout<<endl<<endl;
- heapSort(a, n);
- cout<<"Day da xep tang: "<<endl; xuat(a, n);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment