Chương trình Python QuickSort

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 thuật toán QuickSort.

Ở đây ta phân hoạch (partition) mảng và sắp xếp các phân hoạch riêng biệt đểได้ mảng đã sắp xếp.

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

Ví dụ

# hàm phân hoạch
def partition(arr, low, high):
    i = (low - 1)
    pivot = arr[high]  # phần tử chốt
    for j in range(low, high):
        # nếu phần tử hiện tại nhỏ hơn pivot
        if arr[j] <= pivot:
            i = i + 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return (i+1)

# sắp xếp
def quickSort(arr, low, high):
    if low < high:
        # chỉ số phân hoạch
        pi = partition(arr, low, high)
        # sắp xếp 2 phân hoạch
        quickSort(arr, low, pi-1)
        quickSort(arr, pi+1, high)

# main
arr = [2, 5, 3, 8, 6, 5, 4, 7]
n = len(arr)
quickSort(arr, 0, n-1)
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: 2 3 4 5 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 QuickSort.