#include "lab1.h"
#include "lab2.h"
#include "lab3.h"

using namespace std;




void sort(lab1::Queue<int>& q){
    q.N_op+=3;
    for(int i = 0; i < q.size(); ++i){
        q.N_op+= 12;
        int mn = INT_MAX;
        int first = 0, temp = 0;
        bool swap = true;
        for(int j = 0; j < i; ++j){
            q.N_op++;
            temp = q.front();
            q.pop();
            q.push(temp);
        }
        first = q.front();
        for(int j = i; j < q.size(); ++j){
            temp = q.front();
            mn = min(q.front(), mn);
            q.pop();
            q.push(temp);
            q.N_op+=3;
        }
        for(int j = 0; j < i; ++j){
            q.N_op++;
            temp = q.front();
            q.pop();
            q.push(temp);
        }
        for(int j = i; j < q.size(); ++j){
            q.N_op+=5;
            temp = q.front();
            q.pop();
            if(temp == mn && swap) {
                q.push(first);
                swap = false;
            }
            else if(i == j) {
                q.push(mn);
            }
            else
                q.push(temp);
        }
    }
}


int main(){
    for (int a = 3000; a <= 4000; a += 200) {
        size_t n = 0;
        lab1::Queue<int> queue(a);
        srand(time(NULL));
        ::clock_t start = ::clock();
        for(int i = 0; i < a; ++i){
            queue.push(::rand() % (10 * a));
        }
        cout << "init of " << a << " elements takes " <<
            1000 * (::clock() - start) / CLOCKS_PER_SEC << '\n';
        n += queue.N_op;
        start = ::clock();
        sort(queue);
        cout << "sort of " << a << " elements takes " << 1000 * (::clock() - start) / CLOCKS_PER_SEC << " millisec\n";

        cout << "takes " << n << " N_op\n\n";
    }
    return 0;
}