Cai Dat Cac Thuat Toan Sap Xep
Written By 1 on Thứ Hai, 21 tháng 5, 2012 | 04:52
#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);
}
0 nhận xét:
Đăng nhận xét