Connect & Share !

//Ice.Tea
// THUAT TOAN SAP XEP


/*
1. Doi cho truc tiep - Interchange sort
2. Chon truc tiep - Selection sort
3. Chen truc tiep - Insertion sort
4. Noi bot - Bubble sort
*/


//------------------


// THUAT TOAN TIM KIEM
/*
1. Tim kiem tuan tu (Tuyen tinh)- sequential Search
2. Tim kiem nhi phan - binary Search
*/


// Code by Ice.Tea
//-------SAP XEP---------
#include <iostream.h>
#include <conio.h>
//1. Interchange Sort
void interchangesort(int a[],int n)
{
int temp;
for (int i=0;i<n-1;i++)
 for(int j=i+1;j<n;j++)
{
if (a[j]<a[i])
 {
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}


// 2. Selection Sort
void selectionsort(int a[],int n)
{
int i,j,min,temp;
for(i=0;i<n-1;i++)
  {
  min = i;
  for (j=i+1;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;
}
  }
}


// 3. Insertion sort
void insertionsort(int a[],int n)
{
int i,x,pos;
for (i=1;i<n;i++)
  {
  pos=i-1;
  x=a[i];// luu phan tu can chen ra ngoai
  // tim vi tri chen va don cac phan tu
 while((x<a[pos])&&(pos>=0 ))
  {
  a[pos+1]=a[pos];
  pos--;
  }
 // chen phan tu vao dung vi tri
 a[pos+1]=x;
  }
}


//4. Bubble sort
void bubblesort(int a[],int  n)
{
int i,j,temp;
// so sanh va doi cho cac phan tu lien ke nhau
for(i=0;i<n-1;i++)
  for(j=n-1;j>i;j--)
if (a[j]<a[j-1])
{
temp = a[j];
a[j]=a[j-1];
a[j-1]=temp;
}
}




// -------TIM KIEM--------


// Tiem kiem tuan tu (tuyen tinh)
void sequential_search(int a[],int n)
{
int i=0;
int x;// x= khoa tim kiem
cout<<"Nhap khoa tim kiem : ";
cin>>x;
while((i<n)&&(x!=a[i]))// hoac co the dung vong lap for
i++;
// Code dung for
/*
  for (int i=0;i<n;i++)
if (a[i]==x)
return i;  // tra ve vi tri cua khoa
else
return 0;
*/
  if (i<n)
cout<<"Tim thay tai vi tri \n"<<i;
else
 cout<<"Khong tim thay phan tu thoa man ! \n";
}


// Tim kiem nhi phan
void binary_search(int a[],int n)
{
int m=0,r=n-1,l=0,x;
cout<<"Nhap khoa tiem kiem : ";cin>>x;
while(l<=r)
 {
 m=(l+r)/2;
 if (x==a[m])
  break;
 else
if(x<a[m])
 r=m-1;//tim kiem theo thu tu tang dan
else
 l=m+1;
 }
 if (l<=r)
  cout<<"Tim thay khoa tai vi tri "<<m;
 else
 cout<<"Khong ton tai khoa trong day ! \n";
}
// Ham nhap du lieu
void nhap(int a[],int n)
{
cout<<"Nhap day so : \n";
  for(int i=0;i<n;i++)
cin>>a[i];
}


//Ham hien thi ket qua


 void xuat(int a[],int n)
 {
 cout<<"Day sau khi xu ly : \n";
 for(int i=0;i<n;i++)
  cout<<a[i]<<"  ";
 }


 //MAIN


 void main()
 {
 int a[100],n,t;
 cout<<"Nhap so phan tu n = ";
 cin>>n;
 nhap(a,n);
 lap:
 cout<<"\t---------MENU-----------\n";
 cout<<"\n1. Sap xep truc tiep - Interchange sort ";
 cout<<"\n2. Sap xep tron  - selection sort ";
 cout<<"\n3. Sap xep chen truc tiep - Insertion sort ";
 cout<<"\n4. Sap xep noi bot - Bubble sort ";
 cout<<"\n5. Tim kiem tuan tu - sequential search ";
 cout<<"\n6. Tim kiem nhi phan - binary search ";
 cout<<"\n\nNhap lua chon : ";
 cin>>t;
 switch(t)
  {
  case 1:interchangesort(a,n);  xuat(a,n);break;
  case 2:selectionsort(a,n);  xuat(a,n);break;
  case 3:insertionsort(a,n);  xuat(a,n);break;
  case 4:bubblesort(a,n);  xuat(a,n);break;
  case 5:sequential_search(a,n);break;
  case 6:binary_search(a,n);break;
  default: goto lap;
  }
  cout<<"\n";


  getch();
 }

Read Users' Comments (0)