#include <iostream>
#include <ctime>
#include <algorithm>
#include <string>
#include <sstream>
#include <chrono>

using namespace std;
using namespace std::chrono;

class Array {
    int *a, n;

    public:
    // конструктор 1
    // len – число элементов в массиве
    // t = 1 – неупорядоченный массив
    // t = 2 – массив, упорядоченный по неубыванию
    // t = 3 – массив, упорядоченный по невозрастанию
    // d – диапазон псевдослучайных чисел для неупорядоченного массива (при t = 1)
    Array(int len = 1, int d = 10, int t = 1) {
        a = new int[len];
        n = len;
        if (t == 2) {
            a[0] = rand()%d;
            for (int i = 1; i < n; i++) {
                a[i] = a[i - 1] + rand()%d;
            }
        }
        else if (t == 3) {
            a[n-1] = rand()%d;
            for (int i = n-2; i >= 0; i--) {
                a[i] = a[i + 1] + rand()%d;
            }
        }
        else {
            for (int i = 0; i < n; i++) {
                a[i] = rand() % d;
            }
        }
    };


    Array(int *b, int len) {
        a = new int[len];
        n = len;
        for (int i = 0; i < n; i++) {
            a[i] = b[i];
        }
    }  // конструктор 2: по массиву
    Array(Array &b) {
        a = new int[b.n];
        n = b.n;
        for (int i = 0; i < n; i++) {
            a[i] = b.a[i];
        }
    }
    ~Array() { if(a) delete []a; a = NULL;}

    Array& operator = (Array &b) {
        if(this!=(&b)) {
            if (n != b.n) {
                delete []a;
                a = new int[b.n];
                n = b.n;
            }

            for (int i = 0; i < n; i++) {
                a[i] = b.a[i];
            }
        }
        return *this;
    }

    int &operator [](int);

    bool Test();   // проверка на упорядоченность по неубыванию
    bool operator == (Array);   // равенство элементов массивов (но не порядка)

    void Shell_sort();
    void Heapsort();
    void heapify(int, int);
    void Hoar_init();
    void Hoar_sort(int, int);
    void Bit_sort(int, int, int);
    void major_bit();// для Bit_sort

    // int getlen() {
    //     return n;
    // }

    friend istream & operator >> (istream &, Array &);
    friend ostream & operator << (ostream &, Array &);
};

int & Array::operator [](int b) {
    if (b < 0 || b >= n) return a[0];
    return a[b];
}

bool Array::Test() {
    for (int i = 1; i < n; i++) {
        if (a[i] < a[i-1]) return false;
    }
    return true;
}

bool Array::operator == (Array b) {
    if (n != b.n) return false;
    int len = n;
    for (int i = 0; i < n; i++) {
        bool ch = false;
        for (int j = 0; j < len; j++) {
            if (a[i] == b.a[j]) {
                ch = true;
                b[j]=b[len-1];
                len--;
                break;
            }
        }
        if (ch == false) return false;
    }
    return true;
}

istream & operator >> (istream & in, Array & a) {
    string line;
    getline(cin, line);
    istringstream is(line);
    int size = 1;
    delete [] a.a;
    a.a = new int[size];
    while(is>>a.a[size - 1]) {
        int *temp = new int[size];
        size++;
        for (int i = 0; i < size-1; i++) {
            temp[i] = a.a[i];
        }
        delete [] a.a;
        a.a = new int[size];
        for (int i = 0; i < size-1; i++) {
            a.a[i] = temp[i];
        }
        delete [] temp;
    }
    a.n = size-1;
    return in;
}
ostream & operator << (ostream & out, Array & a) {
    for (int i = 0; i < a.n; i++) {
        out << a[i] << " ";
    }
    return out;
}



void Array::Shell_sort() {
    for (int s = n / 2; s > 0; s /= 2)
        for (int i = s; i < n; ++i){
            int k = a[i];
            int j;
            for (j = i; j >= s && a[j - s] > k; j -= s)
                a[j] = a[j - s];
            a[j] = k;
        }
}
void Array::Hoar_init() {
    this->Hoar_sort(0,n-1);
}
void Array::Hoar_sort(int low ,int high){

    if (low < high) {
        int pivot = a[(low+high)/2];
        int i = low;
        int j = high;
        while (true) {
            while (a[i]<pivot) i++;
            while (a[j]>pivot) j--;
            if (i>j) {
                break;
            }
            if (a[i]!=a[j]) {
                a[i]^=a[j];
                a[j]^=a[i];
                a[i]^=a[j];
            }
            i++;
            j--;
        }
        cout<<endl<<pivot<<"\t"<<j<<"\t"<<i<<"\n"<<*this<<"\n";
        this->Hoar_sort(low, j);
        this->Hoar_sort(i,high);
    }
}

void Array::heapify(int n, int i) {
    int j = 2 * i + 1;
    int x = a[i];
    bool f = true;
    while(j < n && f) {
        if (j + 1 < n && a[j + 1]>a[j]) j++;
        if(a[j] > x) {
            a[i] = a[j];
            i = j;
            j = 2 * i + 1;
        }
        else f = false;
    }
    a[i] = x;
}

void Array::Heapsort() {
    for (int i = n / 2 - 1; i >= 0; i--)
        this->heapify(n,i);
    for (int i = n - 1; i > 0; i--) {
        if (a[i]!=a[0]) {
            a[i]^=a[0];
            a[0]^=a[i];
            a[i]^=a[0];
        }
        this->heapify(i, 0);
    }
}
void Array::major_bit() {
    int max = a[0];
    for (int i = 0; i < n; i++) {
        if(a[i]>max) max = a[i];
    }
    int k = 0;
    while(max) {
        max>>=1;
        k++;
    }
    this->Bit_sort(0,n-1,k-1);
}

void Array::Bit_sort(int l, int r, int k) {
    if (!(l>=r || k < 0)) {
        int i = l, j = r;
        int mask = 1<<k;
        while (i<=j) {
            while (i<=j && !(a[i]&mask)) i++;
            while (i<=j && a[j]&mask) j--;
            if (i < j) {
                if (a[i]!=a[j]) {
                    a[i]^=a[j];
                    a[j]^=a[i];
                    a[i]^=a[j];
                }
                i++;
                j--;
            }
        }
    this->Bit_sort(l,j,k-1);
    this->Bit_sort(i,r,k-1);
    }
}
void func_test() {
    Array a(10);
    Array b(a);
    cin>>a;
    cout<<a<<endl<<b<<endl;
    cin>>b;
    Array c = b;
    b.Shell_sort();
    cout<<"After Shell_sort\n"<<b<<endl;
    cout<<"To compare: \n";
    cout<<c<<endl<<b<<endl;
    if (c == b) cout<<"equal"<<endl;
    else cout<<"not equal\n";

    Array d1(50,10000);
    Array d2 = d1, d3 = d1;
    cout<<d1<<endl;
    if(!d1.Test()) d1.Hoar_init();
    cout<<d1<<endl;
    if(!d2.Test()) d2.Heapsort();
    cout<<d2<<endl;
    if(!d3.Test()) d3.major_bit();
    cout<<d3<<endl;

    Array test1(1000000,100000);
    Array test2 = test1;
    Array test3 = test1;
    Array test4 = test1;
    auto start = high_resolution_clock::now();
    test1.Shell_sort();
    auto stop = high_resolution_clock::now();
    auto duration1 = duration_cast<microseconds>(stop - start);
    start = high_resolution_clock::now();
    test2.Hoar_init();
    stop = high_resolution_clock::now();
    auto duration2 = duration_cast<microseconds>(stop - start);
    start = high_resolution_clock::now();
    test3.Heapsort();
    stop = high_resolution_clock::now();
    auto duration3 = duration_cast<microseconds>(stop - start);
    start = high_resolution_clock::now();
    test4.major_bit();
    stop = high_resolution_clock::now();
    auto duration4 = duration_cast<microseconds>(stop - start);
    if(test1.Test() && test2.Test() && test3.Test() && test4.Test())
        cout<<"Shell_sort: "<<duration1.count()<<"\nHoar_init: "<<duration2.count()<<"\nHeapsort: "<<duration3.count()<<"\nmajor_bit: "<<duration4.count()<<endl
            <<"----------------------------------------------------\n";

    start = high_resolution_clock::now();
    test1.Shell_sort();
    stop = high_resolution_clock::now();
    duration1 = duration_cast<microseconds>(stop - start);
    start = high_resolution_clock::now();
    test2.Hoar_init();
    stop = high_resolution_clock::now();
    duration2 = duration_cast<microseconds>(stop - start);
    start = high_resolution_clock::now();
    test3.Heapsort();
    stop = high_resolution_clock::now();
    duration3 = duration_cast<microseconds>(stop - start);
    start = high_resolution_clock::now();
    test4.major_bit();
    stop = high_resolution_clock::now();
    duration4 = duration_cast<microseconds>(stop - start);

    cout<<"Shell_sort: "<<duration1.count()<<"\nHoar_init: "<<duration2.count()<<"\nHeapsort: "<<duration3.count()<<"\nmajor_bit: "<<duration4.count()<<endl<<"----------------------------------------------------\n";

    Array sequence(1000000,1000,3);
    test1 = sequence;
    test2 = sequence;
    test3 = sequence;
    test4 = sequence;

    start = high_resolution_clock::now();
    test1.Shell_sort();
    stop = high_resolution_clock::now();
    duration1 = duration_cast<microseconds>(stop - start);
    start = high_resolution_clock::now();
    test2.Hoar_init();
    stop = high_resolution_clock::now();
    duration2 = duration_cast<microseconds>(stop - start);
    start = high_resolution_clock::now();
    test3.Heapsort();
    stop = high_resolution_clock::now();
    duration3 = duration_cast<microseconds>(stop - start);
    start = high_resolution_clock::now();
    test4.major_bit();
    stop = high_resolution_clock::now();
    duration4 = duration_cast<microseconds>(stop - start);

    cout<<"Shell_sort: "<<duration1.count()<<
    "\nHoar_init: "<<duration2.count()<<
    "\nHeapsort: "<<duration3.count()<<
    "\nmajor_bit: "<<duration4.count()<<
    endl<<"----------------------------------------------------\n";
}


int main() {
    srand(time(0));
    Array a(12,100);
    cout<<a<<endl;
    a.Shell_sort();
    cout<<a<<endl;

    // func_test();

    return 0;
}


// Дополнительно (не обязательно).
// 1. Конструктор, который формирует арифметическую прогрессию.
// 2. Перегрузка операции +: слить два упорядоченных массива в третий упорядоченный.
// 3. void operator - (int k); // удалить все вхождения числа k