MERGESORT

MERGESORT

MergeSort là một giải thuật hay, chia nhỏ dãy đầu vào,  sử dụng phương pháp trộn 2 dãy đã được sắp xếp. Ở đây mình xin giới thiệu source code kèm theo hướng dẫn.

CODE (C++)

void MergeSort(int A[], int L, int R)
          // *** Sắp xếp mảng A, gồm N phần tử bằng giải thuật MergeSort
          // *** Ý tưởng: Ta chia dãy số thành 2 dãy, sau trộn hai dãy này thành 1 dãy, dãy này là kết quả,
          //   hai dãy được chia phải được sắp xếp, để đảm bảo điều này,
          //      ta xem mỗi dãy là 1 dãy mới và cũng chia nhỏ như dãy ban đầu, đến khi dãy chia nhỏ đã sắp xếp
{
          if (L < R) // Nếu L == R, xem như dãy đầu vào có 1 phần tử, và dãy này đã được sắp xếp.
          {
                    int K = (L + R) / 2;
                    // Chia dãy đầu vào thành 2 dãy mới
                   MergeSort(A, L, K);
                   MergeSort(A, K + 1, R);
                  //Trộn hai dãy trên thành 1 dãy, trong đó trong đó vị trí phân cách giữa hai dãy
                  //                   ngầm định là K = (L + R) / 2
                  Merge(A, L, R);
          }
}

void Merge(int A[], int L ,int R)
          // *** Trộn hai dãy nằm kề nhau và được phân cách ngầm định là K = (L + R) / 2
          // *** Ý tưởng: Ta lần lượt duyệt các phần tử của cả hai dãy,
          //          ở mỗi lượt duyệt ta duyệt hai phần tử 1 của dãy I, 1 của dãy II
          //          so sánh 2 phần tử và lấy ra phần tử nhỏ hơn bỏ vào dãy Kết Quả,
          //          cứ như vậy 2 dãy được trộn với nhau
{
          // Vì trộn dãy không mang tính tự đổi chỗ, nên ta phải dùng một mảng trung gian,
          //          ở đây ta dùng mảng B là mảng chứa dãy cần trộn, A là mảng lưu dãy đã được trộn
          int B[MAXSL] = {};
          for (int u = L; u <= R; u++)
                    B[u] = A[u];

          int K = (L + R) / 2;
          int i = L;
          int j = K + 1;
          int t = L - 1;
          // Trộn hai dãy
          while (t < R)
          {
                    if ((B[i] <= B[j] || j == R + 1) && i != K + 1)
                    {
                              t++;
                              A[t] = B[i];
                              i++;
                    }
                    if ((B[i] > B[j] || i == K + 1) && j != R + 1)
                    {
                              t++;
                              A[t] = B[j];
                              j++;
                    }
          }
}

Các bạn có thể tải hoặc xem code tường minh hơn ở đây

Ngựa Sông