Đánh giá thuật toán merge sort năm 2024

là một trong những thuật toán có độ phức tạp ở mức trung bình và cùng sử dụng phương pháp chia để trị giống thuật toán sắp xếp nhanh Quicksort rồi gọi đệ quy chính nó trên các phân vùng đã chia. Thuật toán này không chỉ áp dụng trong sắp xếp mà còn ở nhiều bài toán khác. Sự khác biệt chính là Quicksort là thuật toán sắp xếp nội (internal), tại chỗ (in-place) trong khi đó Merge Sort lại là thuật toán sắp xếp ngoại (external), không tại chỗ (not-in-place).

Cài đặt

Thuật toán này chia mảng cần sắp xếp thành 2 nửa. Với phương thức mergeSort(), tiếp tục lặp lại việc này ở các nửa mảng đã chia cho đến khi chỉ còn 1 phần tử. Sau cùng gộp lại thành mảng đã sắp xếp. Phương thức merge() là tiến trình quan trọng nhất, được sử dụng để gộp hai nửa mảng thành 1 mảng duy nhất đã được sắp xếp.

Khởi đầu với phương thức mergeSort():

public static void mergeSort(int[] array, int low, int high) {     if (high <= low) return;     int mid = low + (high - low) / 2;     mergeSort(array, low, mid);     mergeSort(array, mid+1, high);     merge(array, low, mid, high); }

Phần này khá đơn giản, chúng ta có 1 mảng cần được sắp xếp, các con trỏ ở vị trí đầu và cuối. Nếu con trỏ ở vị trí cuối nhỏ hơn hoặc bằng vị trí con trỏ ở đầu thì trả về.

Mặt khác, chúng ta sẽ phân vùng mảng thành 2 nửa, gọi phương thức mergeSort() từ đầu đến giữa và từ giữa đến cuối.

Đã đăng vào thg 7 18, 2019 3:50 SA 1 phút đọc

Merge Sort

Đây là một trong các thuật toán sắp xếp cơ bản mà sinh viên thường bị hỏi khi đi phỏng vấn, cùng với các thuật toán sắp xếp khác như: quick sort, heap sort, ...

Merge sort sử dụng kĩ thuật chia để trị cho việc sắp xếp. Merge sort gồm 2 công đoạn:

• Đầu tiên nó chia dãy cần sắp xếp thành 2 nửa.
• Sau đó gộp 2 dãy đã được sắp xếp lại thành một.

def merge arr, left, mid, right
  # create temp arrays
  tempL = []
  tempR = []
  # copy data to temp arrays
  for i in left..mid do
    tempL.push(arr[i])
  end
  for i in mid+1..right do
    tempR.push(arr[i])
  end
  # merge 2 temp arrays
  i = 0
  j = 0
  k = left
  while i < tempL.length && j < tempR.length
    if tempL[i] <= tempR[j]
      arr[k] = tempL[i]
      i += 1
    else
      arr[k] = tempR[j]
      j += 1
    end
    k += 1
  end
  while i < tempL.length
    arr[k] = tempL[i]
    i += 1
    k += 1
  end
  while j < tempR.length
    arr[k] = tempR[j]
    j += 1
    k += 1
  end
end
def mergesort arr, left, right
  if left < right
    mid = (left + right) / 2
    mergesort arr, left, mid
    mergesort arr, mid + 1, right
    merge arr, left, mid, right
  end
end

Độ phức tạp thời gian trong trường hợp xấu nhất, tốt nhất, trung bình của Merge Sort đều là O(nlogn), điều này làm cho Merge Sort tỏ ra khá hiệu quả. Merge sort là một lựa chọn khi cần một thuật toán để sắp xếp có tính ổn định, khác với quick sort, không ổn định cho lắm. Nhược điểm của merge sort có thể kể đến như không hiệu quả lắm về mặt không gian, khi độ phức tạp không gian trong trường hợp xấu nhất là O(n), trong khi của quick sort là O(1)

Nguồn tham khảo : wikipedia.

All rights reserved