Merge Sort

Thuật toán Merge Sort

1.      Ý tưởng:

Áp dụng mô hình chia để trị để thiết kế thuật toán sắp xếp bằng phương pháp trộn.

Chia:

Nếu mảng A rỗng hoặc chỉ có một phần tử thì trả về chính A (đã có thứ tự).

Ngược lại A được chia thành 2 mảng con A1 và A2, mỗi mảng chứa n/2 phần tử

Đệ qui:

Sắp xếp một cách đệ qui hai mảng con A1 và A2

Trị:

Tạo mảng A bằng cách trộn hai mảng đã được sắp xếp A1 và A2.

2.      Thuật toán:

Algorithm mergeSort(A, n)

            Input: Một mảng n phần tử số A

            Output: Mảng A đã được sắp xếp tăng dần.

            For i ← 0 to n/2 do

                        A1[i] = A[i]

            For i ← n/2+1 to n-1 do

                        A2[i-n/2-1] = A[i]

            mergeSort(A1,n/2)

            mergeSort(A2, n-n/2-1)

            merge(A1,A2,A)

            Return array A

                        Trộn hai mảng đã có thứ tự

Algorithm merge (A1,A2,A)

            Input: Mảng A1, A2 đã có thứ tự tăng dần.

            Output: Mảng A được hình thành từ A1, A2 và có thứ tự tăng dần.

while not(A1.isEmpty and A2.isEmpty)

            if A1[0]<=A2[0] then

                        A.insertLast(A1[0])

                        A1.removeFirst

            else

                        A.insertLast(A2[0])

                        A2.removeFirst

while not(A1.isEmpty)

            A.insertLast(A1[0])

            A1.removeFirst

while not(A2.isEmpty)

            A.insertLast(A2[0])

            A2.removeFirst

3.      Mã nguồn bằng C:

#include<stdio.h>   

#include<conio.h>

void mergeSort(int numbers[], int temp[], int array_size)

{

  m_sort(numbers, temp, 0, array_size - 1);

} 

void m_sort(int numbers[], int temp[], int left, int right)

{

  int mid;

  if (right > left)

  {

    mid = (right + left) / 2;

    m_sort(numbers, temp, left, mid);

    m_sort(numbers, temp, mid+1, right);

    merge(numbers, temp, left, mid+1, right);

  }

}

 void merge(int numbers[], int temp[], int left, int mid, int right)

{

  int i, left_end, num_elements, tmp_pos;

  left_end = mid - 1;

  tmp_pos = left;

  num_elements = right - left + 1;

  while ((left <= left_end) && (mid <= right))

  {

    if (numbers[left] <= numbers[mid])

    {

      temp[tmp_pos] = numbers[left];

      tmp_pos = tmp_pos + 1;

      left = left +1;

    }

    else

    {

      temp[tmp_pos] = numbers[mid];

      tmp_pos = tmp_pos + 1;

      mid = mid + 1;

    }

  }

  while (left <= left_end)

  {

    temp[tmp_pos] = numbers[left];

    left = left + 1;

    tmp_pos = tmp_pos + 1;

  }

  while (mid <= right)

  {

    temp[tmp_pos] = numbers[mid];

    mid = mid + 1;

    tmp_pos = tmp_pos + 1;

  }

  for (i=0; i <= num_elements; i++)

  {

    numbers[right] = temp[right];

    right = right - 1;

  }

}