fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define el "\n"
  4. #define ll long long
  5. #define ull unsigned long long
  6. #define se second
  7. #define fi first
  8. #define be begin()
  9. #define en end()
  10. #define Faster cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
  11.  
  12. void selectionSort(vector<int>& arr)
  13. {
  14.     for(int i = 0; i < arr.size(); i++)
  15.     {
  16.         int id = i;
  17.         for(int j = i; j < arr.size(); j++)
  18.         {
  19.             if(arr[j] < arr[id]) id = j;
  20.         }
  21.         swap(arr[i], arr[id]);
  22.     }
  23. }
  24.  
  25. void insertionSort(vector<int>& arr)
  26. {
  27.     for(int i = 1; i < arr.size(); i++)
  28.     {
  29.         int id = i - 1, tmp = arr[i];
  30.         while(id >= 0 && tmp < arr[id])
  31.         {
  32.             arr[id + 1] = arr[id];
  33.             id--;
  34.         }
  35.         arr[id + 1] = tmp;
  36.     }
  37. }
  38.  
  39. void bubbleSort(vector<int>& arr)
  40. {
  41.     for(int i = 0; i < arr.size(); i++)
  42.     {
  43.         for(int j = 0; j < arr.size() - i - 1; j++)
  44.         {
  45.             if(arr[j] > arr[j + 1]) swap(arr[j], arr[j + 1]);
  46.         }
  47.     }
  48. }
  49.  
  50. void merge(vector<int>& arr, int left, int mid, int right)
  51. {
  52.     vector<int> x(arr.begin() + left, arr.begin() + mid + 1);
  53.     vector<int> y(arr.begin() + mid + 1, arr.begin() + right + 1);
  54.     int i = 0, j = 0, k = left;
  55.     while(i < x.size() && j < y.size())
  56.     {
  57.         if(x[i] <= y[j]) arr[k++] = x[i++];
  58.         else arr[k++] = y[j++];
  59.     }
  60.     while(i < x.size()) arr[k++] = x[i++];
  61.     while(j < y.size()) arr[k++] = y[j++];
  62. }
  63.  
  64. void mergeSort(vector<int>& arr, int left, int right)
  65. {
  66.     if(left >= right) return;
  67.     int mid = (left + right) / 2;
  68.     mergeSort(arr, left, mid);
  69.     mergeSort(arr, mid + 1, right);
  70.     merge(arr, left, mid, right);
  71. }
  72.  
  73. int partition(vector<int>& arr, int left, int right)
  74. {
  75.     int i = left - 1, tmp = arr[right];
  76.     for(int j = left; j < right; j++)
  77.     {
  78.         if(arr[j] <= tmp) swap(arr[++i], arr[j]);
  79.     }
  80.     swap(arr[++i], arr[right]);
  81.     return i;
  82. }
  83.  
  84. void quickSort(vector<int>& arr, int left, int right)
  85. {
  86.     if(left < right)
  87.     {
  88.         int p = partition(arr, left, right);
  89.         quickSort(arr, left, p - 1);
  90.         quickSort(arr, p + 1, right);
  91.     }
  92. }
  93.  
  94. void heapify(vector<int>& arr, int n, int i)
  95. {
  96.     int id = i, left = 2 * i + 1, right = 2 * i + 2;
  97.     if(left < n && arr[left] > arr[id]) id = left;
  98.     if(right < n && arr[right] > arr[id]) id = right;
  99.     if(id != i)
  100.     {
  101.         swap(arr[i], arr[id]);
  102.         heapify(arr, n, id);
  103.     }
  104. }
  105.  
  106. void heapSort(vector<int>& arr)
  107. {
  108.     int n = arr.size();
  109.     for(int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);
  110.     for(int i = n - 1; i > 0; i--)
  111.     {
  112.         swap(arr[0], arr[i]);
  113.         heapify(arr, i, 0);
  114.     }
  115. }
  116.  
  117. void countSort(vector<int>& arr, int exp)
  118. {
  119.     vector<int> b(arr.size()), cnt(10, 0);
  120.     for(int i = 0; i < arr.size(); i++) cnt[(arr[i] / exp) % 10]++;
  121.     for(int i = 1; i < 10; i++) cnt[i] += cnt[i - 1];
  122.     for(int i = arr.size() - 1; i >= 0; i--) b[--cnt[(arr[i] / exp) % 10]] = arr[i];
  123.     for(int i = 0; i < arr.size(); i++) arr[i] = b[i];
  124. }
  125.  
  126. void radixSort(vector<int>& arr)
  127. {
  128.     int maxx = *max_element(arr.begin(), arr.end());
  129.     for(int exp = 1; maxx / exp > 0; exp *= 10) countSort(arr, exp);
  130. }
  131.  
  132. void printArray(const vector<int>& arr)
  133. {
  134.     for(int num : arr) cout << num << " ";
  135.     cout << el;
  136. }
  137.  
  138. int main()
  139. {
  140.     Faster;
  141.     vector<int> arr = {38, 27, 43, 3, 9, 82, 10};
  142.     cout << "Mang ban dau: ";
  143.     printArray(arr);
  144.  
  145.     mergeSort(arr, 0, arr.size() - 1);
  146.     cout << "Mang sau khi sap xep tron: ";
  147.     printArray(arr);
  148.  
  149.     return 0;
  150. }
  151.  
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Mang ban dau: 38 27 43 3 9 82 10 
Mang sau khi sap xep tron: 3 9 10 27 38 43 82
https://ideone.com/LuU4Nt
language:
C++ (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!