Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment