Cài đặt thuật toán Cocktail Shaker Sort trong lập trình

Cocktail Shaker Sort là một thuật toán sắp xếp có nhiều điểm tương đồng với Bubble Sort. Điểm khác biệt lớn nhất của thuật toán này là thay vì chỉ đi theo một hướng, Cocktail Shaker Sort đi qua lại trong dãy số, tức là nó thực hiện việc sắp xếp theo hai chiều.

Nguyên lý hoạt động

Cocktail Shaker Sort dựa trên nguyên tắc “bong bóng nổi”, tương tự như Bubble Sort. Tuy nhiên, thay vì chỉ đi từ đầu đến cuối danh sách và sau đó lặp lại từ đầu, thuật toán này đi từ đầu đến cuối và sau đó ngược lại từ cuối lên đầu. Quy trình này tiếp diễn cho đến khi danh sách được sắp xếp hoàn toàn.

Các bước thực hiện

1. Khởi tạo các biến cho phép duyệt qua lại trong dãy số.
2. Bắt đầu từ đầu danh sách, so sánh từng cặp phần tử liền kề và hoán đổi chúng nếu chúng không theo thứ tự mong muốn.
3. Khi đến cuối danh sách, đổi hướng di chuyển và thực hiện so sánh các cặp phần tử ngược lại.
4. Lặp lại quá trình này cho đến khi không còn cần thực hiện hoán đổi nào nữa.

Ví dụ cài đặt

Dưới đây là minh họa cách cài đặt Cocktail Shaker Sort bằng ngôn ngữ lập trình Python:

def cocktail_shaker_sort(arr):
    n = len(arr)
    swapped = True
    start = 0
    end = n - 1
    while swapped:
        swapped = False
        # Đi từ trái sang phải
        for i in range(start, end):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                swapped = True
        # Nếu không có phần tử nào được hoán đổi, danh sách đã được sắp xếp
        if not swapped:
            break
        swapped = False
        end -= 1
        # Đi từ phải sang trái
        for i in range(end - 1, start - 1, -1):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                swapped = True
        start += 1
    return arr

# Ví dụ sử dụng
arr = [5, 1, 4, 2, 8, 0, 2]
sorted_arr = cocktail_shaker_sort(arr)
print("Mảng sau khi được sắp xếp:", sorted_arr)

Đánh giá thuật toán

Ưu điểm:

• Dễ hiểu và dễ triển khai.
• Tốt hơn Bubble Sort: So với Bubble Sort, Cocktail Shaker Sort thường hoạt động hiệu quả hơn vì nó có thể loại bỏ các phần tử đã được sắp xếp không chỉ ở một đầu của dãy mà ở cả hai đầu.

Nhược điểm:

• Hiệu suất thấp: Với độ phức tạp thời gian O(n^2), thuật toán này không hiệu quả đối với các dãy số lớn so với các thuật toán sắp xếp nâng cao như Quick Sort hoặc Merge Sort.
• Tính ứng dụng hạn chế: Thường chỉ được sử dụng trong các ứng dụng đơn giản hoặc giáo dục để minh họa nguyên tắc cơ bản của thuật toán sắp xếp.

Kết luận

Cocktail Shaker Sort là một biến thể cải tiến của Bubble Sort với khả năng xử lý hiệu quả hơn đối với các trường hợp đã gần như được sắp xếp. Tuy nhiên, do độ phức tạp O(n^2), thuật toán này không thích hợp cho các ứng dụng đòi hỏi khả năng xử lý cao. Tuy nhiên, nó vẫn là một giải pháp tốt để hiểu về các thuật toán sắp xếp đi từ cơ bản đến nâng cao.