Sorting integers with primes


/ Published in: C++
Save to your folder(s)

http://sortwithprimes.webs.com/
Deeper description on how it works.


Copy this code and paste it in your HTML
  1. int main()
  2. {
  3. srand(unsigned(time(NULL)));
  4.  
  5.  
  6. int upperLimit = 10000;
  7. int multipl = 1000;
  8. int size = 1000000;
  9. int *nrs = new int[size];
  10. for(int ix = 0 ; ix < size; ix++)
  11. {
  12. nrs[ix] = (rand()%multipl) * (rand()%upperLimit);
  13. }
  14.  
  15.  
  16. clock_t start,end;
  17. start = clock();
  18. primeSort(nrs,size);
  19. end = clock() - start;
  20. cout<<"Prime sort : "<<end<<endl;
  21.  
  22.  
  23. delete [] nrs;
  24. system("pause");
  25. return 0;
  26. }
  27.  
  28. void primeSort(int arr[], int size)
  29. {
  30. int primeCount,primeProduct,currentPrime;
  31. currentPrime = 1;
  32. primeProduct = currentPrime;
  33. primeCount = 0;
  34. while(primeProduct < size/3)
  35. {
  36. currentPrime = nextPrime(currentPrime);
  37. primeProduct *= currentPrime;
  38. primeCount++;
  39. }
  40.  
  41. int *occ = new int[primeProduct];
  42. int *primes = new int[primeCount];
  43. currentPrime = 1;
  44. for(int ix = 0 ; ix < primeCount ; ix++)
  45. {
  46. currentPrime = nextPrime(currentPrime);
  47. primes[ix] = currentPrime;
  48. }
  49.  
  50.  
  51. int index,
  52. currentProduct,
  53. currentOrder,
  54. nextOrder,
  55. border,
  56. count;
  57.  
  58. bool flag = true;
  59. border = count = currentOrder = 0;
  60. nextOrder = 1000000;
  61.  
  62. while(flag)
  63. {
  64. for(int ix = 0 ; ix < primeProduct; ix++)
  65. {
  66. occ[ix] = 0;
  67. }
  68. border = 0;
  69. flag = false;
  70. for(int ix = count ; ix < size-border; ix++)
  71. {
  72. while(arr[ix] >= primeProduct*(currentOrder+1) && ix < size-(border+1))
  73. {
  74. if(arr[ix] / primeProduct < nextOrder)
  75. {
  76. nextOrder = arr[ix] / primeProduct;
  77. }
  78. border++;
  79. swap(arr[size-border],arr[ix]);
  80. flag = true;
  81. }
  82. if(arr[ix] < primeProduct*(currentOrder+1))
  83. {
  84. index = 0;
  85. for(int z = 0; z < primeCount; z++)
  86. {
  87. currentProduct = arr[ix] % primes[z];
  88. for(int z_n = z + 1 ; z_n < primeCount; z_n++)
  89. {
  90. currentProduct *= primes[z_n];
  91. }
  92. index += currentProduct;
  93. }
  94. occ[index]++;
  95. }
  96. }
  97.  
  98. for(int ix = 0 ; ix < primeProduct; ix++)
  99. {
  100. index = 0;
  101. for(int z = 0; z < primeCount; z++)
  102. {
  103. currentProduct = ix % primes[z];
  104. for(int z_n = z + 1 ; z_n < primeCount; z_n++)
  105. {
  106. currentProduct *= primes[z_n];
  107. }
  108. index += currentProduct;
  109. }
  110. while(occ[index] > 0)
  111. {
  112. arr[count++] = ix + primeProduct*currentOrder;
  113. occ[index]--;
  114. }
  115. }
  116.  
  117. currentOrder = nextOrder;
  118. nextOrder = 10000000;
  119. }
  120.  
  121.  
  122. delete [] occ;
  123. delete [] primes;
  124.  
  125. }
  126.  
  127.  
  128. *** Trivial function, one could sieve or initiate directly
  129. int nextPrime(int current)
  130. {
  131. int result = current;
  132. bool status = false;
  133. while(!status)
  134. {
  135. result++;
  136. status = true;
  137. for(int ix = (int)pow(result,0.5); ix > 1; ix--)
  138. {
  139. if(result % ix == 0)
  140. {
  141. status = false;
  142. }
  143. }
  144. }
  145. return result;
  146. }

Report this snippet


Comments

RSS Icon Subscribe to comments

You need to login to post a comment.