tổng hợp sxep

/*Sap xep tang dan danh sach ke theo giai thuat
  selection sort, bubblesort, quicksort, insertion sort, 
    heapsort, mergesort*/
//Danh sach cai dat bang mang tinh.
#include <stdio.h>
#include <conio.h> 
#include <iostream>
using namespace std;
#define true  1
#define false 0
//================================================== 
void swap(float &x,float &y)
 {float tmp=x;x=y;y=tmp;
 };
//==================================================
//Nhap danh sach.
void nhap(float a[],int &N)
 {cout<<"\nSo phan tu can nhap N = ";cin>>N;
  for(int i=0;i<N;i++)
 { cout<<"a["<<i<<"]= "; cin>>a[i];}
 }
//==================================================
//Hien danh sach tren man hinh.
void xem(float a[],int N)
 {int i;
  cout<<"\nCac phan tu danh sach:";
  for(i=0;i<N;i++) cout<<a[i]<<"  ";
  }
//==================================================
/*Sap xep danh sach theo thu tu tang dan bang phuong phap lua chon don gian.
  Simple Selection Sort*/
void selectsort(float a[],int N)
 {int i,j,k;float min;
  for(i=0;i<N-1;i++)
   {min=a[i];k=i;
    for(j=i+1;j<N;j++)
     if(a[j]<min) {k=j;min=a[j];}
    if(k!=i) swap(a[i],a[k]);
    xem(a,N);
   }
 }
//==================================================
/*Sap xep danh sach theo thu tu tang dan bang phuong phap
 BUBBLE Sort co cai tien:
 Duyet danh sach nhieu lan, moi lan duyet so sanh cap nut i va i+1 va doi cho
 2 nut nay neu chua dung thu tu cho den khi danh sach duoc sap xep hoan toan.
 Tuy nhien ta co the thay rang:
 - Sau lan duyet 1 thi 1 nut la nut thu n-1 duoc dat dung cho (n=n-1+1)
 - Sau lan duyet 2 thi 2 nut la cac nut n-1,n duoc dat dung cho
 - ...
 - Sau lan duyet i-1 thi cac nut tu n-i+2 den n duoc dat dung cho, do do tai
   lan duyet thu i ta chi can duyet cac phan tu 1 den n-i+1.
   O lan duyet thu n-1 thi n-1 nut duoc dat dung cho, tuc la khong can duyet tiep
   Vay ta co the cai tien thuat toan tren.Neu co mot lan duyet nao do ma
   khong co lan duyet nao thi day da duoc sap xep*/
void bubblesort(float a[],int N)
 {int i,j,doicho;
  do
   {doicho=false;
    for(j=0;j<N-1;j++)
     if(a[j]>a[j+1]) 
  {swap(a[j],a[j+1]);
  doicho=true;}
     xem(a,N);
  }
  while(doicho);
 }
//==================================================
/*Sap xep danh sach theo thu tu tang dan bang phuong phap
  Simple Insertion Sort*/
void insertsort(float a[],int N, int h=1)
 {int i,j;int x;
  for(i=h;i<N;i++) //Ban dau day chi co 1 phan tu a[0]
   {x=a[i];//chen a[i] vao day da sx a[0],a[1],...,a[i-1]
    j=i;
    while(j>0 && x<a[j-h])
     {a[j]=a[j-h];//Keo nut lon hon x len h vi tri
     j=j-h;
     };
     /*Chen x vao vi tri hop le, j la vi tri dau tien ma x>=a[j-h]
      do do gia tri j dung la vi tri can chen x */
     a[j]=x;
     xem(a,N);
   } //end of for(i=h;i<N;i++)
 };
//==================================================
/*CAI DAT GIAI THUAT QUICKSORT}
 Thu tuc partition se phan hoach danh sach tu low den up thanh 2 phan:
 cac nut co noi dung <= a[pivot] nam ben trai pivot, cac nut co
 noi dung > a[pivot] nam ben phai.
 Chon nuttruc=a[low], quet 2 dau lai, i tu duoi len, j tu tren xuong,
 va doi cho cac cap phan tu sai cho, khi ket thuc quet thi doi cho a[low]
 va a[j], vay nut truc se chuyen den vi tri j*/
void partition(float a[],int low,int up,int& pivot)
 {int pivotval=a[low];//Chon nut dau lam truc
  int i=low;
  int j=up;
  while(i<j) //Bat dau quet
   {while(a[i]<=pivotval && i<up) i++; //a[i]>pivotval
    while(a[j]>pivotval)  j--;         //a[j]<=pivotval
    if(i<j) swap(a[i],a[j]); //Doi cho cap nut sai vi tri
    };
  /*Sau vong lap ta co i>=j, cac phan tu tu low den j deu <=pivotval
    cac phan tu tu j+1 deu > pivota, thi du
    0  1  2  3  4
    3  7  2  1  6  i=1 j=3 (a[1]=7>pivotval,(a[3]=1<=pivotval)
    3  1  2  7  6  i=3 j=2 (a[3]=7>pivotval,(a[2]=2<=pivotval)
    ta chuyen pivotval den vi tri j de bao dam rang pivotval
    o dung vi tri trong day, tuc la cac phan tu ben trai
    deu nho hon hoac bang, cac phan tu ben phai lon hon*/
   swap(a[low],a[j]);pivot=j;
 }
//==================================================
void quicksort(float a[],int low,int up)
 {int pivot;
  if(low>=up) return;
  partition(a,low,up,pivot);
  quicksort(a,low,pivot-1);
  quicksort(a,pivot+1,up);
  }
//==================================================
/*Sap xep bang HEAP: Heap la cay nhi phan gan day duoc cai dat bang
  mang mot chieu voi cac nut tren heap co noi dung nho hon nut goc
  va cac nhanh cay con cung la cac heap*/
void heapsort(float a[],int N)
 {/*Chuyen danh sach thanh HEAP bang cach xem khoi dau heap gom nut
    a[0], sau do lan luot chuyen cac nut a[1],a[2],...,
    a[N-1] vao heap*/
  int i,s,f;int x;
  for(i=1;i<N;i++)
   {x=a[i];//Nut can them vao HEAP, ban dau heap co mot nut a[0].
    /*Insert x vao vi tri thich hop cua HEAP: xuat phat tu i, di dan ve
     goc de tim mot vi tri nut cha thich hop. Vay f se giam dan*/
     s=i;       //s la nut con, hien tai tren heap chua co a[i]
     //f=(s-1)/2 la nut cha
     while(s>0 && x>a[(s-1)/2])
      {a[s]=a[(s-1)/2]; //Keo nut < x xuong 1 muc
       s=(s-1)/2;
      };
     a[s]=x; //Dien nut x vao vi tri phu hop
    }; //end of for(int i=1;i<N;i++)
 //Ket thuc chuyen danh sach thanh heap

 //Lan luot xoa nut a[0] tren HEAP, dua ve vi tri thich hop tren ds
    for(i=N-1;i>0;i--)
     {x=a[i];a[i]=a[0];
     /*O buoc i heap co i+1 nut, la a[0], a[1],...,a[i]
      Muc dich cua chung ta la dua nut a[0] ve vi tri a[i],
      dong thoi, chen a[i] vao heap sao cho cau truc heap van bao
      toan. De lam dieu nay ta bat dau tu
      nut f = 0, theo con duong cha - con trai hoac phai, tim mot vi tri
      de chen nut a[i]. De co duoc nut trong de chen a[i], ta can
      dich cac nut tren duong di len mot muc, bang cong thuc
      nutgoc=max(contrai,conphai,a[i])*/
      f=0; //f la nut cha, s la nut con lon hon
      s=2*f+1; //Gan s la nut con ben trai
      if(s+1<i && a[s]<a[s+1]) s=s+1;/*Neu co nut phai va
     lon hon thi chon nut phai*/
      while(s<i && x<a[s])
       {a[f]=a[s];//Con lon thay the cha
 f=s;//Chuyen den con lon tiep theo
 s=2*f+1;
 if(s+1<i && a[s]<a[s+1]) s=s+1;
       };
       a[f]=x; //Nut a[k] duoc chen dung cho
     }; //end of for(i=N-1;i>0;i--)
 };
//==================================================
/*Sap xep danh sach theo thu tu tang dan bang phuong phap
 Merge Sort.
 Input:  Day a[0],a[1],...,a[N-1]
 Tr.gian:Ltemp la danh sach tam dung khi tron, k la chi so cua danh sach nay
  size la kich thuoc cua danh sach con, o buoc 1 size = 1,
  buoc 2 size = 2, buoc 3 size = 4,...
  low1,up1,low2,up2 la can duoi va can tren cua 2 danh sach dang tron
 Output: Danh sach da duoc sap xep*/
void mergesort(float a[],int N)
 {int i,j,k,low1,up1,low2,up2;//Can duoi va tren cua 2 ds con
  int size;
  int *Listtmp=new int[N];
  size=1;//Buoc tron 1: gan size bang 1
  while(size<N)
   {low1=0;k=0;

    while(low1+size<N)
     {low2=low1+size;
      up1=low2-1;
      up2=(low2+size-1<N)? low2+size-1 : N-1;

      /*Cho i quet tu low1 den up1, j quet tu low2 den up2. Voi moi i va j
 so sanh va chon phan tu nho hon chuyen sang danh sach tam.*/
      for(i=low1,j=low2;i<=up1 && j<=up2;k++)
 if(a[i]<=a[j]) Listtmp[k]=a[i++];
  else Listtmp[k]=a[j++];;

      /*Vi so phan tu duoc chon tu 2 ds khong nhu nhau nen co the i hoac
 j se den dich truoc. Trong truong hop nay ta chuyen phan con lai
 cua day chua quet xong sang ds tam*/
      for(; i <= up1; k++) Listtmp[k] = a[i++];
      for(; j <= up2; k++) Listtmp[k] = a[j++];
      low1 = up2+1;
     } //while(low1+size<N)

     /*Neu so ds con la so le thi khi tron tung cap se con lai ds cuoi
      cung. Ta phai chuyen danh sach nay sang ds tam*/
     for(i = low1; k < N; i++) Listtmp[k++] = a[i];
     for(i = 0; i < N; i++) a[i] = Listtmp[i];
     size *= 2;//Tang co cua danh sach con len 2 lan.
   }//end of while(size<N)
}
//==================================================
main()
 {int step[3] = {5,3,1};
  float a[50]; int N,i;int x;
   while(true)
    {  //Tao menu
     cout<<"\n 1. Nhap danh sach";
     cout<<"\n 2. Xem danh sach ";
     cout<<"\n 3. Sap xep tang dan bang SELECTION Sort";
     cout<<"\n 4. Sap xep tang dan bang BUBBLE Sort";
     cout<<"\n 5. Sap xep tang dan bang INSERTION Sort";
     cout<<"\n 6. Sap xep tang dan bang QUICK Sort";
     cout<<"\n 7. Sap xep tang dan bang HEAP Sort";
     cout<<"\n 8. Sap xep tang dan bang MERGE Sort";
     cout<<"\n z. Ket thuc";
     cout<<endl<<"\nHay nhan phim tu 1 -> z de chon: ";
     char chon=toupper(getch());
     if(toupper(chon)=='Z') break;
     switch (chon)
      {case '1':nhap(a,N);break;
       case '2':xem(a,N);break;
       case '3':selectsort(a,N);break;
       case '4':bubblesort(a,N);break;
       case '5':insertsort(a,N);break;
       case '6':quicksort(a,0,N-1);break;
       case '7':heapsort(a,N);break;
       case '8':mergesort(a,N);break;
       }
     cout<<"\n\nNhan phim bat ky de tiep tuc";
     getch();
     }
  }