Thuật toán Shell Sort trong Python

Shell Sort là một thuật toán sắp xếp cải tiến dựa trên việc sử dụng một kỹ thuật gọi là “gaps” để sắp xếp các phần tử trong một danh sách. Thuật toán này được đặt theo tên của nhà khoa học máy tính Donald Shell, người đã phát triển nó vào năm 1959. Shell Sort là một thuật toán sắp xếp không tuần tự (non-comparison sort) và có hiệu suất tốt hơn so với thuật toán sắp xếp đơn giản như Bubble Sort và Insertion Sort.

Nguyên Tắc Hoạt Động

Shell Sort hoạt động bằng cách chia danh sách thành nhiều nhóm nhỏ hơn dựa trên khoảng cách (gap) giữa các phần tử. Sau đó, nó sắp xếp từng nhóm bằng cách sử dụng thuật toán sắp xếp chèn (Insertion Sort). Khi khoảng cách giảm dần (thường là giảm theo một hệ số), thuật toán sẽ tiếp tục sắp xếp cho đến khi khoảng cách bằng 1, lúc này thuật toán sẽ thực hiện một lần sắp xếp chèn cuối cùng cho toàn bộ danh sách.

Các Bước Cơ Bản của Giải Thuật

1. Chọn một khoảng cách (gap): Bắt đầu với một giá trị gap lớn hơn 1 và giảm dần đến 1.
2. Sắp xếp các phần tử theo gap: Duyệt qua các phần tử ở các chỉ số cách nhau một khoảng gap và thực hiện sắp xếp chèn trên chúng.
3. Lặp lại cho đến khi gap bằng 1: Khi gap bằng 1, thuật toán sẽ sắp xếp toàn bộ danh sách.

Ví Dụ Mã Nguồn Shell Sort trong Python

Dưới đây là một ví dụ chi tiết về cách cài đặt thuật toán Shell Sort trong Python:

def shell_sort(arr):
    n = len(arr)
    gap = n // 2  # Bắt đầu với khoảng cách là n/2

    # Tiến hành lặp qua khoảng cách
    while gap > 0:
        # Sắp xếp các phần tử theo gap
        for i in range(gap, n):
            # Lưu giá trị hiện tại
            temp = arr[i]
            j = i
            
            # Di chuyển các phần tử arr[j - gap] đến vị trí phù hợp
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            
            # Đặt giá trị vào vị trí phù hợp
            arr[j] = temp
        
        # Giảm khoảng cách
        gap //= 2

# Sử dụng hàm shell_sort
if __name__ == "__main__":
    data = [12, 34, 54, 2, 3]
    print("Danh sách ban đầu:", data)
    shell_sort(data)
    print("Danh sách sau khi sắp xếp:", data)

Kết Quả

Khi bạn chạy đoạn mã trên, đầu ra sẽ là:

Danh sách ban đầu: [12, 34, 54, 2, 3]
Danh sách sau khi sắp xếp: [2, 3, 12, 34, 54]

Đánh Giá Hiệu Suất

• Thời gian trung bình: O(n log n) trong trường hợp tốt nhất, O(n^2) trong trường hợp xấu nhất.
• Không gian: O(1) vì thuật toán này là sắp xếp tại chỗ (in-place).
• Tính ổn định: Shell Sort không ổn định (stable), vì hai phần tử bằng nhau có thể đổi chỗ cho nhau trong quá trình sắp xếp.

Kết Luận

Shell Sort là một thuật toán sắp xếp hiệu quả cho danh sách nhỏ và có thể dễ dàng cài đặt trong Python. Mặc dù có một số thuật toán sắp xếp khác nhanh hơn cho các danh sách lớn, Shell Sort vẫn hữu ích trong các tình huống cụ thể và là một thuật toán quan trọng để học hỏi trong lĩnh vực thuật toán.