Triển khai thuật toán Shell Sort trong Python

Shell Sort là thuật toán sắp xếp cải tiến từ Insertion Sort. Nó sắp xếp các phần tử cách nhau một khoảng cách (gap) cụ thể, giảm dần khoảng cách này cho đến khi bằng 1 (lúc này thành Insertion Sort chuẩn).

Ví dụ triển khai

def shell_sort(arr):
    """
    Sắp xếp Shell Sort (in-place).
    Độ phức tạp trung bình: O(n log n) đến O(n^(3/2)) tùy gap sequence.
    """
    n = len(arr)
    gap = n // 2  # Khởi tạo gap = n/2
    
    while gap > 0:
        # Thực hiện insertion sort cho các sublist cách nhau gap
        for i in range(gap, n):
            temp = arr[i]
            j = i
            # Dịch chuyển các phần tử lớn hơn temp trong sublist
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 2  # Giảm gap
    return arr

# Test
my_list = [45, 31, 62, 12, 89, 5, 9, 8]
print("Danh sách trước khi sắp xếp:")
print(my_list)

sorted_list = shell_sort(my_list.copy())  # copy để giữ nguyên list gốc
print("\nDanh sách sau Shell Sort:")
print(sorted_list)

Kết quả

Danh sách trước khi sắp xếp:
[45, 31, 62, 12, 89, 5, 9, 8]

Danh sách sau Shell Sort:
[5, 8, 9, 12, 31, 45, 62, 89]

Giải thích

• Gap sequence: Bắt đầu từ n//2, giảm dần bằng chia 2 (//= 2). Đây là dãy gap gốc của Shell.
• Sublist: Với gap = k, các phần tử có chỉ số i, i+k, i+2k... tạo thành một sublist. Mỗi sublist được sắp xếp bằng insertion sort.
• In-place: Thuật toán sắp xếp trực tiếp trên mảng gốc, không cần bộ nhớ thêm.
• Độ phức tạp: Tốt hơn Insertion Sort (O(n²)) nhờ các phần tử di chuyển xa hơn qua các gap lớn.

Các dãy gap phổ biến hơn (hiệu quả hơn)

# Dãy Knuth: 1, 4, 13, 40, 121... (3*k + 1)
# Dãy Sedgewick: 1, 5, 19, 41, 109...
# Dãy Ciura (tối ưu thực nghiệm): [1, 4, 10, 23, 57, 132, 301, 701, 1750]

def shell_sort_knuth(arr):
    n = len(arr)
    # Tính gap lớn nhất theo Knuth < n
    gap = 1
    while gap < n // 3:
        gap = 3 * gap + 1
    
    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 3
    return arr

Dãy Knuth hoặc Ciura thường cho hiệu năng tốt hơn dãy Shell gốc.