fork download
copy 
  1. #ifdef _OPENMP
  2. #include <omp.h>
  3. #endif
  4. #include <stddef.h>
  5. #include <stdio.h>
  6. #include <stdlib.h>
  7. #include <sys/time.h>
  8.  
  9. #ifndef ELEM_COUNT
  10. #define ELEM_COUNT (1 << 29)
  11. #elif ELEM_COUNT <= 0
  12. #error Don't you think you're smarter than me?
  13. #endif
  14.  
  15. #ifdef MAX_ELEMENT
  16. int next_element() {
  17.     return rand() % MAX_ELEMENT;
  18. }
  19. #else
  20. int next_element() {
  21.     return rand();
  22. }
  23. #endif
  24.  
  25. void print_array(int* arr) {
  26.     printf("[ %d", arr[0]);
  27.     for (int i = 1; i < ELEM_COUNT; ++i) {
  28.         printf(", %d", arr[i]);
  29.     }
  30.     printf(" ]\n");
  31. }
  32.  
  33. int main() {
  34.     int* from = (int*)malloc(((size_t)ELEM_COUNT) * sizeof(int));
  35.     int* to = (int*)malloc(((size_t)ELEM_COUNT) * sizeof(int));
  36.     if (!from || !to) {
  37.         printf("Buy and install more RAM, looser!\n");
  38.         exit(EXIT_FAILURE);
  39.     }
  40.     for (int i = 0; i < ELEM_COUNT; ++i) {
  41.         from[i] = next_element();
  42.     }
  43. #ifdef DEBUG
  44.     printf("Going to sort array:\n");
  45.     print_array(from);
  46. #else
  47.     printf("Array prepared\n");
  48. #endif
  49.     struct timeval start, end;
  50.     gettimeofday(&start, NULL);
  51.     for (int size = 1; size < ELEM_COUNT; size += size) {
  52.         int* stop = from + ELEM_COUNT;
  53. #pragma omp parallel for
  54.         for (int i = 0; i < ELEM_COUNT; i += size + size) {
  55.             int* a = from + i;
  56.             int* aend = a + size;
  57.             if (aend > stop) {
  58.                 aend = stop;
  59.             }
  60.             int* b = aend;
  61.             int* bend = b + size;
  62.             if (bend > stop) {
  63.                 bend = stop;
  64.             }
  65.             int* out = to + i;
  66.             while (a < aend && b < bend) {
  67.                 if (*a < *b) {
  68.                     *out++ = *a++;
  69.                 } else {
  70.                     *out++ = *b++;
  71.                 }
  72.             }
  73.             if (a < aend) {
  74.                 while (a < aend) {
  75.                     *out++ = *a++;
  76.                 }
  77.             } else {
  78.                 while (b < bend) {
  79.                     *out++ = *b++;
  80.                 }
  81.             }
  82.         }
  83.         int* t = from;
  84.         from = to;
  85.         to = t;
  86.     }
  87.     gettimeofday(&end, NULL);
  88. #ifdef DEBUG
  89.     printf("Array sorted:\n");
  90.     print_array(from);
  91. #endif
  92.     printf("Time taken: %fs\n",
  93.         ((double)(end.tv_sec - start.tv_sec) + (double)(end.tv_usec - start.tv_usec) / 1000000.0));
  94. #ifdef _OPENMP
  95.     printf("Threads: %d\n", omp_get_max_threads());
  96. #endif
  97.     return EXIT_SUCCESS;
  98. }
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/yawZnl
language:
C (gcc 8.3)
created:
12 years 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!