Advertisement
Guest User

Untitled

a guest
Apr 29th, 2017
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.21 KB | None | 0 0
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <time.h>
  4.  
  5. #define MAX 10000000
  6. int selectRandomPosition(int* target, int left, int right){
  7. srand((unsigned) time(NULL));
  8. int length = right - left + 1;
  9. int r = left + rand()%length;
  10. return r;
  11. }
  12.  
  13. void ternarySplitQuickSort(int* target, int left, int right)
  14. {
  15. if(left>=right) return;
  16.  
  17. int maxlen = right - left + 1;
  18. int same[MAX];
  19. int less[MAX];
  20. int more[MAX];
  21. int same_count = 0;
  22. int less_count = 0;
  23. int more_count = 0;
  24. int random_idx = selectRandomPosition(target, left, right);
  25. int pivot = target[random_idx];
  26.  
  27. for(int i = 0; i < maxlen; i++) {
  28. if(target[i] < pivot) {
  29. less[less_count++] = target[i];
  30. } else if (target[i] > pivot) {
  31. more[more_count++] = target[i];
  32. } else {
  33. same[same_count++] = target[i];
  34. }
  35. }
  36. {
  37. int i = 0;
  38. for(int j = 0; j < less_count; j++) {
  39. target[i++] = less[j];
  40. }
  41. for(int j = 0; j < same_count; j++) {
  42. target[i++] = same[j];
  43. }
  44. for(int j = 0; j < more_count; j++) {
  45. target[i++] = more[j];
  46. }
  47. }
  48. // free(same); free(less); free(more);
  49. ternarySplitQuickSort(target, left, less_count);
  50. ternarySplitQuickSort(target, less_count + same_count - 1, right);
  51.  
  52. }
  53.  
  54. int main(int argc, char** argv){
  55. // Generate the running example array of size 12
  56. int n = 12;
  57. int target[12] = {48, 195, 12, 49, 198, 24, 99, 140, 48, 195, 12, 48};
  58.  
  59. // Generate an array of random numbers
  60. // int n = 10000000; // array length
  61. // int* target;
  62. // target = (int *)malloc( sizeof(int) * n); // Use the heap to generate a long array
  63. // for(int i=0; i<n; i++) {
  64. // target[i] = rand()%256;
  65. // }
  66.  
  67. clock_t sTime, eTime;
  68. sTime = clock();
  69.  
  70. ternarySplitQuickSort(target, 0, n-1);
  71.  
  72. eTime = clock();
  73. printf("Elapsed time = %f sec.\n", (float)(eTime - sTime)/(float)CLOCKS_PER_SEC);
  74.  
  75. // Check if the target is sorted
  76. int sorted = 1;
  77. for(int i = 0; i < (n-1); i++){
  78. if( target[i] > target[i+1]) sorted = 0;
  79. }
  80. if (sorted == 1) printf("sorted\n");
  81.  
  82. // free(target);
  83.  
  84. return 0; // 0 means EXIT_SUCCESS
  85. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement