[Thuật toán] Các thuật toán sắp xếp trong lập trình C - Thuật toán sắp xếp nhanh


1. Bài toán
   Cho dãy X = {X1, X1, ..., Xn}, hãy sắp xếp dãy theo chiều không giảm.
2. Ý tưởng
    - Ý tưởng của thuật toán này là "chia để trị", nói cách khác chúng ta tìm cách chia đôi dãy ban đầu bằng cách chọn ra một phần tử là chốt (pivot). Từ dãy ban đầu, tất cả phần tử nhỏ hơn phần tử chốt thì đưa về bên trái dãy, tất cả các phần tử lớn hơn hoặc bằng phần tử chốt thì đưa về bên phải dãy. Sau bước này ta có phần tử chốt là đứng đúng vị trí. Dãy ban đầu phân chia làm hai dãy con nằm hai bên chốt.
   - Tiếp tục phân chia các dãy con theo cách tương tự đến khi mọi dãy con đều có độ dài bằng 1.
   - Có thể lựa chọn phần tử chốt nằm đầu, cuối hay giữa dãy. Ở đây ta sẽ lựa chọn phần tử chốt nằm gần giữa dãy nhất.
3. Giải thuật
    a. Sắp xếp một đoạn bất kỳ X[L],...,X[R] với điều kiện L < R
        - Bước 1: pirot = (L+R) div 2, key=X[pirot]
        - Bước 2: i=L+1, j=R
        - Bước 3:
       * Nếu X[i] < key thì i=i+1;
       * Nếu X[j] > key thì j=j-1;
       - Bước 3: Nếu i>j thì đổi chổ X[i] với X[j], quay về Bước 3
      - Bước 4: Lặp lại từ Bước 1 đến Bước 3 với đoạn X[L],...,X[j-1] và X[j] đến X[R], dừng khi tất cả đoạn có độ dài là 1.
Thuật toán viết bằng C++ : 
Code:
void QuickSort(int X[], int n)
{
   Partition(1,n);
}
// hàm phân đoạn có 2 tham số L, R lần lượt là chỉ số đầu và cuối của //mảng
void Partition (int L, int R)
{
   if (L>=R) return;
       pirot=(L+R)div 2; // Luôn lấy chốt ở vị trí gần chính giữa dãy
   key = X[pirot];
   int i=L;
   int j= R;
   
   while (i<=j)
   {
      while (X[i] < key) i=i+1;
      while (X[j] > key) j=j-1;
      if (i<j)
      {
         swap(X[i],X[j]);
         i=i+1; j=j-1;      
      }      
   }
   Partition(L,j);
   Partition(i,R);   
}
4. Ví dụ
X = {7, 2, 5, 4, 1, 3, 8, 6}
Dãy ban đầu: 7, 2, 5, 4, 1, 3, 8, 6
Phân chia lần đầu:
Ban đầu ta có L=1, R=8, pirot=( 1+8 ) div 2 = 4, key=X[4]=4
i=1, j=8, tăng i trước, giảm j sau, ta chỉ xét tại các điểm có xẩy ra việc đổi chổ
i=1 < j=6, X[1]=7 > key > X[6]=3, swap(X[1],X[6], ta có 3, 2, 5, 4, 1, 7, 8, 6
i=3 < j=5, X[3]=5 > key > X[5]=1, swap(X[3],X[5], ta có 3, 2, 1, 4, 5, 7, 8, 6
i=5 > j=3, dừng việc xét, ta có 3, 2, 1, 4, 5, 7, 8, 6
Sau lần phân chia thứ nhất ta có hai dãy con nằm hai bên phần tử chốt {3, 2, 1} 4 {5, 7, 8, 6}
Thực hiện với dãy con {3, 2, 1}
L=1, R=3, pirot=( 1+3 ) div 2 = 2, key=X[2]=2
i=1 < j=3, X[1]=3 > key > X[3]=1, swap(X[1],X[3], ta có 1, 2, 3
i=3 > j=1, ngừng việc xét, ta có 1, 2, 3
Dãy này tiếp tục phân chia thành 2 dãy con {1},2, {3}, vì số phần tử trong các dãy đều bằng 1 nên ta không xét nữa.
Thực hiện với dãy con {5, 7, 8, 6}
L=i+1=5, R=8, pirot=( 4+8 ) div 2 = 6, key =X[6]=7
i=6 < j=8, X[6]=7 >= key > X[8]=6, swap(X[6],X[8], ta có 5, 6, 8, 7
i=7 > j= 6, dừng việc xét, ta có 5, 6, 8, 7
Dãy này lại phân làm hai dãy con {5} , 6, {8, 7}
Thực hiện tương tự với dãy {8, 7} ta có 7, {8}
Cuối cùng, ghép các dãy trên theo thứ tự ban đầu ta có 1, 2, 3, 4, 5, 6, 7, 8, dãy đã được sắp xếp.

[Thuật toán] Các thuật toán sắp xếp trong lập trình C - Thuật toán sắp xếp Merge sort. (Sắp xếp hòa nhập, sắp xếp trộn)

1. Bài toán
Cho dãy X = {X1, X1, ..., Xn}, hãy sắp xếp dãy theo chiều không giảm.
2. Ý tưởng
- Giả sử dãy X[1],...,X[i],...,X[n] có hai đoạn đã được sắp xếp không giảm là X[1],...,X[i] và X[i+1],...,X[n], ta tiến hành tạo ra dãy mới bằng cách lần lượt lấy hai phần tử đầu tiên của mỗi đoạn và so sánh với nhau. Phần tử nào nhỏ hơn thì lấy ra dãy mới và bỏ nó ra khỏi đoạn đang xét. Cứ tiến hành như vậy cho tới khi một dãy bị vét hết (không còn phần tử nào). Lấy toàn bộ phần tử còn lại của đoạn không xét hết nối vào sau dãy đích. Như vậy dãy mới là một dãy đã được sắp xếp.
- Trong mọi trường hợp, có thể coi dãy gồm duy nhất 1 phần tử là đã được sắp xếp. Lợi dụng việc này, ta phân chia một dãy ra thành nhiều dãy con chỉ gồm một phần tử rồi lần lượt hòa nhập từng đôi một với nhau.
Thuật toán viết bằng C++ : 
Code:
// Thủ tục trộn gọi đệ quy
void MergeSort(int X[], int L, int R)
{
     int M;
     if (L<R){
     M=int((L+R)/2);
     MergeSort(X,L,M);
     MergeSort(X,M+1,R);
     Merge(X,L,M+1,R);
}
}
// Thủ tục trộn hai đoạn đã sắp xếp trong một dãy
void Merge(int a[], int k1, int k2, int k3)
{
     int i,j,k,t;
     int temp[];
     i=k1; j=k2; k=k3;
     while (i<k2) and (j<=k3)
    {
       if (a[i]<=a[j]){
       temmp[k]=a[i];
       i=i+1;
     }
else{
      temp[k]=a[j];
       j=j+1;
    }
k=k+1;
}
if (i>=k2)
for(t=j;t<=k3,t++)
      temp[k+t-j]=a[t];
else
for(t=i;t<=k2,t++)
     temp[k+t-i]=a[t];
for(k=k1;t<=k3,k++)
     a[k]=temp[k];
}

[Thuật toán] Các thuật toán sắp xếp trong lập trình C - Thuật toán sắp xếp Shell sort

  1. Bubble sort. (Nổi bọt, nổi bong bóng)
  2. Quick sort. (Sắp xếp nhanh)
  3. Simple selection sort. (Sắp xếp chọn)
  4. Thuật toán sắp xếp chèn
  5. Heap sort. (Sắp xếp vun đống)
  6. Simple insertion sort.(Sắp xếp chèn)
  7.  Shell sort.
vÝ tưởng thuật toán 
  • Là giải thuật cải tiến từ Insertion sort. Ý tưởng chính của thuật toán là phân chia dãy ban đầu thành những dãy con mà mỗi phần tử của dãy cách nhau 1 vị trí là h. Insertion sort áp dụng sau đó trên mỗi dãy con sẽ làm cho các phần tử được đưa về vị trí đúng tương đối (trong dãy con) 1 cách nhanh chóng.
  • Sau đó tiếp tục giảm khoảng cách h để tạo thành các dãy con mới (Tạo điều kiện để so sánh một phần tử với nhiều phần tử khác trước đó không ở cùng dãy con với nó) và lại tiếp tục sắp xếp.
  • Thuật toán dừng khi h = 1, lúc này bảo đảm tất cả các phần tử trong dãy ban đầu sẽ được so sánh với nhau để xác định trật tự cuối cùng.

Thuật toán viết bằng C++ : 
void main()
{
int i,n,j,gap,temp,a[10];
printf("Mang co bao nhieu phan tu:=");
scanf("%d",&n);
printf("Nhap %d phan tu mang \n\n",n);
for(i=0;i<n;i++)
{
printf("Nhap a[%d]:",i);
scanf("\n%d",&a[i]);
}
for(gap=n/2;gap>0;gap=gap/2)
{
for(i=0;i<n;i=i+gap)
{
temp=a[i];
for(j=i;j>0&&a[j-gap]>temp;j=j-gap)
{
a[j]=a[j-gap];
}
a[j]=temp;
}
}
printf("Sap Xep Hoan Thanh\n");
for(i=0;i<n;i++)
printf("%d\n",a[i]);
getch();
}

vĐộ phức tạp của thuật toán
  •  Yếu tố quyết định chính của thuật toán chính là cách chọn khoảng cách h trong từng bước sắp xếp và số bước sắp xếp k. Nhưng phải thỏa 2 điều kiện sau: hi > hi + 1 và hk = 1. 
  • Các phần tử h không được là bội số của nhau nhằm tránh hiện tượng mỗi bước sắp thứ tự phải tổ hợp 2 nhóm mà bước trước chúng không hề có ảnh hưởng lẫn nhau. Điều mong muốn là ảnh hưởng giữa các nhóm khác nhau càng nhiều càng tốt. 
  • Việc đánh giá giải thuật Shell sort hiện nay rất phức tạp, thậm chí 1 số chưa được chứng minh. Nhưng có 1 điều chắc chắn là hiệu quả của thuật toán phụ thuộc vào dãy các độ dài được chọn. Trong trường hợp chọn dãy độ dài theo công thức hi = (hi – 1 - 1)/2 và hk = 1, k = log2 - 1 thì giải thuật có độ phức tạp tương đương n1,2 << n2 .

[Thuật toán] Các thuật toán sắp xếp trong lập trình C- Thuật toán sắp xếp chèn




  • Bubble sort. (Nổi bọt, nổi bong bóng)
  • Quick sort. (Sắp xếp nhanh)
  • Simple selection sort. (Sắp xếp chọn)

    • Sắp xếp chèn (insertion sort) là một thuật toán sắp xếp bắt chước cách sắp xếp quân bài của những người chơi bài. Muốn sắp một bộ bài theo trật tự người chơi bài rút lần lượt từ quân thứ 2, so với các quân đứng trước nó để chèn vào vị trí thích hợp.
    Thuật toán:
    Cơ sở lập luận của sắp xếp chèn có thể mô tả như sau: Xét danh sách con gồm k phần tử đầu a_1,...,a_{k}. Với k = 1, danh sách gồm một phần tử đã được sắp. Giả sử trong danh sách k-1 phần tử đầu a_1,...,a_{k-1} đã được sắp. Để sắp xếp phần tử a_k=xta tìm vị trí thích hợp của nó trong dãy a_1,...,a_{k-1}. Vị trí thích hợp đó là đứng trước phần tử lớn hơn nó và sau phần tử nhỏ hơn hoặc bằng nó.
    Các phần tử ≤xVị trí thích hợpCác phần tử>xCác phần tử chưa sắp
    a_1...a_{i-1}xa_{i+1}...a_{k-1}a_{k+1}...a_n

    Mô tả thuật toán sắp xếp chèn - tinhoccoban.net
    Mô tả thuật toán sắp xếp chèn
    Thuật toán viết bằng C++ : 
    Code:
    #include <iostream>
    using namespace std;
    void insertion_sort(int a[], int n)
    {
         int i,tg,x;
         for (i=1;i<n;i++)
          {
            tg=a[i];
            x=i-1;
            while((x>=0)&&(a[x]>tg))
                {
                a[x+1] = a[x];
                x--;
                }
            a[x+1] =tg;
         }
    }
    int main()
    {
        int n;
        cout <<"Nhap so cac so hang can sap xep:  ";
        cin >> n;
        int a[n];
        cout<<"Nhap cac so hang: "<<endl;
        for(int i=0;i<n;i++)
        {
            cout<<"a"<<i+1<<": " ;
            cin >>a[i];
            cout << endl;
        }
        insertion_sort(a,n);
        cout<<"Day sau khi sap xep:  ";
        for(int i=0;i<n;i++)
            cout<<a[i] << "  ";}

    5.Heap sort. (Sắp xếp vun đống)
    6.Simple insertion sort.(Sắp xếp chèn)
    7. Shell sort.
    8.Merge sort. (Sắp xếp hòa nhập)

    [Thuật toán] Tìm kiếm nhị phân:



    Là phương pháp tìm kiếm phổ biến, dựa trên dãy đã sắp xếp thứ tự. Nội dung của giải thuật này là : lấy khoá X cần tìm so sánh với phần tử ở giữa dãy , với vị trí phần tử ở giữa được xác định là mid = (hight+low)/2, trong đó cận dưới low=0, cận trên hight= n-1. Vì dãy đã sắp xếp nên có các trường hợp sau xảy ra: 
    nếu X= A[mid] thì cho ra kết quả (cần tìm X trong dãy A[i])
    nếu X < A[mid] => X thuộc khoảng [A[low];A[mid-1] ] lại tiếp tục tìm kiếm nhị phân X trong dãy từ A[low]-> A[mid -1]
    Nếu X> A[mid]=> X thuộc khoảng [A[mid+1], A[hight]], lại tiếp tục tìm kiếm nhị phân X trong dãy từ A[mid + 1], A[hight]
    Quá trình tìm cho tới khi tìm ra X hoặc không tìm được X trong dãy

    Có thể viết thuật toán tìm kiếm nhị phân theo vòng lặp hoặc theo đệ quy đều được.
    Ta sẽ viết luôn thủ tục hàm tìm kiếm nhị phân theo hai cách:
    Hàm tìm kiếm nhị phân mà chúng ta viết là : 
    Binary_Search(Usertype *A, Usertype X, int n);
    Trong đó: Usertype là cấu trúc dữ liệu mà ta cần tìm kiếm, có thể là các kiểu đơn giản có sẵn: int, long , float, doublle., char… hoặc các kiểu do người dùng định nghĩa, có thể là một cấu trúc nào đó (ví dụ như Struct SinhVien, SoPhuc….)
    Mảng A có n phần tử đã được sắp xếp. Do đó trước khi thực hiện thao tác tìm kiếm thì chúng ta phải thực hiện thao tác sắp xếp dãy đã.

    Viết dưới dạng vòng lặp : 


    int Binary_Search(Usertype *A, Usertype X, int n) // hàm trả về là vị trí của X trong dãy
    {
    2.     int mid,low=o,hight=n-1;
    3.     while(low<=hight) // lap neu can duoi van nho hon can tren
    4.        {
    5.     mid=(low+hight)/2;  //xác định vị trí phần tử ở giữa
    6.     if(X>A[mid]) low=mid+1;      // X thuộc [mid+1,hight]
    7.             else        if(X<A[mid]) hight=mid-1;   // X thuộc đoạn [low,mid-1]
    8.     else   return(mid); //trả về vị trí của X trong dãy
    9.    }
    10.         return(-1); // nếu X không thuộc dãy thì trả về giá trị của hàm là -1
    11. }

    Viết dưới dạng hàm đệ quy:
    C Code:
    1. int Binary_Search(Usertype *A, Usertype X, int i,int j)  // hàm trả về là vị trí của X trong dãy
    2. {
    3.     int mid=(i+j)/2;
    4.     if(X>A[mid]&&i<mid)
    5.         return(Binary_Search(A,X,mid+1,j));
    6.     else if(X<A[mid]&&j>mid)
    7.         return(Binary_Search(A,X,i,mid-1));
    8.     else if(X==A[mid])
    9.         return(mid);
    10.     return(-1); // tra lai gia tri la -1 nếu không tìm thấy X
    11. }

    Chương trình cài đặt thuật toán cho tìm kiếm nhị phân một số nguyên trong dãy như sau:
    C Code:
    1. #include    <stdio.h>
    2. #include    <conio.h>
    3. #include    <stdlib.h>
    4. #include    <alloc.h>
    5. #include    <dos.h>
    6. int Binary_Search( int *, int, int);
    7. void Bubble(int *, int);
    8. void Init(int *, int);
    10. int Binary_Search( int *A, int X, int n) {
    11.     int mid, low = 0, hight = n-1;
    12.     while (low<=hight){
    13.         mid = (low +hight)/2;
    14.         if (X >A[mid] ) low = mid +1;
    15.         else if (X<A[mid] ) hight = mid -1;
    16.         else    return (mid);
    17.     }
    18.     return(-1);
    19. }
    20. void Init(int *A, int n){
    21.     int i;
    22.     printf("\n Tao lap day so:");
    23.     for (i=0; i<n;i++){
    24.         A[i]=random(1000);
    25.         printf("%5d",A[i]);
    26.     }
    27.     delay(1000);
    28. }
    29. void Bubble(int *A, int n){
    30.     register i,j,temp;
    31.     for (i=1; i<n; i++){
    32.         for (j=n-1; j>=i;j--){
    33.             if (A[j-1]>A[j]){
    34.                 temp=A[j-1];
    35.                 A[j-1]=A[j];
    36.                 A[j]=temp;
    37.             }
    38.         }
    39.         printf("\n Ket qua lan:%d", i);
    40.         In(A,n);
    41.     }
    42. }
    43. void In(int *A, int n){
    44.     register int i;
    45.     for(i=0;i<n;i++)
    46.         printf("%5d",A[i]);
    47.     delay(1000);
    48. }
    49. void main(void){
    50.     int *A,n, X, k;clrscr();
    51.     printf("\n Nhap n="); scanf("%d",&n);
    52.     printf(“\n Sè cÇn t×m X=”); scanf(“%d”,&X);
    53.     A=(int *) malloc(n*sizeof(int));
    54.     Init(A,n);Bubble(A,n); k= Binary_Search(A, X, n);
    55.     if ( k>0)
    56.         printf (“\n %d ë vÞ trÝ sè %d”, X, k);
    57.     else
    58.         printf(“\n %d kh«ng thuéc d·y”);
    59.     getch();
    60.     free(A);
    61. }
    Download code tìm kiếm nhị phân miễn phí

    Bài đăng phổ biến

    Bài viết mới nhất

    Tin học cơ bản - Nền tảng của mọi kỹ năng

    Mọi thông tin trên blog đều được giữ bản quyền bởi Tin học cơ bản. Các bạn nếu muốn lấy thông tin từ blog vui lòng ghi rõ nguồn Tinhoccoban.net

    TIN HỌC CƠ BẢN