fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <time.h>
  4.  
  5. #define ARRAY_SIZE 10000000
  6.  
  7. using namespace std;
  8.  
  9. void randomize(vector<int> &arr);
  10. bool isSorted(vector<int> &arr);
  11.  
  12. void quickSort(vector<int> &arr, int low, int high);
  13. int partition(vector<int> &arr, int low, int high);
  14. void quickSort2(vector<int> &arr, int low, int high);
  15. int partition2(vector<int> &arr, int low, int high);
  16.  
  17. int main(void) {
  18.     clock_t timeStart, timeEnd;
  19.  
  20.     vector<int> array(ARRAY_SIZE);
  21.  
  22.     // quick sort1
  23.     randomize(array);
  24.     timeStart = clock();
  25.     quickSort(array, 0, ARRAY_SIZE-1);
  26.     timeEnd = clock();
  27.     if(!isSorted(array)) printf("not sorted.\n");
  28.     printf( "%s: %f sec\n", "quick1", (double)(timeEnd - timeStart) / CLOCKS_PER_SEC );
  29.  
  30.     // quick sort2
  31.     randomize(array);
  32.     timeStart = clock();
  33.     quickSort2(array, 0, ARRAY_SIZE-1);
  34.     timeEnd = clock();
  35.     if(!isSorted(array)) printf("not sorted.\n");
  36.     printf( "%s: %f sec\n", "quick2", (double)(timeEnd - timeStart) / CLOCKS_PER_SEC );
  37.  
  38.     return 0;
  39. }
  40.  
  41. void randomize(vector<int> &arr) {
  42.     srand((unsigned) time(NULL));
  43.  
  44.     for(int i = 0; i < ARRAY_SIZE; ++i) {
  45.         arr[i] = rand();
  46.     }
  47. }
  48.  
  49. bool isSorted(vector<int> &arr) {
  50.     for(int i = 1; i < ARRAY_SIZE; ++i) {
  51.         if(arr[i-1] > arr[i]) return false;
  52.     }
  53.     return true;
  54. }
  55.  
  56. void quickSort(vector<int> &arr, int low, int high) {
  57.     if (low < high) { 
  58.         int pi = partition(arr, low, high); 
  59.  
  60.         quickSort(arr, low, pi - 1);
  61.         quickSort(arr, pi + 1, high);
  62.     }
  63. }
  64.  
  65. int partition(vector<int> &arr, int low, int high) {
  66.     int pivot = arr[high];
  67.  
  68.     int i = low;
  69.  
  70.     for (int j = low; j <= high - 1; j++) {
  71.         if (arr[j] < pivot) {
  72.             swap(arr[i], arr[j]);
  73.             i++;
  74.         } 
  75.     }
  76.     swap(arr[i], arr[high]);
  77.     return i;
  78. }
  79. /*
  80. // GeeksforGeeksのものは以下なのですが、これだとさらに遅くなります
  81. int partition(vector<int> &arr, int low, int high) {
  82.     int pivot = arr[high];
  83.     
  84.     int i = low - 1;
  85.     
  86.     for (int j = low; j <= high - 1; j++) {
  87.         if (arr[j] <= pivot) { // この = のせいらしい
  88.             i++;
  89.             swap(arr[i], arr[j]);
  90.         }
  91.     }
  92.     swap(arr[i + 1], arr[high]);
  93.     return i + 1; 
  94. }
  95. */
  96.  
  97.  
  98. void quickSort2(vector<int> &arr, int low, int high) {
  99.     if (low < high) {
  100.         int pi = partition2(arr, low, high);
  101.  
  102.         quickSort2(arr, low, pi - 1);
  103.         quickSort2(arr, pi + 1, high);
  104.     } 
  105. } 
  106.  
  107. int partition2(vector<int> &arr, int low, int high) {
  108.     int pivot = arr[high];
  109.     int i = low;
  110.     int j = high-1;
  111.  
  112.     for ( ; ; ) {
  113.         while (arr[i] < pivot) i++;
  114.         while (pivot < arr[j]) j--;
  115.         if (i >= j) break;
  116.         swap(arr[i], arr[j]);
  117.         i++; 
  118.         j--;
  119.     }
  120.     swap(arr[i], arr[high]);
  121.     return i;
  122. } 
  123.  
  124.  
  125.  
Success #stdin #stdout 1.68s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
quick1: 0.758109 sec
quick2: 0.773889 sec
https://ideone.com/Ehhq0f
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
secret

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!