## Posted By

Henkish_92 on 07/12/13

# Sorting integers with primes

/ Published in: C++

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

`int main(){	srand(unsigned(time(NULL)));  	int upperLimit = 10000;	int multipl = 1000;	int size = 1000000;	int *nrs = new int[size];	for(int ix = 0 ; ix < size; ix++)	{		nrs[ix] = (rand()%multipl) * (rand()%upperLimit);	}  	clock_t start,end;	start = clock();	primeSort(nrs,size);	end = clock() - start;	cout<<"Prime sort : "<<end<<endl;  	delete [] nrs;	system("pause");	return 0;} void primeSort(int arr[], int size){	int primeCount,primeProduct,currentPrime;	currentPrime = 1;	primeProduct = currentPrime;	primeCount = 0;	while(primeProduct < size/3)	{		currentPrime = nextPrime(currentPrime);		primeProduct *= currentPrime;		primeCount++;	} 	int *occ = new int[primeProduct];	int *primes = new int[primeCount];	currentPrime = 1;	for(int ix = 0 ; ix < primeCount ; ix++)	{		currentPrime = nextPrime(currentPrime);		primes[ix] = currentPrime;	}  	int index,		currentProduct,		currentOrder,		nextOrder,		border,		count; 	bool flag = true;	border = count = currentOrder = 0;	nextOrder = 1000000; 	while(flag)	{		for(int ix = 0 ; ix < primeProduct; ix++)		{			occ[ix] = 0;		}		border = 0;		flag = false;		for(int ix = count ; ix < size-border; ix++)		{			while(arr[ix] >= primeProduct*(currentOrder+1) && ix < size-(border+1))			{				if(arr[ix] / primeProduct < nextOrder)				{					nextOrder = arr[ix] / primeProduct;				}				border++;				swap(arr[size-border],arr[ix]);				flag = true;			}			if(arr[ix] < primeProduct*(currentOrder+1))			{				index = 0;				for(int z = 0; z < primeCount; z++)				{					currentProduct = arr[ix] % primes[z];					for(int z_n = z + 1 ; z_n < primeCount; z_n++)					{											currentProduct *= primes[z_n];					}					index += currentProduct;				}				occ[index]++;			}		} 		for(int ix = 0 ; ix < primeProduct; ix++)		{			index = 0;			for(int z = 0; z < primeCount; z++)			{				currentProduct = ix % primes[z];				for(int z_n = z + 1 ; z_n < primeCount; z_n++)				{					currentProduct *= primes[z_n];				}				index += currentProduct;			}			while(occ[index] > 0)			{				arr[count++] = ix + primeProduct*currentOrder;				occ[index]--;			}		} 		currentOrder = nextOrder;		nextOrder = 10000000;	}  	delete [] occ;	delete [] primes; }  *** Trivial function, one could sieve or initiate directlyint nextPrime(int current){	int result = current;	bool status = false;	while(!status)	{		result++;		status = true;		for(int ix = (int)pow(result,0.5); ix > 1; ix--)		{			if(result % ix == 0)			{				status = false;			}		}	}	return result;}`

You need to login to post a comment.