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

Mô tả thuật toán Merge Sort

Thuật toán Merge Sort là một thuật toán sắp xếp đệ quy dựa trên việc chia đôi và trộn mảng. Nó hoạt động bằng cách chia mảng ban đầu thành hai mảng con, sau đó đệ quy sắp xếp từng mảng con đó và sau đó trộn hai mảng con đó lại với nhau để tạo ra một mảng con đã sắp xếp. Thuật toán Merge Sort có hiệu suất tốt nhất trong số các thuật toán sắp xếp với độ phức tạp thời gian O(n log n).

Thuật toán Merge Sort có ba bước chính:

1. Chia đôi mảng: Thuật toán chia mảng ban đầu thành hai mảng con bằng cách tìm chỉ số trung tâm của mảng.
2. Sắp xếp các mảng con: Đệ quy sắp xếp từng mảng con bằng cách tiếp tục chia đôi đến khi chỉ còn một phần tử trong mảng con đó. Khi đó, mảng con đó đã được sắp xếp theo định dạng đơn giản.
3. Trộn các mảng con đã sắp xếp: Trộn hai mảng con đã sắp xếp với nhau bằng cách so sánh phần tử đầu tiên của từng mảng con, chọn phần tử nhỏ hơn và đẩy nó vào mảng kết quả. Tiếp tục thực hiện việc so sánh và đẩy phần tử vào mảng kết quả cho đến khi một trong hai mảng con đã được hoàn thành. Khi đó, chúng ta đẩy toàn bộ phần tử của mảng con còn lại vào mảng kết quả.

Ví dụ về thuật toán Merge Sort

Giả sử chúng ta có một mảng số nguyên chưa sắp xếp như sau: [38, 27, 43, 3, 9, 82, 10]. Áp dụng thuật toán Merge Sort để sắp xếp mảng này theo thứ tự tăng dần:

1. Chia đôi mảng ban đầu thành hai mảng con: [38, 27, 43, 3] và [9, 82, 10].
2. Đệ quy sắp xếp từng mảng con: Chúng ta tiếp tục chia đôi và đệ quy sắp xếp từng mảng con, ta được:

Mảng [38, 27, 43, 3] sau khi sắp xếp: [3, 27, 38, 43]

Mảng [9, 82, 10] sau khi sắp xếp: [9, 10, 82]

3. Trộn các mảng con đã sắp xếp: Trộn hai mảng con đã sắp xếp với nhau bằng cách so sánh phần tử đầu tiên của từng mảng con, chọn phần tử nhỏ hơn và đẩy nó vào mảng kết quả. Tiếp tục thực hiện việc so sánh và đẩy phần tử vào mảng kết quả cho đến khi một trong hai mảng con đã được hoàn thành. Khi đó, chúng ta đẩy toàn bộ phần tử của mảng con còn lại vào mảng kết quả.

Kết quả sau khi trộn hai mảng con đã sắp xếp là: [3, 9, 10, 27, 38, 43, 82]. Đó là mảng đã được sắp xếp theo thứ tự tăng dần.

Độ phức tạp của thuật toán Merge Sort

Thuật toán Merge Sort có độ phức tạp thời gian là O(n log n) trong trường hợp tốt nhất, trung bình và trong trường hợp xấu nhất. Độ phức tạp không gian là O(n). Do đó, Merge Sort là một trong những thuật toán sắp xếp hiệu quả nhất.

Cài đặt Thuật toán Merge Sort trên Python

Merge Sort là một thuật toán sắp xếp đệ quy hiệu quả với độ phức tạp trung bình O(nlogn). Thuật toán sử dụng kỹ thuật chia để trị để sắp xếp một mảng bằng cách chia thành hai phần, sắp xếp các phần đó đệ quy, và sau đó trộn các phần đã sắp xếp lại.

Cài đặt thuật toán Merge Sort bằng Python như sau:

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]

        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0

        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

    return arr

Hàm merge_sort sẽ nhận vào một mảng arr và sắp xếp nó theo thứ tự tăng dần bằng cách sử dụng thuật toán Merge Sort. Thuật toán sử dụng đệ quy để chia mảng thành các phần nhỏ hơn, sau đó trộn các phần đã sắp xếp lại để tạo thành một mảng đã sắp xếp. Thuật toán này không chỉ hiệu quả về mặt thời gian mà còn được sử dụng rộng rãi trong các ứng dụng thực tế.