template<class T>
void swap(T* x, int i, int j) {
    T tmp;
    tmp = x[i]; x[i] = x[j]; x[j] = tmp;
}
 
template<class T>
void ShakerSort(T* x) {
    int last = n-1;
    int left = 1, right = n-1;
 
    /* основной цикл до тех пор пока границы
       отсортированных с разных сторон отрезков
       не пересекутся */
    do {
        /* проход снизу вверх */
        for (int j = right; j > 0; j--) {
            if (x[j-1] > x[j]) {
                swap(x, j-1, j);
                last = j;
            }
        }
 
        /* Корректируем нижнюю границу
           до которой уже все элементы получились
           отсортироваными */
        left = last + 1;
 
        /* проход сверху вниз */
        for (int j = 1; j <= right; j++) {
            if (x[j-1] > x[j]) {
                swap(x, j-1, j);
                last = j;
            }
        }
 
        /* Корректируем верхнюю границу
           после которой уже все элементы получились
           отсортироваными */
        right = last - 1;
    } while (left < right);
}