Chương trình C++ cho thuật toán Cocktail Sort (Phiên bản 2)

Cocktail Sort (Shaker Sort) là biến thể Bubble Sort duyệt hai chiều luân phiên. Bubble Sort chỉ đẩy phần tử lớn về cuối; Cocktail Sort đẩy lớn về cuối, rồi đẩy nhỏ về đầu.

Thuật toán

cocktail(array, n):
    flag = true
    start = 0, end = n-1
    while flag:
        flag = false
        // Xuôi: trái -> phải
        for i = start to end-1:
            if arr[i] > arr[i+1]: swap; flag = true
        if not flag: break
        flag = false
        end--
        // Ngược: phải -> trái
        for i = end-1 downto start:
            if arr[i] > arr[i+1]: swap; flag = true
        start++
    end while
end

Code ví dụ

#include <iostream>
#include <algorithm>
using namespace std;

void cocktailSort(int arr[], int n) {
    bool flag = true;
    int start = 0, end = n - 1;
    
    while (flag) {
        flag = false;
        // Pass xuôi (left to right)
        for (int i = start; i < end; i++) {
            if (arr[i] > arr[i+1]) {
                swap(arr[i], arr[i+1]);
                flag = true;
            }
        }
        if (!flag) break; // Đã sắp xếp xong
        
        flag = false;
        end--; // Phần tử cuối đã đúng vị trí
        
        // Pass ngược (right to left)
        for (int i = end - 1; i >= start; i--) {
            if (arr[i] > arr[i+1]) {
                swap(arr[i], arr[i+1]);
                flag = true;
            }
        }
        start++; // Phần tử đầu đã đúng vị trí
    }
}

int main() {
    int data[] = {54, 74, 98, 154, 98, 32, 20, 13, 35, 40};
    int n = sizeof(data)/sizeof(data[0]);
    
    cout << "Day truoc: ";
    for(int x : data) cout << x << " ";
    
    cocktailSort(data, n);
    
    cout << "\nDay sau:  ";
    for(int x : data) cout << x << " ";
    return 0;
}

Kết quả

Day truoc: 54 74 98 154 98 32 20 13 35 40
Day sau:  13 20 32 35 40 54 74 98 98 154

Độ phức tạp

• Thời gian: O(n²) trung bình/xấu nhất, O(n) tốt nhất (đã sắp xếp).
• Không gian: O(1).
• Ổn định: Có.

So sánh với Bubble Sort

Cocktail Sort tốt hơn Bubble Sort khi có nhiều phần tử nhỏ ở cuối mảng (turtles problem).