typedef struct ElemType {
    char data[16];
    int key;
} ElemType;

#include <stdbool.h>

void BubbleSortBothWay(ElemType A[], int n) {
    int i, j;
    ElemType swap;
    bool flag;
    for (i = 0; i < n - 1; i++) {
        flag = true;
        if (i % 2 == 0) {
            for (j = i + 1; j < n; j++) {
                if (A[j - 1].key > A[j].key) {
                    flag = false;
                    swap = A[j];
                    A[j] = A[j - 1];
                    A[j - 1] = swap;
                }
            }

        } else {
            for (j = n - 1; j > i; j--) {
                if (A[j - 1].key > A[j].key) {
                    flag = false;
                    swap = A[j];
                    A[j] = A[j - 1];
                    A[j - 1] = swap;
                }
            }
        }
        if (flag) { return; }
    }
}

void BubbleSortDual(ElemType A[], int n) {
    int low = 0, high = n - 1, i;
    ElemType swap;
    bool flag = true;
    while (low < high && flag) {
        flag = false;
        for (i = low; i < high; i++) {
            if (A[i].key > A[i + 1].key) {
                swap = A[i];
                A[i] = A[i + 1];
                A[i + 1] = swap;
                flag = true;
            }
        }
        high--;
        for (i = high; i > low; i--) {
            if (A[i].key < A[i - 1].key) {
                swap = A[i];
                A[i] = A[i - 1];
                A[i - 1] = swap;
                flag = true;
            }
        }
        low++;
    }
}