Chương trình C++ thực hiện Shaker Sort (Cocktail Sort)

Shaker Sort (còn gọi là Cocktail Sort) được dùng để sắp xếp dữ liệu. Khác với Bubble Sort, Shaker Sort sắp xếp mảng theo cả hai hướng. Độ phức tạp xấu nhất của thuật toán này là O(n²).

Thuật toán

Bắt đầu
  Hàm ShakerSort() có 'arr' mảng dữ liệu và 'n' số lượng giá trị.
  Triển khai thuật toán sắp xếp bằng vòng lặp lồng nhau.
  Vòng lặp cha chạy 'i' từ 0 đến n-1 và chứa hai vòng lặp bên trong.
  Vòng lặp đầu chạy 'j' từ i+1 đến n-1 và dùng swap() nếu a[j] < a[j-1].
  Giảm n.
  Vòng lặp thứ hai chạy 'k' từ m-1 xuống i+1 và dùng swap() nếu a[k] < a[k-1].
  Tăng i.
Kết thúc

Mã ví dụ

#include <iostream>
using namespace std;

void swap(int *a, int *b) {
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

void ShakerSort(int a[], int m) {
    int i, j, k;
    for (i = 0; i < m;) {
        for (j = i+1; j < m; j++) {
            if (a[j] < a[j-1])
                swap(&a[j], &a[j-1]);
        }
        m--;
        for (k = m-1; k > i; k--) {
            if (a[k] < a[k-1])
                swap(&a[k], &a[k-1]);
        }
        i++;
    }
}

int main() {
    int n, i;
    cout << "\nNhập số lượng phần tử dữ liệu cần sắp xếp: ";
    cin >> n;
    int a[n];
    for (i = 0; i < n; i++) {
        cout << "Nhập phần tử " << i+1 << ": ";
        cin >> a[i];
    }
    ShakerSort(a, n);
    cout << "\nDữ liệu đã sắp xếp ";
    for (i = 0; i < n; i++)
        cout << "->" << a[i];
    return 0;
}

Kết quả

Nhập số lượng phần tử dữ liệu cần sắp xếp: 4
Nhập phần tử 1: 3
Nhập phần tử 2: 1
Nhập phần tử 3: 7
Nhập phần tử 4: 6
Dữ liệu đã sắp xếp ->1->3->6->7