Chương trình Python Stooge Sort

Trong bài viết này, chúng ta sẽ tìm hiểu giải pháp cho bài toán sau:

Đề bài – Cho một mảng, cần sắp xếp nó bằng thuật toán Stooge Sort.

Thuật toán

1. Kiểm tra nếu giá trị index 0 > index cuối, đổi chỗ.
2. Sắp xếp 2/3 đầu mảng.
3. Sắp xếp 2/3 cuối mảng.
4. Sắp xếp lại 2/3 đầu để xác nhận.

Hãy quan sát giải pháp trong triển khai dưới đây:

Ví dụ

def stoogesort(arr, l, h):
    if l >= h:
        return
    # đổi chỗ
    if arr[l] > arr[h]:
        t = arr[l]
        arr[l] = arr[h]
        arr[h] = t
    # hơn 2 phần tử
    if h - l + 1 > 2:
        t = int((h - l + 1) / 3)
        # sắp xếp 2/3 đầu
        stoogesort(arr, l, h - t)
        # sắp xếp 2/3 cuối
        stoogesort(arr, l + t, h)
        # sắp xếp lại 2/3 đầu
        stoogesort(arr, l, h - t)

# main
arr = [1, 4, 2, 3, 6, 5, 8, 7]
n = len(arr)
stoogesort(arr, 0, n-1)
print("Dãy đã sắp xếp:")
for i in range(n):
    print(arr[i], end=" ")

Kết quả

Dãy đã sắp xếp: 1 2 3 4 5 6 7 8

Kết luận

Trong bài này, chúng ta đã học cách làm chương trình Python Stooge Sort.