1. Phần cơ sở lý thuyết bạn tìm kiếm và học thêm để hiểu rõ về việc mình cần làm nhé.
2 Cài đặt chương trình như dưới.
Lưu ý là chương trình chỉ mang tính chất tham khảo, bạn cố gắng tự làm để hiểu rõ về
cách hoạt động cũng như ý nghĩa các công thức , thuật toán nhé.
Thầy cô bảo vệ sẽ hỏi kỹ vấn đề này đó.
/* Chuong Trinh Su Dung Cac Thuat Toan Sap Xep & Tim Kiem Tung Phan Tu.
Ngon ngu lap trinh: C++ */
#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(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);
}
// Code Nguồn: Cộng đồng C Việt.
Thông tin liên hệ anh2bmw khi có bất kỳ thắc mắc:
skype: trantien281
mail: anh2bmw@gmail.com
