Các Thuật Toán Sắp Xếp & Tìm Kiếm Trên Mảng

[cò lã]

Tôi xin được chia sẽ với các bạn chương trình của mình, với mục đích giúp đỡ những bạn đang tìm kiếm bài mẫu về những thuật toán sắp xếp và tìm kiếm trên mảng.
Sau đây là đoạn chương trình:

PHP Code:

/* Chuong Trinh Su Dung Cac Thuat Toan Sap Xep & Tim Kiem Tung Phan Tu.
Ho & Ten: Do Minh Tan
Lop: CN1-K4
---5/2007---
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<<"\nHo & Ten: DO MINH TAN";
 cout<<endl<<"\nLop: CN1-K4";
 cout<<endl<<"\nThuc hien: 5/2007";
 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);
} 


Chương trình trên tôi đã chạy thử, thấy hoàn toàn ổn định nên các bạn có thể yên tâm đưa vào chạy trực tiếp.
Vì thời gian có hạn, tôi lại lên website ít nên có thể không trả lời được những câu hỏi các bạn đặt ra do đó tôi xin nhờ các bạn giải đáp những thắc mắc cho những bạn không hiểu.
Xin chân thành cảm ơn !

[lelinhcntt]

Có đồ họa minh họa các thuật toán để thấy rõ ưu nhược điểm và cách sắp xếp của từng thuật toán thì tốt. Hi vọng ai đó có nhiều kinh nghiệm post lên cho mọi người cùng tham khảo

[Forlorn_hope]

Sách "Cấu trúc dữ liệu" của trường Tự nhiên hiển thị minh họa đồ họa rất rõ ràng đấy bạn. Mua về xem và để dành khi lâu ngày quên có thể lấy ra xem

[anhtai1281992]

nhìn mà thấy sợ luôn
mấy anh pro thật!