Chương trình Python Cocktail 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 list, cần thực hiện Bitonic Sort (Cocktail Sort) và hiển thị list.

Cocktail Sort – Sắp xếp như Bubble Sort nhưng lặp 2 chiều.

Thuật toán

Duyệt trái sang phải, so sánh cặp liền kề, đổi chỗ theo điều kiện. Phần tử lớn nhất về cuối. Duyệt ngược lại, phần tử nhỏ nhất về đầu.

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

Ví dụ

def cocktailSort(a):
    n = len(a)
    flag = True
    start = 0
    end = n-1
    while (flag == True):
        flag = False
        # trái sang phải
        for i in range(start, end):
            if (a[i] > a[i+1]):
                a[i], a[i+1] = a[i+1], a[i]
                flag = True
        # nếu không swap -> đã sort
        if (flag == False):
            break
        flag = False
        # phần tử cuối đã sort
        end = end - 1
        # phải sang trái
        for i in range(end-1, start-1, -1):
            if (a[i] > a[i+1]):
                a[i], a[i+1] = a[i+1], a[i]
                flag = True
        # phần tử đầu đã sort
        start = start + 1

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

Kết quả

Mảng đã sắp xếp: 2 3 3 4 4 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 Cocktail Sort.