fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4. #define swap(x,y,t) {(t)=(x);(x)=(y);(y)=(t);}
  5. long int v[1000000];
  6. long int L[1000000];
  7. long int R[1000000];
  8. void quickSort(int e[],int n)
  9. {
  10.     if(n<=1) return;
  11.     int temp;
  12.     int L,R;
  13.     int pivot = e[0];
  14.     int num = 0;
  15.     L = 1;
  16.     R = n-1;
  17.     while(L!=R)
  18.     {
  19.         while((e[R] > pivot)&&( L < R))
  20.             R--;
  21.         while((e[L] <= pivot )&&( L < R))
  22.             L++;
  23.         if( L < R)
  24.         {
  25.             num++;
  26.             swap(e[L],e[R],temp);
  27.         }
  28.     }
  29.         if(e[R] <= pivot)
  30.         {
  31.             num++;
  32.             swap(e[0],e[R],temp);
  33.         }
  34.         if( num == 0)
  35.         {
  36.             quickSort( e + 1, n - 1);
  37.             return ;
  38.         }
  39.         quickSort( e , R);
  40.         quickSort( e + R +1,n - R - 1);
  41.  
  42. }
  43. void merge(int arr[], int l, int m, int r)
  44. {
  45.     int i, j, k;
  46.     int n1 = m - l + 1;
  47.     int n2 = r - m;
  48.     for (i = 0; i < n1; i++)
  49.         L[i] = arr[l + i];
  50.     for (j = 0; j < n2; j++)
  51.         R[j] = arr[m + 1 + j];
  52.     i = 0;
  53.     k = l;
  54.     while (i < n1 && j < n2) {
  55.         if (L[i] <= R[j]) {
  56.             arr[k] = L[i];
  57.             i++;
  58.         }
  59.         else {
  60.             arr[k] = R[j];
  61.             j++;
  62.         }
  63.         k++;
  64.     }
  65.     while (i < n1) {
  66.         arr[k] = L[i];
  67.         i++;
  68.         k++;
  69.     }
  70.     while (j < n2) {
  71.         arr[k] = R[j];
  72.         j++;
  73.         k++;
  74.     }
  75. }
  76. void mergeSort(int arr[], int l, int r)
  77. {
  78.     if (l < r) {
  79.         int m = l + (r - l) / 2;
  80.         mergeSort(arr, l, m);
  81.         mergeSort(arr, m + 1, r);
  82.         merge(arr, l, m, r);
  83.     }
  84. }
  85. void heapify(int arr[], int n, int i)
  86. {
  87.     int temp;
  88.     int largest = i;
  89.     int l = 2 * i + 1;
  90.     int r = 2 * i + 2;
  91.     if (l < n && arr[l] > arr[largest])
  92.         largest = l;
  93.     if (r < n && arr[r] > arr[largest])
  94.         largest = r;
  95.     if (largest != i) {
  96.         swap(arr[i], arr[largest],temp);
  97.         heapify(arr, n, largest);
  98.     }
  99. }
  100. void heapSort(int arr[], int n)
  101. {
  102.     int temp;
  103.     for (int i = n / 2 - 1; i >= 0; i--)
  104.         heapify(arr, n, i);
  105.     for (int i = n - 1; i > 0; i--) {
  106.         swap(arr[0], arr[i],temp);
  107.         heapify(arr, i, 0);
  108.     }
  109. }
  110.  
  111. int main()
  112. {
  113.     clock_t start,end;
  114.     srand(time(NULL));
  115.     int i=0;
  116. 	while( i < 1000000 )
  117. 	{
  118. 		v[i]=rand()*rand();
  119. 		if(v[i]==0)
  120. 		{
  121. 			continue;
  122. 		}
  123. 		i++;
  124. 	} 
  125.     start = clock();
  126.     quickSort(v,1000000);
  127.     end   = clock();
  128.     double total =((double)(end-start)) / CLOCKS_PER_SEC;
  129.     printf("quickSort time:%f\n",total);
  130.     start = clock();
  131.     mergeSort(v,0,999999);
  132.     end   = clock();
  133.     total =((double)(end-start)) / CLOCKS_PER_SEC;
  134.     printf("mergeSort time:%f\n",total);
  135.     start = clock();
  136.     heapSort(v,1000000);
  137.     end   = clock();
  138.     total =((double)(end-start)) / CLOCKS_PER_SEC;
  139.     printf("heapSort time:%f\n",total);
  140.     return 0;
  141. }
Time limit exceeded #stdin #stdout 5s 12736KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Glm92N
language:
C (gcc 8.3)
created:
2 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!