Code:

// 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();
 }

Thuật toán QuickSort:
Thuật toán dựa trên kỹ thuật chia để trị,được đề xuất bởi C.A.R Hoare
Ý tưởng như sau:Sắp xếp dãy khóa k[1..n] thì có thể coi là sắp xếp đoạn từ chỉ số 1 tới chỉ số n trong dãy khóa đó.
Nếu đoạn đó có ít hơn 2 khóa thì không cần làm gì cả,nếu đoạn đó có ít nhất 2 khóa,ta chọn một khóa ngẫu nhiên nào đó làm chốt(pivot).Mọi khóa nhỏ hơn khóa chốt được xếp vào vị trí đứng trước chốt,mọi khóa lớn hơn chốt được xếp vào vị trí sau chốt.Sau phép hoán chuyển như vậy thì đoạn đang xét được chia làm 2 đoạn khác rỗng mà mọi khóa trong đoạn đầu đều <=chốt và mọi khóa trong đoạn sau đều >=chốt.Vấn đề trở thành sắp xếp 2 đoạn mới được tạo ra (độ dài ngắn hơn độ dài đoạn ban đầu ) bằng phương pháp tương tự (gọi đệ quy)
Độ phức tạp là O(n*lgn)

Code:


// Thuat toan QuickSort
//---------------------------------------------
   //Thu tuc phan hoach mot mang
   //-------------------------------------------
   int Partition(int l,int r){
      int i,m;
      m=l;
      for(i=l+1;i<=r;++i)
         if(A[i]<A[l]){
            Swap(A[++m],A[i]);
         }
      Swap(A[l],A[m]);
      return (m);
   }

   //-------------------------------------------
   void QuickSort(int l,int r){
   int p;
   if(l<r){
      p=Partition(l,r);
      QuickSort(l,p-1);
      QuickSort(p+1,r);
   }
}

Thuật toán HeapSort:
Ta xem danh sách n phần tử là cây nhị phân. Cây nhị phân này được xác định như sau: tại nút thứ i tương ứng với chỉ số thứ i của mảng có con trái là nút 2*(i+1)-1 và con phải 2*(i+1) nếu 2*(i+1)-1 và 2*(i+1) nhỏ hơn n. Thuật toán được mô tả như sau:
- Xây dựng Heap sao cho với mọi nút cha đều có giá trị lớn hơn nút con. Khi đó nút gốc là nút có giá trị lớn nhất.
- Hoán vị nút gốc với nút thứ n – 1 và xây dựng lại Heap mới với n – 2 nút và tiếp tục hoán vị nút gốc với nút lá cuối của cây mới sau n – 2 bước ta sẽ thu được danh sách được sắp xếp theo thứ tự.
Ví dụ: xét danh sách trước khi sắp xếp
11 3 5 4 9 15 19 7
Danh sách trên được thể hiện bằng cây theo thuật toán Heap Sort như sau:
[You must be registered and logged in to see this image.]

Code:


// Thuat toan HeapSort
//---------------------------------------------
   //-----------------------------------------------
   // Thu tuc bien doi cay nhi phan co goc i thanh
   // cay Heap, n - so phan tu
   //----------------------------------------------
   void MaxHeapify(int i,int n){
      int Max;
      int l, r;
      l=2*i+1;
      r=2*i+2;
      if((l<=n)&&(A[l]>A[i]))
         Max=l;
      else
         Max=i;
      if((r<=n)&&(A[r]>A[Max]))
         Max=r;
      if(Max!=i){
         Swap(A[i],A[Max]);
         MaxHeapify(Max,n);
      }
   }
   //-----------------------------------------------
   // Thu tuc xay dung cay Heap tu mang ban dau
   //-----------------------------------------------
   void BuildMaxHeap(int n){
      for(int i=n/2-1;i>=0;--i)
         MaxHeapify(i,n);
   }

   //-----------------------------------------------
   // Thuat toan Heapsort
   //-----------------------------------------------
   void HeapSort(){
      BuildMaxHeap(N-1);
      for(int i=N-1;i>=1;--i){
         Swap(A[0],A[i]);
         MaxHeapify(0,i-1);
      }
   }


Thuật Toán MergeSort:

Mô tả bài toán: cho 2 danh sách A và B lần lượt có m và n phần tử đã sắp xếp theo thứ tự. Bài toán đặt ra trộn 2 danh sách A và B với nhau thành danh sách C cũng là một danh sách có thứ tự.
Thuật toán:
Bước 1: khởi tạo ba chỉ số chạy trong vòng lặp i = 0, j = 0, k = 0 tương ứng cho ba mảng A, B và C.
Bước 2: tại mỗi bước nếu cả hai chỉ số (iBước 3: tăng giá trị k lên 1 và quay về Bước 2.
Bước 4: sao chép tất cả các giá trị còn lại từ các danh sách mà chỉ số còn vi phạm

Code:


// Thuat toan sap xep tron
//----------------------------------------------
   // thu tuc tron hai mang da duoc sap
   // A[l,m] va A[m+1,r]
   //--------------------------------------------
   void Merge(int first, int mid, int last){
      int tmpA[N];
      int first1=first; int last1=mid;
      int first2=mid+1; int last2=last;
      int id=first1;
      for(;(first1<=last1)&&(first2<=last2);++id){
         if(A[first1]<A[first2]){
            tmpA[id]=A[first1];
            ++first1;
         }
         else{
            tmpA[id]=A[first2];
            ++first2;
         }
      }
      // sao not day con so 1
      for(;first1<=last1;++first1,++id){
         tmpA[id]=A[first1];
      }

      //Sao no day con so 2
      for(;first2<=last2;++first2,++id)
         tmpA[id]=A[first2];

      //Lay lai mang ban dau
      for(id=first;id<=last;++id)
         A[id]=tmpA[id];
   }
   //--------------------------------------------
   // Sap xep mang A[f,l] phan tu
   //-------------------------------------------
   void MergeSort(int f, int l){
   int m;
      if(f<l){
         m=(f+l)/2;
         MergeSort(f,m);
         MergeSort(m+1,l);
         Merge(f, m, l);
      }
   }