Thứ Hai, ngày 21 tháng 5 năm 2012

Cai Dat Cac Thuat Toan Sap Xep

Posted by CôĐơn Online Thứ Hai, tháng 5 21, 2012, under |


#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()
{
 cout<<"\n   Hay Chon Chuc Nang:"<<endl;
 cout<<"\n 1.Nhap Du Lieu"<<endl;
 cout<<"\n 2.Tim Kiem Bang PP LinearSeach"<<endl;
 cout<<"\n 3.Tim Kiem Bang PP BinarySearch"<<endl;
 cout<<"\n 4.Sap Xep Bang PP InsertionSort"<<endl;
 cout<<"\n 5.Sap Xep Bang PP SelectionSort"<<endl;
 cout<<"\n 6.Sap Xep Bang PP InterchangeSort"<<endl;
 cout<<"\n 7.Sap Xep Bang PP BubbleSort"<<endl;
 cout<<"\n 8.Sap Xep Bang PP ShakerSort"<<endl;
 cout<<"\n 9.Sap Xep Bang PP HeapSort"<<endl;
 cout<<"\n 10.Sap Xep Bang PP BInsertionSort"<<endl;
 cout<<"\n 11.Sap Xep Bang PP ShellSort"<<endl;
 cout<<"\n 12.Sap Xep Bang PP QuickSort"<<endl;
 cout<<"\n 13.Sap Xep Bang PP MergeSort"<<endl;
 cout<<"\n 14.Sap Xep Bang PP RadixSort"<<endl;
 cout<<"\n 15.Giai Thoat"<<endl;
 cout<<"\n Chon (1->15): ";
}

//Xac lap vung gioi han chon
int chon_menu()
{
   int ch;
   cin>>ch;
   if ((ch >= 1) && (ch <= 15)) 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;
 float 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)
{
 float 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)
{
 float 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;
 float  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 i,j;
 float x;
 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 r;
 float temp;
 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;
 float  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;
 float 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;
 float 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)
      {
       float 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;
 float 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 i,j=1,k=0;
 float  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(i=1;i<=n;i++) a[i]=temp[i];
   k=k+1;
  }
 while(k<=m);
}



//Thu tuc vao phan tu mang
void input(float a[],int n)
{
 int i;
 for (i = 1; i <= n; i++)
  {
   cout<<"\n Nhap phan tu: 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;

 do
  {
   menu();
   chon = chon_menu();
   switch(chon)
    {
     case 1:
         
          cout<<"Hay nhap vao so phan tu : n=";
          cin>>n;
          cout<<endl;
 cout<<"\n";
          if(n>0)
          {
          input(a,n);
          cout<<"\n Day vua nhap la: ";
          output(a,n);
          }
          else cout<<endl<<"Khong hop le !...Quay ve Menu !";
         
          break;



      case 2:          
          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;
       
          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 !";
       
          break;

      case 3:
       
          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;
       
          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 !";
       
         
          break;

      case 4:
          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 !";
         
          break;

      case 5:
          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 !";
       
         
          break;

      case 6:
          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 !";
         
         
          break;

      case 7:
          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 !";
         
          break;

      case 8:
          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 !";
       
       
          break;

      case 9:
          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 !";
       
          break;

      case 10:
          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 !";  
         
          break;

      case 11:
          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 !";        
          break;

      case 12:
          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 !";
       
          break;

      case 13:
          if(n>0)
          {
          cout<<" Day ban dau: ";
          output(a,n);
          cout<<endl;
          cout<<"\n Sap xep theo PP MergeSort:"<<endl;
          cout<<endl;
          MergeSort(a,1,n);
          output(a,n);
          }
          else cout<<"Chua co gi ?...Quay ve Menu !";      

         
          break;

      case 14:

          if(n>0)
          {
          cout<<"Day ban dau: ";
          output(a,n);
          cout<<endl;
          cout<<"\n Sap xep theo PP RadixSort:"<<endl;
          cout<<endl;
          RadixSort(a,n,4);
          output(a,n);
          }
          else cout<<"Chua co gi ?...Quay ve Menu !";        

          break;


 case 15:        
          exit(1);
    }
   }
   while (1);
}




Xem Nhiều

Bài đăng phổ biến

Lưu trữ blog

Blog Archive