Thứ Hai, 21 tháng 5, 2012

Cai Dat Cac Thuat Toan Sap Xep

Posted by Unknown Thứ Hai, tháng 5 21, 2012, under |


#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);
}



Thuat Toan Shaker Sort

Posted by Unknown Thứ Hai, tháng 5 21, 2012, under |

Ý tưởng:
Thuật toán Shaker Sort là cải tiến của Bubble Sort bằng cách thực hiện 2 lượt đi và về cùng lúc. Lượt đi sẽ đẩy các phần tử nhỏ về đầu dãy, lượt về sẽ đẩy các phần tử lớn về cuối dãy.
Thuật toán:

Bước 1:
Khởi tạo: l=0; r = N-1;//từ l đến r là đoạn cần được sắp xếp
K=N-1; //ghi nhận lại vị trí l xảy ra hoán vị sau cùng để làm cơ sở
thu hẹp đoạn l đến r
Bước 2:
Bước 2a: j = r;//đẩy phần tử nhỏ nhất về đầu mảng
Trong khi (j>l)
Nếu a[j] < a[j-1]:
a[j]↔ a[j-1];
k=j;//lưu lại nơi xảy ra hoán vị
j = j-1;
l=k;//loại bớt phần tử đã có thứ tự ở đầu dãy

Bước 2:

b: j=l; // đẩy phần tử lớn về cuối mảng
Trong khi (j<r)
Nếu a[j]>a[j+1]:
a[j]↔ a[j+1];
k=j;//lưu lại nơi xảy ra hoán vị
j=j+1;
r=k;//loại bớt phần tử đã có thứ tự ở cuối dãy
Bước 3: 
Nếu l < r : lặp lại bước 2.
Ví dụ:







Cài đặt:

void ShakerSort(int a[], int N)
{
   int i, k, left, right;
   k = 0;
   left = 0;
   right = N - 1;
   while (left < right) {
       for (i = right; i > left; i--)
           if (a[i] < a[i - 1]) {
               Swap(a[i], a[i - 1]); // Hoan vi a[i], a[i - 1]
               k = i; // Dung bien k danh dau de bo qua doan da co thu tu.
           }
       left = k;
       for (i = left; i < right; i++)
           if (a[i] > a[i + 1]) {
              Swap(a[i], a[i + 1]);
              k = i;
          }
      right = k;
   }
}

Thuat Toan HeapSort

Posted by Unknown Thứ Hai, tháng 5 21, 2012, under |

Ý tưởng:
Để tìm phần tử nhỏ nhất ở bước i, phương pháp sắp xếp chọn trực tiếp đã không tận dụng được các thông tin đã có được do các phép so sánh ở bước i-1. Phương pháp Heap Sort khắc phục được nhược điểm này.
 Giả sử xét trường hợp sắp xếp tăng dần, khi đó Heap được định nghĩa là một dãy các phần tử al,..,ar thoã các quan hệ sau với mọi  i  thuộc (r,l)
 ai , a2i
 ai  ,  a2i+1      (ai,a2i), (ai,a2i+1) là các cặp phần tử liên đới
o   Tính chất của heap:
 Tính chất 1: Nếu al,.,ar là một Heap thì khi cắt bỏ một số phần tử ở hai đầu của Heap thì dãy con còn lại vẫn là một Heap .
 Tính chất 2: Nếu các phần tử a1,..,an là một Heap thì phần tử a1 (đầu heap) luôn là  phần tử lớn nhất trong Heap.
 Tính chất 3: Mọi dãy al,al+1,…,ar với  2l > r là một Heap
Thuật toán:
  Giai đoạn 1:    Hiệu chỉnh dãy số ban đầu thành Heap
Giai đoạn 2:    Sắp xếp dãy số dựa trên Heap
o   Bước 1:Đưa phần tử lớn nhất về vị trí đứng ở cuối dãy
  r = n;
 Hoán vị (a1,ar)
o   Bước 2: Loại bỏ phần tử lớn nhất ra khỏi Heap r=r-1;
  Hiệu chỉnh phần còn lại của dãy từ al đến ar thành một Heap.
o   Bước 3:Nếu r >1 ( heap còn phần tử) : lặp lại bước 2
  Ngược lại: dừng
o   Dựa vào tính chất 3, ta có thể thực hiện giai đoạn 1 bằng cách bắt đầu từ heap mặc nhiên an/2+1, an/2+2,…,an,  lần lượt thêm vào các phần tử an/2, an/2-1,…,a1. ta sẽ nhận được Heap theo mong muốn. Như vậy giải đoạn 1 tương đương với n/2 lần thực hiện bước 2 của giai đoạn 2.
o   Cài đặt
o   Để cài đặt Heap sort cần xây dựng một số thủ tục phụ trợ:
1. Thủ tục hiệu chỉnh một dãy al,ar thành heap
o   Giả sử có al,al+1,…ar, trong đó đoạn al+1,…ar, đã là một heap.  ta cần xây dựng al,al+1,…,ar thành một heap. để làm điều này ta lần lượt xét quan hệ của một phần tử ai nào đó với các phần tử liên đới của nó trong dãy là a2i và a2i+1,  nếu nó vi phạm quan hệ của heap  thì đổi chổ ai với phần tử liên đới thich hợp của nó – việc đổi này có thể gây phản ứng dây chuyền.
2. Hiệu chỉnh ao,..,an-1 thành heap.
  Cho một dãy bất kỳ al,…,ar ,  theo tính chất 3 ta có dãy an/2+1, an/2+2,…,an đã là một heap. Ghép thêm phần tử an/2  vào bên trái của heap hiện hành và hiệu chỉnh lại dãy an/2,an/2+1,..,ar thành heap.

Ví dụ:
Ví dụ:  Cho dãy : 15 , 19 , 10 , 7 , 17 , 16
 Giai đoạn 1: tạo heap: i= [0+length]/2=[0+5]/2=2,  (ai , a2i)
 (ai  ,  a2i+1) trong đó: (ai,a2i), (ai,a2i+1) là các cặp phần tử liên đới, nếu thỏa thì i=i-1, không thi hoán vị (ai,a2i+1).




Giai đoạn 2: Sắp xếp dựa trên heap, phần tử đầu heap lớn nhất dãy, trong quá trình sx nếu mảng không còn là heap thì phải hiệu chỉnh lại

























Cài đặt:
void heap_sort(int a[], int n)
{
int i,j,size=n-1,k,tg,tg2;
//Gioi han dan cac phan tu van vun
while(size>0)
{
k=(int)(size-1)/2; //Vun cac phan tu mang thanh dong
while(k>=0)
{
i=k; //Vun phan tu lon nhat len nut tren
while(i*2<size)
{
j=2*i+1;
if ((j+1<=size)&&(a[j]<a[j+1])) //***
j=j+1;
if (a[i]<a[j]) //***
{
tg=a[i];
a[i]=a[j];
a[j]=tg;
i=j;
}
else break;
}
k--;
}
tg2=a[0];
a[0]=a[size];
a[size]=tg2;
size--;
}
}
Đây là trang Web về các thuật toán rất hay





Thuat Toan MergeSort

Posted by Unknown Thứ Hai, tháng 5 21, 2012, under |


Ý tưởng:
Merge sort chia danh sách dữ liệu  cần được sắp xếp thành hai nữa bằng nhau, và đặt chúng vào các vùng chứa  dữ liệu riêng biệt (list, array,…). Mỗi mảng dữ liệu được sắp xếp một  cách đệ quy, sau đó trộn lẫn vào nhau tạo thành danh sách dữ liệu được  sắp xếp cuối cùng. Giống như hầu hết các phương pháp sắp xếp đệ quy,  Merge sort có độ phức tạp là O(n log n).
Cách triển khai cơ bản của Merge sort là dùng ba mảng dữ liệu – mỗi mảng  để chứa mổi nữa của tập dữ liệu cần sắp xếp và một mảng chứa danh sách  được sắp xếp cuối cùng. Thuật toán được giới thiệu sau đây trộn các mảng  lại thành một, vì vậy chỉ sử dụng hai mảng cho toàn bộ quá trình xử lý.  Hiện nay cũng tồn tại phiên bản không đệ quy của Merge sort, nhưng  chúng không thu được bất kì một cải tiến tốc độ nào so với phiên bản đệ  quy qua thử nghiệm trên hầu hết các kiến trúc xử lý.
Merge sort thì nhanh hơn một ít so với Heap sort với các tập dữ liệu  lớn, nhưng nó đòi hỏi 2 lần bộ nhớ so với Heap sort vì vậy nó không được  ưa chuộng trong việc triển khai ứng dụng dù cho mục đích là gì – Quick  sort là lựa chọn tốt hơn cho thời gian và Heap sort thì lại là lựa chọn  tốt hơn với các tập dữ liệu rất lớn.
Giống như Quick sort, Merge sort là phương pháp dựa trên đệ quy, điều  này khiến nó sẽ là lựa chọn tồi với các ứng dụng chạy trên máy tính bị  giới hạn về bộ nhớ.
Thuật giải:

- Ta xem dãy cần sắp xếp có N phần tử là N đoạn và mỗi đoạn đã được sắp xếp là dãy tăng dần rồi (Tất nhiên vì chỉ mỗi đoạn chỉ có 1 phần tử).
- Sau đó ta trộn 2 đoạn liên tiếp nhau để tạo thành các đoạn có độ dài bằng 2 sao cho mỗi đoạn đã được sắp xếp tăng dần.
- Và tiếp tục cứ trộn 2 đoạn liên tiếp, ta sẽ được những đoạn có độ dài lớn hơn và đồng thời số đoạn trong dãy cũng sẽ ít đi... và cho tới khi chỉ còn lại 1 đoạn duy nhất là dãy đã được sắp xếp tăng dần.
Ví dụ:  Cho dãy : 38 , 27 , 43 , 3 , 9 , 82  , 10


Ví dụ:   Cho dãy: 6 , 5 ,  3 , 1 , 8 ,  7 ,  2 ,  4



Cài dặt:

void merge(int a[],int k1,int k2,int k3)
{
int i,j,z,t[100];
i=k1;
j=k2;
z=k1;
// Tron phan tu
// So sanh cac phan tu de dua vao day T
while((i<k2)&&(j<=k3))
{
if (a[i]<=a[j]) //***
{
t[z]=a[i];
i++;
}
else
{
t[z]=a[j];
j++;
}
z++;
}
// Gan cac phan tu con lai cua day (k1->k2-1) vao day T (neu con)
if(i>=k2)
while (z<=k3)
{
t[z]=a[j];
j++;
z++;
}
// Gan cac phan tu con lai cua day (k2->k3) vao day T (neu con)
if (j>k3)
while (z<=k3)
{
t[z]=a[i];
i++;
z++;
}
// Sao chep day T vao day A
for(z=k1;z<=k3;z++)
a[z]=t[z];
}




Thuat Toan RadixSort

Posted by Unknown Thứ Hai, tháng 5 21, 2012, under |

Ý tưởng: 

 Thuật giải sắp xếp theo phương pháp cơ số không quan tâm đến việc so sánh giá trị
của các phần tử như các thuật giải trước. RadixSort sử dụng cách thức phân loại các con
số trong dãy và thứ tự phân loại con con số này để tạo ra thứ tự cho các phần tử. Đây là
cách tiếp cận khác so với các phương pháp sắp xếp trước là so sánh các giá trị của các
phần tử. Thuật giải dựa trên ý tưởng chính là sắp xếp từng con số của một dãy các số.

 Để sắp xếp dãy a[1], a[2],..., a[n] giải thuật RadixSort thực hiện như sau:
 Xem mỗi phần tử a[i] trong dãy a[1]...a[n] là một số nguyên có tối đa m chữ số
 Lần lượt phân loại các chữ số theo hàng đơn vị, hàng chục, hàng trăm...Tại mỗi
bước phân loại ta sẽ nối các dãy con từ danh sách đã phân loại theo thứ tự 0 ® 9.
Sau khi phân loại xong ở hàng thứ m cao nhất ta sẽ thu được danh sách các phần
tử được sắp.
Thuật toán :

Bước 1 : k = 0; // k là chữ số phân loại, k = 0 hàng đơn vị, k = 1 hàng chục...
 Bước 2 : // Tạo các dãy chứa phần tử phân loại B[0]...B[9]
Khởi tạo B[0]...B[9] rỗng, chưa chứa phần tử nào, B[i] sẽ chứa các phần tử có chữ
số thứ k là i.
 Bước 3 :
o For i=1 to n do
 Đặt a[i] vào dãy B[j] với j là chữ số thứ k của a[i].
o Nối B[0], B[1],..., B[9] lại theo đúng trình tự thành a.
 Bước 4 :
o k = k +1
o Nếu k < m: Þ Bước 2. // m là số lượng chữ số tối đa của các số
trong mảng
o Ngược lại: Þ Dừng.

 Mảng a[MAX] chứa các phần tử của mảng cần sắp tăng.
 Mảng B[10][MAX] chứa các dãy số được phân tạm thời theo các
con số. Ví dụ B[0] chứa các phần tử có con số ở hàng đơn vị .Khi đó với mỗi dòng của B thì sẽ phân các phần tử có con số ở hàng thứ i (i từ 0 - 9), các giá trị cột j sẽ lần lượt chứa các phần tử có cùng con số ở hàng thứ i.
 Mảng Len[10] chứa số lượng các phần tử của các dòng B[i].  Tại mỗi bước
trước khi phân các phần tử vào mảng B thì các Len[i] được khởi tạo là 0.
 Ví dụ : Cho dãy:



Phân lô theo hàng đơn vị:

12
0701
11
1725
10
0999
9
9170
8
3252
7
4518
6
7009
5
1424
4
0428
3
1239
0999
2
8425
1725
4518
7009
1
7013
9170
0701
3252
7013
1424
8425
0428
1239
CS
A
0
1
2
3
4
5
6
7
8
9
Các lô B dùng để phân loại

Phân lô theo hàng chục:


12
0999
11
7009
10
1239
9
4518
8
0428
7
1725
6
8425
5
1424
4
7013
0428
3
3252
1725
2
0701
7009
4518
8425
1
9170
0701
7013
1424
1239
3252
9170
0999
CS
A
0
1
2
3
4
5
6
7
8
9

Phân lô theo hàng trăm:


12
0999
11
9170
10
3252
9
1239
8
0428
7
1725
6
8425
5
1424 
4
4518
3
0428
2
7009
7013
3252
8425
1725
1
0701
7009
9170
1239
1424
4518
0701
0999
CS
A
0
1
2
3
4
5
6
7
8
9

Phân lô theo hàng ngàn:

12
0999
11
1725
10
0701
9
4518
8
0428
7
8425
6
1424
5
3252
4
1239
3
9170
0999
1725
2
7013
0701
1424
7013
1
7009
0428
1239
3252
4518
7009
8425
9170
CS
A
0
1
2
3
4
5
6
7
8
9

Lấy các phần tử từ các lô B0, B1, ., B9 nối lại thành a:



12
9170
11
8425
10
7013
9
7009
8
4518
7
3252
6
1725
5
1424
4
1239
3
0999
2
0701
1
0428
CS
A
0
1
2
3
4
5
6
7
8
9
Cài đặt:
void RadixSort(long a[], int n)
{
int i, j, d;
int h = 10; // biến để lấy các con số, bắt đầu từ hàng đơn vị
long B[10][MAX]; // mảng hai chiều chứa các phần tử phân lô
int Len[10]; // kích thước của từng mảng B[i]
// MAXDIGIT là số con số tối đa của các phần tử a[i]
for(d = 0; d < MAXDIGIT; d++)
{
// khởi tạo kích thước các dãy B[i] là 0
for( i = 0; i < 10; i++)
Len[i] = 0;
// thực hiện phân lô các phần tử theo con số hàng thứ d tính từ cuối
for(i = 0; i < n; i++) // duyệt qua tất cả các phần tử của mảng
{
digit = (a[i] % h) / (h/ 10); // lấy con số theo hàng h
// đưa vào dãy (lô) B[digit] ở cột Len[digit]
B[digit][Len[digit]++] = a[i];
}// end for i
// thực hiện nối lại tuần tự từ B[0] – đến B[9] vào mảng a[] ban đầu
num = 0; // chỉ số bắt đầu cho mảng a[]
for(i = 0; i < 10; i++) // duyệt qua các dãy từ B[0] – đến B[9]
{
// lấy từng phần tử của từng dãy B[i]
for(j =0; j < Len[i]; j++)
a[num++] = B[i][j];
}// end for i
h *= 10; // qua hàng kế tiếp.
}// end for d
}// end RadixSort


Xem Nhiều

Bài đăng phổ biến

Lưu trữ blog

Blog Archive