Advanced Search

Sorting integers with primes

/ Published in: C++
Save to your folder(s)
http://sortwithprimes.webs.com/
Deeper description on how it works.

Expand | Embed | Plain Text

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.