×

Cài đặt thuật toán Tim Sort trong lập trình

Avatar of admin
admin 0 Views

Thuật toán Tim Sort là sự kết hợp giữa hai thuật toán nổi tiếng: Merge Sort và Insertion Sort, được phát minh bởi Tim Peters vào năm 2002. Thuật toán này đã được sử dụng rộng rãi trong các ngôn ngữ lập trình như Python và Java, nhờ vào hiệu suất và tính hiểu quả của nó cho nhiều trường hợp khác nhau. Bài viết này sẽ hướng dẫn chi tiết cách cài đặt thuật toán này trong lập trình, cũng như giới thiệu các khái niệm và công đoạn cần thiết.

Nguyên lý hoạt động của Tim Sort

Đầu tiên, cần hiểu cơ chế hoạt động của Tim Sort:

  1. Phân đoạn nhỏ (Runs): Thuật toán bắt đầu bằng việc chia nhỏ mảng cần sắp xếp thành các đoạn nhỏ đã được sắp xếp sẵn hoặc gần như sắp xếp sẵn, tên là "runs". Kích thước của mỗi run thường được xác định trước, gọi là MIN_RUN.
  2. Sắp xếp chèn (Insertion Sort): Sau khi phân chia thành các run nhỏ, mỗi run sẽ được sắp xếp bằng thuật toán Insertion Sort.
  3. Trộn đoạn (Merge): Sau khi tất cả các run đã được sắp xếp, chúng sẽ được trộn lại với nhau bằng cách sử dụng thuật toán Merge Sort.

Tim Sort tận dụng các khối dữ liệu có sẵn trong mảng ban đầu, làm giảm số lượng các lần trộn cần thiết và do đó nâng cao hiệu suất.

Cài đặt Tim Sort trong Python

Cùng xem qua việc triển khai thuật toán Tim Sort trong Python.

def binary_insertion_sort(array, left, right):
    for i in range(left + 1, right + 1):
        key = array[i]
        j = i - 1
        while j >= left and array[j] > key:
            array[j + 1] = array[j]
            j -= 1
        array[j + 1] = key

def merge(array, l, m, r):
    len1, len2 = m - l + 1, r - m
    left, right = [], []
    for i in range(0, len1):
        left.append(array[l + i])
    for i in range(0, len2):
        right.append(array[m + 1 + i])
    i, j, k = 0, 0, l
    while i < len1 and j < len2:
        if left[i] <= right[j]:
            array[k] = left[i]
            i += 1
        else:
            array[k] = right[j]
            j += 1
        k += 1
    while i < len1:
        array[k] = left[i]
        k += 1
        i += 1
    while j < len2:
        array[k] = right[j]
        k += 1
        j += 1

def tim_sort(array):
    MIN_RUN = 32
    n = len(array)
    
    for i in range(0, n, MIN_RUN):
        binary_insertion_sort(array, i, min((i + MIN_RUN - 1), n - 1))
    
    size = MIN_RUN
    while size < n:
        for left in range(0, n, 2 * size):
            mid = min((n - 1), (left + size - 1))
            right = min((left + 2 * size - 1), (n - 1))
            merge(array, left, mid, right)
        size = 2 * size

# Ví dụ sử dụng
array = [5, 21, 7, 23, 19]
tim_sort(array)
print(array)  # Output: [5, 7, 19, 21, 23]

Giải thích cài đặt

  1. binary_insertion_sort: Đây là phiên bản của thuật toán Insertion Sort, sắp xếp các phần tử của mảng trong một khoảng từ left đến right.
  2. merge: Hàm này trộn hai nửa đã được sắp xếp của mảng lại thành một mảng lớn hơn.
  3. tim_sort: Hàm chính của thuật toán, đầu tiên sẽ chia mảng thành các run và sau đó sắp xếp chúng bằng binary_insertion_sort. Tiếp theo, nó trộn các phân đoạn nhỏ đã sắp xếp bằng hàm merge.

Kết luận

Thuật toán Tim Sort là một lựa chọn tuyệt vời cho việc sắp xếp mảng trong lập trình, nhờ vào sự kết hợp khéo léo giữa Merge Sort và Insertion Sort. Hy vọng qua bài viết này, bạn sẽ có cái nhìn rõ ràng và cụ thể hơn về cách cài đặt và sử dụng thuật toán này trong thực tế.

Comments

Bài viết liên quan