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 QuickSortแบบ lặp (iterative).
Phân hoạch mảng và sắp xếp các phân hoạch riêng biệt.
Hãy quan sát giải pháp trong triển khai dưới đây:
Ví dụ
# cách lặp
def partition(arr, l, h):
i = (l - 1)
x = arr[h]
for j in range(l, h):
if arr[j] <= x:
i = i + 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[h] = arr[h], arr[i+1]
return (i+1)
# sort
def quickSortIterative(arr, l, h):
# tạo stack
size = h - l + 1
stack = [0] * (size)
top = -1
# push giá trị đầu
top = top + 1
stack[top] = l
top = top + 1
stack[top] = h
# pop từ stack
while top >= 0:
h = stack[top]
top = top - 1
l = stack[top]
top = top - 1
# đặt pivot đúng vị trí
p = partition(arr, l, h)
# phần tử bên trái
if p-1 > l:
top = top + 1
stack[top] = l
top = top + 1
stack[top] = p - 1
# phần tử bên phải
if p+1 < h:
top = top + 1
stack[top] = p + 1
top = top + 1
stack[top] = h
# main
arr = [2, 5, 3, 8, 6, 5, 4, 7]
n = len(arr)
quickSortIterative(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 Iterative Quick Sort.