CNTT K25
Bạn có muốn phản ứng với tin nhắn này? Vui lòng đăng ký diễn đàn trong một vài cú nhấp chuột hoặc đăng nhập để tiếp tục.

Thuật toán sắp xếp trộn (Merge Sort)

2 posters

Go down

Thuật toán sắp xếp trộn (Merge Sort) Empty Thuật toán sắp xếp trộn (Merge Sort)

Bài gửi by hosytan 9/5/2013, 15:54

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.

3. Mã thực thi (tựa 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];
}

4. Ví dụ
X = {7, 2, 5, 4, 1, 3, 8, 6}
Dãy ban đầu: 7, 2, 5, 4, 1, 3, 8, 6
Từ dãy ban đầu, chia làm 2 đoạn con {7, 2, 5, 4} và {1, 3, 8, 6}
Chia tiếp làm các đoạn con X1 = {7, 2}, X2 = {5, 4} và X3 = {1, 3}, X4 = {8, 6}
Merge từng đoạn ta được X1 = {2, 7}, X2 = {4, 5} và X3 = {1, 3}, X4 = {6, 8}
Merge(X1+X2), Merge(X3+X4) ta được X5 = {2, 4, 5, 7} và X6 = {1, 3, 6, 8}
Merge(X5+X6) ta được {1, 2, 3, 4, 5, 6, 7 ,8}

Cuối cùng ta có 1, 2, 3, 4, 5, 6, 7, 8, dãy đã được sắp xếp.


hosytan
hosytan

Tổng số bài gửi : 29
Join date : 02/05/2013

Về Đầu Trang Go down

Thuật toán sắp xếp trộn (Merge Sort) Empty Re: Thuật toán sắp xếp trộn (Merge Sort)

Bài gửi by hbs315 17/12/2013, 16:35

Mình xin góp phần với code C# của thuật toán merge sort:

Thuật toán sắp xếp trộn (Merge Sort) Ug4i

hbs315

Tổng số bài gửi : 8
Join date : 13/12/2013

Về Đầu Trang Go down

Thuật toán sắp xếp trộn (Merge Sort) Empty Re: Thuật toán sắp xếp trộn (Merge Sort)

Bài gửi by hbs315 4/1/2014, 09:17

Để dễ hiểu Thuật toán sắp xếp trộn chúng ta nên biết thuật ngữ trộn(merge):
Trộn (merge)
Giả sử có 2 mảng được sắp xếp A1[a...n] và A2[b...m] khi ta trộn (merge) 2 mảng thành một mảng mới A3[a...(n+m)]
- So sánh 2 phần từ đầu của 2 mảng, lấy phần bé hơn cho vào mảng mới, làm như vậy cho đến khi một trong 2 mảng trở thành rỗng.
- Cho phần còn lại của mảng kia vào cuối danh sách

hbs315

Tổng số bài gửi : 8
Join date : 13/12/2013

Về Đầu Trang Go down

Thuật toán sắp xếp trộn (Merge Sort) Empty Re: Thuật toán sắp xếp trộn (Merge Sort)

Bài gửi by Sponsored content


Sponsored content


Về Đầu Trang Go down

Về Đầu Trang

- Similar topics

 
Permissions in this forum:
Bạn không có quyền trả lời bài viết