Advertisement
th0m45s5helby

Untitled

Aug 16th, 2022
671
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.54 KB | None | 0 0
  1. void bubbleSort(vector<int>& arr){
  2.    
  3.     bool swapped ;
  4.    
  5.     for(int i = 0 ; i < arr.size()-1 ; i++){
  6.        
  7.         swapped = false ;
  8.        
  9.         for(int j = 0 ; j < arr.size()-i-1; j++){
  10.            
  11.             if(arr[j] > arr[j+1]){
  12.                
  13.                 swap(arr[j] , arr[j+1]);
  14.                 swapped = true;
  15.                
  16.             }
  17.            
  18.         }
  19.        
  20.         if(!swapped) break ;
  21.        
  22.     }
  23.    
  24. }
  25.  
  26.  
  27. void selectionSort(vector<int>& arr){
  28.    
  29.     int minIdx = 0 , i;
  30.    
  31.     for( i = 0 ; i < arr.size()-1 ; i++){
  32.        
  33.         minIdx = i ;
  34.        
  35.         for(int j = i+1 ; j < arr.size() ; j++){
  36.            
  37.             if(arr[j] < arr[minIdx]) minIdx = j ;
  38.            
  39.         }
  40.        
  41.         swap(arr[minIdx] , arr[i]) ;
  42.        
  43.     }
  44.    
  45. }
  46.  
  47. void insertionSort(vector<int>& arr){
  48.    
  49.     int i , j , key ;
  50.    
  51.     for(int i = 1 ; i < arr.size() ;i++){
  52.        
  53.         key = arr[i] ;
  54.        
  55.         j = i - 1 ;
  56.        
  57.         while(j >= 0 && arr[j] > key){
  58.            
  59.             arr[j+1] = arr[j] ;
  60.            
  61.             j -= 1 ;
  62.            
  63.         }
  64.        
  65.         arr[j+1] = key ;
  66.        
  67.     }
  68.    
  69. }
  70.  
  71. // ================== QUICK SORT ============================
  72.  
  73. // last element is taken as pivot
  74. int Partition(vector<int> &v, int start, int end){
  75.    
  76.     int pivot = end;
  77.     int j = start;
  78.     for(int i=start;i<end;++i){
  79.         if(v[i]<v[pivot]){
  80.             swap(v[i],v[j]);
  81.             ++j;
  82.         }
  83.     }
  84.     swap(v[j],v[pivot]);
  85.     return j;
  86.    
  87. }
  88.  
  89. void Quicksort(vector<int> &v, int start, int end ){
  90.  
  91.     if(start<end){
  92.         int p = Partition(v,start,end);
  93.         Quicksort(v,start,p-1);
  94.         Quicksort(v,p+1,end);
  95.     }
  96.    
  97. }
  98.  
  99. void PrintVector(vector<int> v){
  100.     for(int i=0;i<v.size();++i)
  101.         cout<<v[i]<<" ";
  102.     cout<<"\n\n";
  103. }
  104.  
  105. int main() {
  106.    
  107.     vector<int> v = { 1 , 10 , 11 , 9 , 14 , 3 , 2 , 20 , 19 };
  108.    
  109.     cout<<"Vector Before Sorting: "<<endl;
  110.     PrintVector(v);
  111.    
  112.     Quicksort(v,0,v.size()-1);
  113.    
  114.     cout<<"Vector After Sorting: "<<endl;
  115.     PrintVector(v);
  116.        
  117. }
  118.  
  119. //============================MERGE SORT ============================
  120.  
  121. void MergeSortedIntervals(vector<int>& v, int s, int m, int e) {
  122.    
  123.     // temp is used to temporary store the vector obtained by merging
  124.     // elements from [s to m] and [m+1 to e] in v
  125.     vector<int> temp;
  126.  
  127.     int i, j;
  128.     i = s;
  129.     j = m + 1;
  130.  
  131.     while (i <= m && j <= e) {
  132.  
  133.         if (v[i] <= v[j]) {
  134.             temp.push_back(v[i]);
  135.             ++i;
  136.         }
  137.         else {
  138.             temp.push_back(v[j]);
  139.             ++j;
  140.         }
  141.  
  142.     }
  143.  
  144.     while (i <= m) {
  145.         temp.push_back(v[i]);
  146.         ++i;
  147.     }
  148.  
  149.     while (j <= e) {
  150.         temp.push_back(v[j]);
  151.         ++j;
  152.     }
  153.  
  154.     for (int i = s; i <= e; ++i)
  155.         v[i] = temp[i - s];
  156.  
  157. }
  158.  
  159. // the MergeSort function
  160. // Sorts the array in the range [s to e] in v using
  161. // merge sort algorithm
  162. void MergeSort(vector<int>& v, int s, int e) {
  163.     if (s < e) {
  164.         int m = (s + e) / 2;
  165.         MergeSort(v, s, m);
  166.         MergeSort(v, m + 1, e);
  167.         MergeSortedIntervals(v, s, m, e);
  168.     }
  169. }
  170.  
  171. int main() {
  172.  
  173.     int n;
  174.     vector<int> v;
  175.  
  176.     cout << "Enter Size of Vector : ";
  177.     cin >> n;
  178.     v = vector<int>(n);
  179.     cout << "Enter Elements of Vector : ";
  180.     for (int i = 0; i < n; ++i) {
  181.         cin >> v[i];
  182.     }
  183.  
  184.     MergeSort(v, 0, n - 1);
  185.  
  186.     cout << "\nVector Obtained After Sorting: ";
  187.     for (int i = 0; i < n; ++i) {
  188.         cout << v[i] << ' ';
  189.     }
  190.  
  191. }
  192.  
  193. //=============== LEVEL ORDER TRAVERSAL OF TREE ================
  194.  
  195. class Solution {
  196. public:
  197.     vector<int> levelOrder(TreeNode* root) {
  198.         vector<int> ans;
  199.        
  200.         if(root == NULL)
  201.             return ans;
  202.            
  203.         queue<TreeNode*> q;
  204.         q.push(root);
  205.        
  206.         while(!q.empty()) {
  207.            
  208.             TreeNode *temp = q.front();
  209.             q.pop();
  210.            
  211.             if(temp->left != NULL)
  212.                 q.push(temp->left);
  213.             if(temp->right != NULL)
  214.                 q.push(temp->right);
  215.                
  216.             ans.push_back(temp->val);
  217.         }
  218.         return ans;
  219.     }
  220. };
  221.  
  222. // ========================= BFS of GRAPH ======================
  223.  
  224. class Solution {
  225.   public:
  226.     vector < int > bfsOfGraph(int V, vector < int > adj[]) {
  227.       vector < int > bfs;
  228.       vector < int > vis(V, 0);
  229.       queue < int > q;
  230.       q.push(0);
  231.       vis[0] = 1;
  232.       while (!q.empty()) {
  233.         int node = q.front();
  234.         q.pop();
  235.         bfs.push_back(node);
  236.  
  237.         for (auto it: adj[node]) {
  238.           if (!vis[it]) {
  239.             q.push(it);
  240.             vis[it] = 1;
  241.           }
  242.         }
  243.       }
  244.  
  245.       return bfs;
  246.     }
  247. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement