void bubbleSort(vector<int>& arr){

    bool swapped ;

    for(int i = 0 ; i < arr.size()-1 ; i++){

        swapped = false ;

        for(int j = 0 ; j < arr.size()-i-1; j++){

            if(arr[j] > arr[j+1]){

                swap(arr[j] , arr[j+1]);
                swapped = true;

            }

        }

        if(!swapped) break ;

    }

}


void selectionSort(vector<int>& arr){

    int minIdx = 0 , i;

    for( i = 0 ; i < arr.size()-1 ; i++){

        minIdx = i ;

        for(int j = i+1 ; j < arr.size() ; j++){

            if(arr[j] < arr[minIdx]) minIdx = j ;

        }

        swap(arr[minIdx] , arr[i]) ;

    }

}

void insertionSort(vector<int>& arr){

    int i , j , key ;

    for(int i = 1 ; i < arr.size() ;i++){

        key = arr[i] ;

        j = i - 1 ;

        while(j >= 0 && arr[j] > key){

            arr[j+1] = arr[j] ;

            j -= 1 ;

        }

        arr[j+1] = key ;

    }

}

// ================== QUICK SORT ============================

// last element is taken as pivot
int Partition(vector<int> &v, int start, int end){

    int pivot = end;
    int j = start;
    for(int i=start;i<end;++i){
        if(v[i]<v[pivot]){
            swap(v[i],v[j]);
            ++j;
        }
    }
    swap(v[j],v[pivot]);
    return j;

}

void Quicksort(vector<int> &v, int start, int end ){

    if(start<end){
        int p = Partition(v,start,end);
        Quicksort(v,start,p-1);
        Quicksort(v,p+1,end);
    }

}

void PrintVector(vector<int> v){
    for(int i=0;i<v.size();++i)
        cout<<v[i]<<" ";
    cout<<"\n\n";
}

int main() {

    vector<int> v = { 1 , 10 , 11 , 9 , 14 , 3 , 2 , 20 , 19 };

    cout<<"Vector Before Sorting: "<<endl;
    PrintVector(v);

    Quicksort(v,0,v.size()-1);

    cout<<"Vector After Sorting: "<<endl;
    PrintVector(v);

}

//============================MERGE SORT ============================

void MergeSortedIntervals(vector<int>& v, int s, int m, int e) {

    // temp is used to temporary store the vector obtained by merging
    // elements from [s to m] and [m+1 to e] in v
    vector<int> temp;

    int i, j;
    i = s;
    j = m + 1;

    while (i <= m && j <= e) {

        if (v[i] <= v[j]) {
            temp.push_back(v[i]);
            ++i;
        }
        else {
            temp.push_back(v[j]);
            ++j;
        }

    }

    while (i <= m) {
        temp.push_back(v[i]);
        ++i;
    }

    while (j <= e) {
        temp.push_back(v[j]);
        ++j;
    }

    for (int i = s; i <= e; ++i)
        v[i] = temp[i - s];

}

// the MergeSort function
// Sorts the array in the range [s to e] in v using
// merge sort algorithm
void MergeSort(vector<int>& v, int s, int e) {
    if (s < e) {
        int m = (s + e) / 2;
        MergeSort(v, s, m);
        MergeSort(v, m + 1, e);
        MergeSortedIntervals(v, s, m, e);
    }
}

int main() {

    int n;
    vector<int> v;

    cout << "Enter Size of Vector : ";
    cin >> n;
    v = vector<int>(n);
    cout << "Enter Elements of Vector : ";
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }

    MergeSort(v, 0, n - 1);

    cout << "\nVector Obtained After Sorting: ";
    for (int i = 0; i < n; ++i) {
        cout << v[i] << ' ';
    }

}

//=============== LEVEL ORDER TRAVERSAL OF TREE ================

class Solution {
public:
    vector<int> levelOrder(TreeNode* root) {
        vector<int> ans;

        if(root == NULL)
            return ans;

        queue<TreeNode*> q;
        q.push(root);

        while(!q.empty()) {

            TreeNode *temp = q.front();
            q.pop();

            if(temp->left != NULL)
                q.push(temp->left);
            if(temp->right != NULL)
                q.push(temp->right);

            ans.push_back(temp->val);
        }
        return ans;
    }
};

// ========================= BFS of GRAPH ======================

class Solution {
  public:
    vector < int > bfsOfGraph(int V, vector < int > adj[]) {
      vector < int > bfs;
      vector < int > vis(V, 0);
      queue < int > q;
      q.push(0);
      vis[0] = 1;
      while (!q.empty()) {
        int node = q.front();
        q.pop();
        bfs.push_back(node);

        for (auto it: adj[node]) {
          if (!vis[it]) {
            q.push(it);
            vis[it] = 1;
          }
        }
      }

      return bfs;
    }
};