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 Brick Sort.
Có 2 pha: Odd (lẻ) và Even (chẵn). Pha lẻ: bubble sort trên phần tử index lẻ. Pha chẵn: bubble sort trên phần tử index chẵn.
Hãy quan sát giải pháp trong triển khai dưới đây:
Ví dụ
def oddEvenSort(arr, n):
# cờ
isSorted = 0
while isSorted == 0:
isSorted = 1
# pha lẻ
for i in range(1, n-1, 2):
if arr[i] > arr[i+1]:
arr[i], arr[i+1] = arr[i+1], arr[i]
isSorted = 0
# pha chẵn
for i in range(0, n-1, 2):
if arr[i] > arr[i+1]:
arr[i], arr[i+1] = arr[i+1], arr[i]
isSorted = 0
return arr
arr = [1, 4, 2, 3, 6, 5, 8, 7]
n = len(arr)
oddEvenSort(arr, n)
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 Odd-Even Sort / Brick Sort.