shellsoert.htm
#include <Rcpp.h>
using namespace Rcpp;
inline void shell ( NumericVector unsorted, int size, NumericVector Gaps)
{
int gn=Gaps.size();
int j,gap ;
for (int t = gn-1; t > -1; t--)
{
gap=Gaps[t];
for (int i = gap; i < size; ++i)
{
double temp = unsorted[i];
for (j = i; j >= gap && temp < unsorted[j - gap]; j -= gap)
{
unsorted[j] = unsorted[j - gap];
}
unsorted[j] = temp;
}
}
}
inline NumericVector gapshell( int size ) {
NumericVector result;
for(int i=size/2;i>0;i/=2)
result.push_back(i);
return rev(result);}
inline NumericVector gapFrank( int N ) {
int tmp=10;
NumericVector result;
for(int k=2;tmp>1;k++){
tmp=2*(N/pow(2,k))+1;
result.push_back(tmp);}
return rev(result);}
inline NumericVector gapHibbard( int N ) {
NumericVector result;
int tmp=0;
for(int k=1;tmp<N;k++){
tmp=pow(2,k)-1;
result.push_back(tmp);}
return result;}
inline NumericVector gappratt( int N ) {
int n=N/3;
NumericVector result;
int tmp=0;
for(int k=1;tmp<n;k++){
tmp=(pow(3,k)-1)/2;
result.push_back(tmp);}
return result;}
inline NumericVector gapsed( int N ) {
NumericVector result;
result.push_back(1);
int tmp=0;
for(int k=1;;k++){
tmp=pow(4,k)+(3*pow(2,k-1))+1;
if(tmp>N)break;
result.push_back(tmp);}
return result;}
inline NumericVector gaptocuda( int N ) {
NumericVector result;
int tmp=0;
for(int k=1;;k++){
tmp=(pow(9,k)-pow(4,k))/(5*pow(4,k-1));
if(tmp>N)break;
result.push_back(tmp);} result[0]=1;
return result;}
inline NumericVector gaptocuda_emp( int N ) {
NumericVector result;
result.push_back(1);
int tmp=1;
for(int k=1;;k++){
tmp=2.25*tmp+1;
if(tmp>N)break;
result.push_back(tmp);} return result;}
NumericVector gapCiura( int sz ) {
NumericVector result;
result.push_back(1);
result.push_back(4);
result.push_back(10);
result.push_back(23);
result.push_back(57);
result.push_back(132);
result.push_back(301);
result.push_back(701);
result.push_back(1705);
return result;}
NumericVector sort_shell_gap(NumericVector unsorted) { int N =unsorted.size();
NumericVector gaps=gapshell(N);
NumericVector result=clone(unsorted);
shell(result,N,gaps);
return result;}
NumericVector sort_shell_frunk(NumericVector unsorted) { int N =unsorted.size();
NumericVector gaps=gapFrank(N);
NumericVector result=clone(unsorted);
shell(result,N,gaps);
return result;}
NumericVector sort_shell_hibbard(NumericVector unsorted) { int N =unsorted.size();
NumericVector gaps=gapHibbard(N);
NumericVector result=clone(unsorted);
shell(result,N,gaps);
return result;}
NumericVector sort_shell_patt(NumericVector unsorted) { int N =unsorted.size();
NumericVector gaps=gappratt(N);
NumericVector result=clone(unsorted);
shell(result,N,gaps);
return result;}
NumericVector sort_shell_sed(NumericVector unsorted) { int N =unsorted.size();
NumericVector gaps=gapsed(N);
NumericVector result=clone(unsorted);
shell(result,N,gaps);
return result;}
NumericVector sort_shell_tacuda(NumericVector unsorted) { int N =unsorted.size();
NumericVector gaps=gaptocuda(N);
NumericVector result=clone(unsorted);
shell(result,N,gaps);
return result;}
NumericVector sort_shell_tacudaemp(NumericVector unsorted) { int N =unsorted.size();
NumericVector gaps=gaptocuda_emp(N);
NumericVector result=clone(unsorted);
shell(result,N,gaps);
return result;}
NumericVector sort_shell_Ciura(NumericVector unsorted) { int N =unsorted.size();
NumericVector Ciura=gapCiura(0);
NumericVector result=clone(unsorted);
shell(result,N,Ciura);
return result;}
No comments:
Post a Comment