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.
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.
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)
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]
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.
