fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using namespace chrono;
  4.  
  5. void bubbleSort(vector<int>& arr) {
  6.     int n = arr.size();
  7.     for (int i = 0; i < n - 1; i++)
  8.         for (int j = 0; j < n - i - 1; j++)
  9.             if (arr[j] > arr[j + 1])
  10.                 swap(arr[j], arr[j + 1]);
  11. }
  12.  
  13. void selectionSort(vector<int>& arr) {
  14.     int n = arr.size();
  15.     for (int i = 0; i < n - 1; i++) {
  16.         int minIdx = i;
  17.         for (int j = i + 1; j < n; j++)
  18.             if (arr[j] < arr[minIdx])
  19.                 minIdx = j;
  20.         swap(arr[minIdx], arr[i]);
  21.     }
  22. }
  23.  
  24. void insertionSort(vector<int>& arr) {
  25.     int n = arr.size();
  26.     for (int i = 1; i < n; i++) {
  27.         int key = arr[i], j = i - 1;
  28.         while (j >= 0 && arr[j] > key) {
  29.             arr[j + 1] = arr[j];
  30.             j--;
  31.         }
  32.         arr[j + 1] = key;
  33.     }
  34. }
  35.  
  36. void merge(vector<int>& arr, int l, int m, int r) {
  37.     int n1 = m - l + 1, n2 = r - m;
  38.     vector<int> L(n1), R(n2);
  39.     for (int i = 0; i < n1; i++) L[i] = arr[l + i];
  40.     for (int i = 0; i < n2; i++) R[i] = arr[m + 1 + i];
  41.     int i = 0, j = 0, k = l;
  42.     while (i < n1 && j < n2) arr[k++] = (L[i] < R[j]) ? L[i++] : R[j++];
  43.     while (i < n1) arr[k++] = L[i++];
  44.     while (j < n2) arr[k++] = R[j++];
  45. }
  46.  
  47. void mergeSort(vector<int>& arr, int l, int r) {
  48.     if (l >= r) return;
  49.     int m = l + (r - l) / 2;
  50.     mergeSort(arr, l, m);
  51.     mergeSort(arr, m + 1, r);
  52.     merge(arr, l, m, r);
  53. }
  54.  
  55. int partition(vector<int>& arr, int low, int high) {
  56.     int pivot = arr[high], i = low - 1;
  57.     for (int j = low; j < high; j++)
  58.         if (arr[j] < pivot)
  59.             swap(arr[++i], arr[j]);
  60.     swap(arr[i + 1], arr[high]);
  61.     return i + 1;
  62. }
  63.  
  64. void quickSort(vector<int>& arr, int low, int high) {
  65.     if (low < high) {
  66.         int pi = partition(arr, low, high);
  67.         quickSort(arr, low, pi - 1);
  68.         quickSort(arr, pi + 1, high);
  69.     }
  70. }
  71.  
  72. void heapify(vector<int>& arr, int n, int i) {
  73.     int largest = i, l = 2 * i + 1, r = 2 * i + 2;
  74.     if (l < n && arr[l] > arr[largest]) largest = l;
  75.     if (r < n && arr[r] > arr[largest]) largest = r;
  76.     if (largest != i) {
  77.         swap(arr[i], arr[largest]);
  78.         heapify(arr, n, largest);
  79.     }
  80. }
  81.  
  82. void heapSort(vector<int>& arr) {
  83.     int n = arr.size();
  84.     for (int i = n / 2 - 1; i >= 0; i--)
  85.         heapify(arr, n, i);
  86.     for (int i = n - 1; i > 0; i--) {
  87.         swap(arr[0], arr[i]);
  88.         heapify(arr, i, 0);
  89.     }
  90. }
  91.  
  92. void measureTime(void (*sortFunc)(vector<int>&), vector<int> arr, string name) {
  93.     auto start = high_resolution_clock::now();
  94.     sortFunc(arr);
  95.     auto stop = high_resolution_clock::now();
  96.     auto duration = duration_cast<milliseconds>(stop - start);
  97.     cout << name << ": " << duration.count() << " ms\n";
  98. }
  99.  
  100. int main() {
  101.     vector<int> arr(10000);
  102.     iota(arr.begin(), arr.end(), 1);
  103.     random_shuffle(arr.begin(), arr.end());
  104.  
  105.     measureTime(bubbleSort, arr, "Bubble Sort");
  106.     measureTime(selectionSort, arr, "Selection Sort");
  107.     measureTime(insertionSort, arr, "Insertion Sort");
  108.     measureTime([](vector<int>& a) { mergeSort(a, 0, a.size() - 1); }, arr, "Merge Sort");
  109.     measureTime([](vector<int>& a) { quickSort(a, 0, a.size() - 1); }, arr, "Quick Sort");
  110.     measureTime(heapSort, arr, "Heap Sort");
  111.  
  112.     return 0;
  113. }
  114.  
Success #stdin #stdout 0.15s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Bubble Sort: 105 ms
Selection Sort: 27 ms
Insertion Sort: 13 ms
Merge Sort: 1 ms
Quick Sort: 0 ms
Heap Sort: 0 ms
https://ideone.com/4ELogT
language:
C++ (gcc 8.3)
created:
1 hour 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!