Chương trình Python Cycle 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 dùng Cycle Sort.

Thuật toán in-place, hoán đổi bằng cách tạo chu trình (cycle).

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

Ví dụ

def cycleSort(array):
    writes = 0
    # các chu trình cần xoay
    for cycleStart in range(0, len(array) - 1):
        item = array[cycleStart]
        # vị trí đặt item
        pos = cycleStart
        for i in range(cycleStart + 1, len(array)):
            if array[i] < item:
                pos += 1
        # nếu item đã ở đúng vị trí, không phải chu trình
        if pos == cycleStart:
            continue
        # đặt item
        while item == array[pos]:
            pos += 1
        array[pos], item = item, array[pos]
        writes += 1
        # tiếp tục xoay
        while pos != cycleStart:
            pos = cycleStart
            for i in range(cycleStart + 1, len(array)):
                if array[i] < item:
                    pos += 1
            while item == array[pos]:
                pos += 1
            array[pos], item = item, array[pos]
            writes += 1
    return writes

# main
arr = [1, 5, 3, 4, 8, 6, 3, 4, 5]
n = len(arr)
cycleSort(arr)
print("Mảng đã sắp xếp:")
for i in range(n):
    print(arr[i], end=" ")

Kết quả

Mảng đã sắp xếp: 1 3 3 4 4 5 5 6 8

Kết luận

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