Chương trình C++ cho thuật toán Cocktail Sort

Cocktail Sort là một biến thể của Bubble Sort, vừa là thuật toán sắp xếp ổn định (stable), vừa là thuật toán so sánh (comparison sort). Nó còn được gọi là Bidirectional Bubble Sort, Cocktail Shaker Sort, Shaker Sort (có thể chỉ một biến thể của Selection Sort), Ripple Sort, Shuffle Sort, hoặc Shuttle Sort. Khác với Bubble Sort chỉ duyệt một chiều, Cocktail Sort sắp xếp theo cả hai hướng trên mỗi lần duyệt qua danh sách.

Ví dụ minh họa

Input: 5 3 4 2 1
Output: 1 2 3 4 5

Giải thích

Trong Cocktail Sort, mảng sẽ bao gồm các phần tử chưa được sắp xếp. Thuật toán hoạt động theo cả hai hướng trên mỗi lần duyệt. Nó sắp xếp mảng bằng cách sử dụng Bubble Sort một lần theo chiều tiến và một lần theo chiều lùi.

Code ví dụ

#include <iostream>
using namespace std;

int main() {
    int arr[] = {5, 3, 4, 2, 1};
    int m = 5;
    int n = m, c = 0;

    do {
        // Duyệt từ trái sang phải (như Bubble Sort thông thường)
        for (int i = 0; i < n - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                // Hoán đổi không dùng biến tạm
                arr[i] = arr[i] + arr[i + 1];
                arr[i + 1] = arr[i] - arr[i + 1];
                arr[i] = arr[i] - arr[i + 1];
            }
        }
        n = n - 1;

        // Duyệt từ phải sang trái
        for (int i = m - 1; i >= c; i--) {
            if (arr[i] < arr[i - 1]) {
                arr[i] = arr[i] + arr[i - 1];
                arr[i - 1] = arr[i] - arr[i - 1];
                arr[i] = arr[i] - arr[i - 1];
            }
        }
        c = c + 1;
    } while (n != 0 && c != 0);

    for (int i = 0; i < m; i++) {
        cout << arr[i] << "\t";
    }
    return 0;
}

Độ phức tạp

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