SHARE
TWEET

Untitled

a guest Nov 14th, 2019 97 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //
  2. //  main.cpp
  3. //  PA1
  4. //
  5. //  Created by Zhasulan Suiebay on 11/14/19.
  6. //  Copyright © 2019 Zhasulan Suiebay. All rights reserved.
  7. //
  8.  
  9. # include <iostream>
  10. # include <fstream>
  11.  
  12. using namespace std;
  13.  
  14. typedef long long ll;
  15. typedef long double ld;
  16. typedef pair < int, int > pii;
  17.  
  18. const int N = (int)2e5 + 5;
  19. const int inf = (int)1e9 + 7;
  20.  
  21. int n;
  22. int a[N];
  23.  
  24. void merge(int lt, int mid, int rt){
  25.     int nl = mid - lt + 1;
  26.     int nr = rt - mid;
  27.     int l[nl + 2], r[nr + 2];
  28.    
  29.     for(int i = 1; i <= nl; i++){
  30.         l[i] = a[lt + i - 1];
  31.     }
  32.     for(int i = 1; i <= nr; i++){
  33.         r[i] = a[mid + i];
  34.     }
  35.    
  36.     l[nl + 1] = inf;
  37.     r[nr + 1] = inf;
  38.    
  39.     int i = 1, j = 1;
  40.    
  41.     for (int k = lt; k <= rt; k++){
  42.         if(l[i] < r[j]){
  43.             a[k] = l[i];
  44.             i++;
  45.         } else{
  46.             a[k] = r[j];
  47.             j++;
  48.         }
  49.     }
  50.    
  51. }
  52.  
  53.  
  54. void merge_sort(int lt, int rt){
  55.     if(lt < rt){
  56.         int mid = (rt + lt) / 2;
  57.        
  58.         merge_sort(lt, mid);
  59.         merge_sort(mid + 1, rt);
  60.         merge(lt, mid, rt);
  61.     }
  62. }
  63.  
  64. int main(){
  65.     int x;
  66.     ifstream File;
  67.    
  68.     File.open("input.txt");
  69.     if (!File) {
  70.         cout << "Unable to open file";
  71.         exit(1);
  72.     }
  73.    
  74.     while (File >> x) {
  75.         n++;
  76.         a[n] = x;
  77.     }
  78.    
  79.     File.close();
  80.    
  81.     merge_sort(1, n);
  82.    
  83.     ofstream o("output.txt");
  84.    
  85.     for(int i = 1; i <= n; i++){
  86.         o << a[i] << " ";
  87.     }
  88.    
  89.     o.close();
  90.     cout << "asd";
  91.  
  92.     return 0;
  93. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top