vietwow

#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
#include<dos.h>

//Khai bao so phan tu & kieu cua no
const Max_Size=100;
float a[100];
int n;

//Tao Menu chon
void menu()
{
   clrscr();
 cout<<"\nHay Chon Chuc Nang:"<<endl;
 cout<<"\n 1.Nhap Du Lieu Bang Tay"<<endl;
 cout<<"\n 2.Su Dung Bo Sinh So Ngau Nhien"<<endl;
 cout<<"\n 3.Tim Kiem Bang PP LinearSeach"<<endl;
 cout<<"\n 4.Tim Kiem Bang PP BinarySearch"<<endl;
 cout<<"\n 5.Sap Xep Bang PP InsertionSort"<<endl;
 cout<<"\n 6.Sap Xep Bang PP SelectionSort"<<endl;
 cout<<"\n 7.Sap Xep Bang PP InterchangeSort"<<endl;
 cout<<"\n 8.Sap Xep Bang PP BubbleSort"<<endl;
 cout<<"\n 9.Sap Xep Bang PP ShakerSort"<<endl;
 cout<<"\n10.Sap Xep Bang PP HeapSort"<<endl;
 cout<<"\n11.Sap Xep Bang PP BInsertionSort"<<endl;
 cout<<"\n12.Sap Xep Bang PP ShellSort"<<endl;
 cout<<"\n13.Sap Xep Bang PP QuickSort"<<endl;
 cout<<"\n14.Sap Xep Bang PP MergeSort"<<endl;
 cout<<"\n15.Sap Xep Bang PP RadixSort"<<endl;
 cout<<"\n16.Giai Thoat"<<endl;
 cout<<"\nChon (1->16): ";
}

//Xac lap vung gioi han chon
int chon_menu()
{
   int ch;
   cin>>ch;
   if ((ch >= 1) && (ch <= 16)) return ch;
   else return -1;
}

//Thuat toan tim kiem tuyen tinh
int LinearSearch(float a[],int n,int x)
{
 int i=1;
 while((i<n)&&(a[i]!=x)) i++;
 if(a[i]==x) return i;
 else return -1;
}

//Thuat toan tim kiem nhi phan
int BinarySearch( float a[], int n, int x)
{
 int l=1,r=n,mid;
 do
  {
   mid=(l+r)/2;
   if(x==a[mid]) return mid;
   else if(x<a[mid]) r=mid-1;
   else l=mid+1;
  }
   while(l<=r);
   return -1;
}

// Thuat toan sap xep chen truc tiep
void InsertionSort(float a[],int n)
{
 float temp;
 for(int i=2;i<=n;i++)
  {
   temp=a[i];
   int vt=i;
   while ((a[vt-1]>temp)&&(vt>1))
    {
     a[vt]=a[vt-1];
     vt=vt-1;
    }
   a[vt]=temp;
  }
}

//Thuat toan sap xep chon truc tiep
void SelectionSort(float a[],int n)
{
 int min,temp;//la chi so phan tu nho nhat
 for(int i=1;i<=n-1;i++)
  {
   //tim phan tu nho nhat ben phai a[i], tu [a[i]+1->a[n]
   min=i+1;
   for(int j=i+2;j<=n;j++)
   if(a[j]<a[min])min=j;
   if(a[min]<a[i])
    {
     temp=a[i];
     a[i]=a[min];
     a[min]=temp;
    }
  }
}

//Thuat toan sap xep doi cho truc tiep
void InterChangeSort(float a[],int n)
{
 int temp;
 for(int i=1;i<n;i++)
 for(int j=i+1;j<=n;j++)
 if(a[i]>a[j])
  {
   temp=a[i];
   a[i]=a[j];
   a[j]=temp;
  }
}

//Thuat toan sap xep bang pp noi bot
void BubbleSort(float a[],int n)
{
 int temp;
 for(int i=1;i<n;i++)
 for(int j=n;j>i;j--)
 if(a[j]<a[j-1])
  {
   temp=a[j];
   a[j]=a[j-1];
   a[j-1]=temp;
  }
}

//Thuat toan sap xep bang pp ShakerSort
void ShakerSort(float a[],int n)
{
 int l=1,r=n,k=n;
 int temp;
 while (l<r)
  {
   for(int j=r;j>l;j--)
   if(a[j]<a[j-1])
    {
     temp=a[j];
     a[j]=a[j-1];
     a[j-1]=temp;
     k=j;
    }
   l=k;
   for(j=l;j<r;j++)
   if(a[j]>a[j+1])
    {
    temp=a[j];
    a[j]=a[j+1];
    a[j+1]=temp;
    k=j;
    }
   r=k;
  }
}

/* Thuat toan sap xep bang pp HeapSort
  1.Chinh Heap */
void ShiftHeap(float a[],int l,int r)
{
 int x,i,j;
 i=l;
 j=2*i;
 x=a[i];
 while(j<=r)
  {
   if(j<r)
   if(a[j]<a[j+1])
   j=j+1;
   if(a[j]<x)break;
   else
    {
     a[i]=a[j];
     a[j]=x;
     i=j;
     j=2*i;
    }
  }
}
// 2.Tao Heap
void CreateHeap(float a[],int n)
{
 int l;
 l=n/2;//a[1] la phan tu ghep them
 while(l>0)
  {
  ShiftHeap(a,l,n);
  l=l-1;
  }
}
// 3.Sap Xep Tren Heap
void HeapSort(float a[],int n)
{
 int temp,r;
 CreateHeap(a,n);
 r=n;// la vi tri dung cho phan tu nho nhat
 while(r>0)
  {
   temp=a[1];
   a[1]=a[r];
   a[r]=temp;
   r=r-1;
   ShiftHeap(a,1,r);
  }
}

//Thuat toan sap xep chen nhi phan
void BInsertionSort(float a[],int n)
{
 int l,r,m;
 int x; //luu gia tri a[i] tranh bi ghi de khi doi cho cac phan tu
 for(int i=2;i<=n;i++)
  {
   x=a[i];
   l=1;
   r=i-1;
   while(i<=r) //tim vi tri can chen
    {
     m=(l+r)/2; //tim vi tri thich hop m
     if(i<m) r=m-1;
     else l=m+1;
    }
   int vt=i;
   while((a[vt-1]>x)&&(vt>1))
    {
     a[vt]=a[vt-1];
     vt=vt-1;
    }
   a[vt]=x;
  }
}

//Thuat toan sap xep bang pp ShellSort
void ShellSort(float a[],int n,int k)
{
 int step,i,j;
 int x;
 for(step=1;step<=k;step++)
  {
    for(i=1;i<=n;i++)
     {
      x=a[i];
      j=i-1;
      while((x<a[j])&&(j>=1))
       {
    a[j+1]=a[j];
    j=j-1;
       }
      a[j+1]=x;
     }
   }
}

//Thuat toan sap xep bang pp QuickSort
void QuickSort(float a[],int l,int r)
{
 int i,j;
 int x;
 i=l;
 j=r;
 x=a[(l+r)/2];
 do
  {
   while (a[i]<x)i++;
   while(a[j]>x)j--;
   if(j<=j)
    {
     if(i<j)
      {
       int temp=a[i];
       a[i]=a[j];
       a[j]=temp;
      }
   i++;
   j--;
     }
   }
   while(i<j);
   if(l<j)QuickSort(a,l,j);
   if(i<r)QuickSort(a,i,r);
}

//Tao Merge
void Merge(float a[],int first,int mid,int last)
{
 int first1=first;
 int last1=mid;
 int first2=mid+1;
 int last2=last;
 int i=first1;
 int temp[Max_Size];
 for(i=first1;first1<=last1&&first2<=last2;i++)
   {
    if(a[first1]<a[first2])
     {
      temp[i]=a[first1];
      first1++;
     }
    else
     {
      temp[i]=a[first2];
      first2++;
     }
   }
 for(;first1<=last1;first1++,i++) temp[i]=a[first1];
 for(;first2<=last2;first2++,i++) temp[i]=a[first2];
 for(i=first;i<=last;i++) a[i]=temp[i];
}

// Sap Merge
void MergeSort(float a[],int first,int last)
{
 if(first<last)
  {
   int mid=(first+last)/2;
   MergeSort(a,first,mid);
   MergeSort(a,mid+1,last);
   Merge(a,first,mid,last);
  }
}

//Tao lo cho tung phan tu cua day
int GetDigit(unsigned long n,int k)
{
 switch(k)
 {
  case 0: return (n%10);
  case 1: return ((n/10)%10);
  case 2: return ((n/100)%10);
  case 3: return ((n/1000)%10);
  case 4: return ((n/10000)%10);
  case 5: return ((n/100000)%10);
  case 6: return ((n/1000000)%10);
  case 7: return ((n/10000000)%10);
  case 8: return ((n/100000000)%10);
  case 9: return ((n/1000000000)%10);
 }
 return n; //Tra ve gia tri neu khong thuoc lo nao
}

//Tron lo & Sap lai lo thanh day moi
void RadixSort(float a[],int n,int m)
{
 int j=1,k=0;
 int temp[Max_Size];
 do
  {
   for(int lo=0;lo<=9;lo++) //lo duoc don tu 0->9
   for(int i=1;i<=n;i++) // so phan tu duoc quet lai toan bo theo lo
    {
     int n=GetDigit(a[i],k);
     if(lo==n)
      {
       temp[j]=a[i];
       j++;
      }
    }
   j=1;
   for(int i=1;i<=n;i++) a[i]=temp[i];
   k=k+1;
  }
 while(k<=m);
}

//Am thanh bao khoi dong chuong trinh
void Volume()
{
 sound(1800);
 delay(300);
 sound(200);
 delay(150);
 sound(800);
 delay(100);
 sound(600);
 delay(300);
 sound(500);
 delay(250);
 nosound();
}

//Thu tuc vao phan tu mang
void input(float a[],int n)
{
 int i;
 for (i = 1; i <= n; i++)
  {
   cout<<"a["<<i<<"]= ";
   cin>>a[i];
  }
}

// Thu tuc in ra phan tu mang
void output(float a[],int n)
{
  int i;
  for (i = 1; i <= n; i++)
      cout<<a[i]<<"  ";
}

//Chuong trinh chinh
void main()
{
 int x,vt;
 int chon;
 clrscr();//Xoa khong cho hien thi text chon  chuc nang thu 16
 Volume(); // Goi am thanh
 textcolor(10); //Tao mau chu
 cout<<endl<<"\nChuong Trinh Sap Xep Theo Cac Thuat Toan & Tim Kiem Tung Phan Tu";
 cout<<endl<<endl;
 cout<<"Chuong trinh dang chay"; delay(500);
 sound(1000);
 delay(150);
 nosound();
 cout<<"."; delay(500); sound(1000); delay(100); nosound();
 cout<<"."; delay(500); sound(1000); delay(100); nosound();
 cout<<"."; delay(500); sound(1000); delay(100); nosound();
 cout<<"."; delay(500); sound(1000); delay(100); nosound();
 cout<<"."; delay(500); sound(1000); delay(100); nosound();
 cout<<"."; delay(500); sound(1000); delay(100); nosound();
 cout<<"."; delay(500); sound(1000); delay(100); nosound();
 cout<<"."; delay(500); sound(1500); delay(350); nosound();
 cout<<"OK"; delay(500);
 do
  {
   menu();
   chon = chon_menu();
   switch(chon)
    {
     case 1: clrscr();
          sound(350);
          delay(150);
          nosound();
          cout<<"Hay nhap vao so phan tu (1->20): ";
          cin>>n;
          cout<<endl;
          if((n>0)&&(n<=20))
          {
          input(a,n);
          cout<<"\nDay vua nhap la: ";
          output(a,n);
          }
          else cout<<endl<<"Khong hop le !...Quay ve Menu !";
          sound(700);
          delay(150);
          nosound();
          getch();
          break;

      case 2: clrscr();
          sound(350);
          delay(150);
          nosound();
          cout<<"Nhap so phan tu can sinh ra (1->20): ";
          cin>>n;
          if((n>0)&&(n<=20))
          {
          cout<<endl<<"Day duoc sinh ra la: ";
          cout<<endl<<endl;
          randomize();
          for(int i=0;i<=n;i++) a[i]=random(1000);
          //So ngau nhien tu 0->1000
          output(a,n);
          }
          else cout<<endl<<"Khong hop le !...Quay ve Menu !";
          sound(700);
          delay(150);
          nosound();
          getch();
          break;

      case 3: clrscr();
          sound(350);
          delay(150);
          nosound();
          if(n>0)
          {
          cout<<"Day ban dau: ";
          output(a,n);
          cout<<endl;
          cout<<"\n---Tim kiem theo PP LinearSearch---";
          cout<<endl;
          cout<<"\nNhap phan tu can tim: ";
          cin>>x;
          clrscr();
          vt = LinearSearch(a,n,x);
          cout<<"Day ban dau: ";
          output(a,n);
          cout<<endl;
          if (vt ==-1) cout<<endl<<"\nKhong co phan tu can tim !";
          else
        {
         cout<<endl<<"Co phan tu can tim !"<<endl;
         cout<<endl<<"La so: "<<x;
         cout<<endl<<"\nTai vi tri thu: "<<vt;
        }
          }
          else cout<<"Chua co gi ?...Quay ve Menu !";
          sound(700);
          delay(150);
          nosound();
          getch();
          break;

      case 4: clrscr();
          sound(350);
          delay(150);
          nosound();
          if(n>0)
          {
          cout<<"Day ban dau: ";
          output(a,n);
          cout<<endl;
          cout<<"\n---Tim kiem theo PP BinarySearch---";
          cout<<endl;
          cout<<"\nNhap phan tu can tim: ";
          cin>>x;
          clrscr();
          cout<<endl;
          vt = BinarySearch(a,n,x);
          cout<<"Day ban dau: ";
          output(a,n);
          cout<<endl;
          if (vt == -1) cout<<endl<<"\nKhong co phan tu can tim !";
          else
           {
         cout<<endl<<"Co phan tu can tim !"<<endl;
         cout<<endl<<"La so: "<<x;
         cout<<endl<<"\nTai vi tri thu: "<<vt;
        }
          }
          else cout<<"Chua co gi ?...Quay ve Menu !";
          sound(700);
          delay(150);
          nosound();
          getch();
          break;

      case 5: clrscr();
          if(n>0)
          {
          cout<<"Day ban dau: ";
          output(a,n);
          cout<<endl;
          cout<<"\nSap xep theo PP InsertionSort:"<<endl;
          cout<<endl;
          InsertionSort(a,n);
          output(a,n);
          }
          else cout<<"Chua co gi ?...Quay ve Menu !";
          sound(700);
          delay(150);
          nosound();
          getch();
          break;

      case 6: clrscr();
          if(n>0)
          {
          cout<<"Day ban dau: ";
          output(a,n);
          cout<<endl;
          cout<<"\nSap xep theo PP SelectionSort:"<<endl;
          cout<<endl;
          SelectionSort(a,n);
          output(a,n);
          }
          else cout<<"Chua co gi ?...Quay ve Menu !";
          sound(700);
          delay(150);
          nosound();
          getch();
          break;

      case 7: clrscr();
          if(n>0)
          {
          cout<<"Day ban dau: ";
          output(a,n);
          cout<<endl;
          cout<<"\nSap xep theo PP InterchangerSort:"<<endl;
          cout<<endl;
          InterChangeSort(a,n);
          output(a,n);
          }
          else cout<<"Chua co gi ?...Quay ve Menu !";
          sound(700);
          delay(150);
          nosound();
          getch();
          break;

      case 8: clrscr();
          if(n>0)
          {
          cout<<"Day ban dau: ";
          output(a,n);
          cout<<endl;
          cout<<"\nSap xep theo PP BubbleSort:"<<endl;
          cout<<endl;
          BubbleSort(a,n);
          output(a,n);
          }
          else cout<<"Chua co gi ?...Quay ve Menu !";
          sound(700);
          delay(150);
          nosound();
          getch();
          break;

      case 9: clrscr();
          if(n>0)
          {
          cout<<"Day ban dau: ";
          output(a,n);
          cout<<endl;
          cout<<"\nSap xep theo PP ShakerSort:"<<endl;
          cout<<endl;
          ShakerSort(a,n);
          output(a,n);
          }
          else cout<<"Chua co gi ?...Quay ve Menu !";
          sound(700);
          delay(150);
          nosound();
          getch();
          break;

      case 10:clrscr();
          if(n>0)
          {
          cout<<"Day ban dau: ";
          output(a,n);
          cout<<endl;
          cout<<"\nSap xep theo PP HeapSort:"<<endl;
          cout<<endl;
          HeapSort(a,n);
          output(a,n);
          }
          else cout<<"Chua co gi ?...Quay ve Menu !";
          sound(700);
          delay(150);
          nosound();
          getch();
          break;

      case 11:clrscr();
          if(n>0)
          {
          cout<<"Day ban dau: ";
          output(a,n);
          cout<<endl;
          cout<<"\nSap xep theo PP BInsertionSort:"<<endl;
          cout<<endl;
          BInsertionSort(a,n);
          output(a,n);
          }
          else cout<<"Chua co gi ?...Quay ve Menu !";
          sound(700);
          delay(150);
          nosound();
          getch();
          break;

      case 12:clrscr();
          if(n>0)
          {
          cout<<"Day ban dau: ";
          output(a,n);
          cout<<endl;
          cout<<"\nSap xep theo PP ShellSort:"<<endl;
          cout<<endl;
          ShellSort(a,n,n);
          output(a,n);
          }
          else cout<<"Chua co gi ?...Quay ve Menu !";
          sound(700);
          delay(150);
          nosound();
          getch();
          break;

      case 13:clrscr();
          if(n>0)
          {
          cout<<"Day ban dau: ";
          output(a,n);
          cout<<endl;
          cout<<"\nSap xep theo PP QuickSort:"<<endl;
          cout<<endl;
          QuickSort(a,1,n);
          output(a,n);
          }
          else cout<<"Chua co gi ?...Quay ve Menu !";
          sound(700);
          delay(150);
          nosound();
          getch();
          break;

      case 14:clrscr();
          if(n>0)
          {
          cout<<"Day ban dau: ";
          output(a,n);
          cout<<endl;
          cout<<"\nSap xep theo PP MergeSort:"<<endl;
          cout<<endl;
          MergeSort(a,1,n);
          output(a,n);
          }
          else cout<<"Chua co gi ?...Quay ve Menu !";
          sound(700);
          delay(150);
          nosound();
          getch();
          break;

      case 15:clrscr();
          if(n>0)
          {
          cout<<"Day ban dau: ";
          output(a,n);
          cout<<endl;
          cout<<"\nSap xep theo PP RadixSort:"<<endl;
          cout<<endl;
          RadixSort(a,n,4);
          output(a,n);
          }
          else cout<<"Chua co gi ?...Quay ve Menu !";
          sound(700);
          delay(150);
          nosound();
          getch();
          break;

      case 16:clrscr();
          sound(1000);//Am thanh bao chuan bi ket thuc
          delay(100);
          nosound();
          cout<<"\nDang thoat khoi chuong trinh !";
          cout<<".";  delay(150); cout<<".";  delay(150);
          cout<<".";  delay(150); cout<<".";  delay(150);
          cout<<".";  delay(150); cout<<".";  delay(150);
          cout<<".";  delay(150); cout<<".";  delay(150);
          cout<<".";  delay(150); cout<<".";  delay(150);
          cout<<".";  delay(150); cout<<".";  delay(150);
          cout<<endl<<endl;
          cout<<"Nhan mot phim bat ki !";
          sound(1000); //Am thanh ket thuc chuong trinh
          delay(500);
          nosound();
          getch();
          exit(1);
    }
   }
   while (1);
}