diff options
Diffstat (limited to 'src/sorting.h')
-rw-r--r-- | src/sorting.h | 134 |
1 files changed, 68 insertions, 66 deletions
diff --git a/src/sorting.h b/src/sorting.h index ec16bbe..03eabc6 100644 --- a/src/sorting.h +++ b/src/sorting.h @@ -1,103 +1,105 @@ template <class T> -__device__ void swap(T &a, T &b) +__device__ void +swap(T &a, T &b) { - T tmp = a; - a = b; - b = tmp; + T tmp = a; + a = b; + b = tmp; } template <class T> -__device__ void reverse(int n, T *a) +__device__ void +reverse(int n, T *a) { - for (int i=0; i < n/2; i++) - swap(a[i],a[n-1-i]); + for (int i=0; i < n/2; i++) + swap(a[i],a[n-1-i]); } template <class T> -__device__ void piksrt(int n, T *arr) +__device__ void +piksrt(int n, T *arr) { - int i,j; - T a; + int i,j; + T a; - for (j=1; j < n; j++) - { - a = arr[j]; - i = j-1; - while (i >= 0 && arr[i] > a) - { - arr[i+1] = arr[i]; - i--; - } - arr[i+1] = a; + for (j=1; j < n; j++) { + a = arr[j]; + i = j-1; + while (i >= 0 && arr[i] > a) { + arr[i+1] = arr[i]; + i--; } + arr[i+1] = a; + } } template <class T, class U> -__device__ void piksrt2(int n, T *arr, U *brr) +__device__ void +piksrt2(int n, T *arr, U *brr) { - int i,j; - T a; - U b; + int i,j; + T a; + U b; - for (j=1; j < n; j++) - { - a = arr[j]; - b = brr[j]; - i = j-1; - while (i >= 0 && arr[i] > a) - { - arr[i+1] = arr[i]; - brr[i+1] = brr[i]; - i--; - } - arr[i+1] = a; - brr[i+1] = b; + for (j=1; j < n; j++) { + a = arr[j]; + b = brr[j]; + i = j-1; + while (i >= 0 && arr[i] > a) { + arr[i+1] = arr[i]; + brr[i+1] = brr[i]; + i--; } + arr[i+1] = a; + brr[i+1] = b; + } } template <class T> -__device__ unsigned long searchsorted(unsigned long n, T *arr, const T &x) +__device__ unsigned long +searchsorted(unsigned long n, T *arr, const T &x) { - unsigned long ju,jm,jl; - int ascnd; + unsigned long ju,jm,jl; + int ascnd; - jl = 0; - ju = n; + jl = 0; + ju = n; - ascnd = (arr[n-1] > arr[0]); + ascnd = (arr[n-1] > arr[0]); - while (ju-jl > 1) - { - jm = (ju+jl) >> 1; + while (ju-jl > 1) { + jm = (ju+jl) >> 1; - if (x >= arr[jm] == ascnd) - jl = jm; - else - ju = jm; - } - - if (x <= arr[0]) - return 0; - else if (x == arr[n-1]) - return n-1; + if (x >= arr[jm] == ascnd) + jl = jm; else - return ju; + ju = jm; + } + + if (x <= arr[0]) + return 0; + else if (x == arr[n-1]) + return n-1; + else + return ju; } template <class T> -__device__ void insert(unsigned long n, T *arr, unsigned long i, const T &x) +__device__ void +insert(unsigned long n, T *arr, unsigned long i, const T &x) { - unsigned long j; - for (j=n-1; j > i; j--) - arr[j] = arr[j-1]; - arr[i] = x; + unsigned long j; + for (j=n-1; j > i; j--) + arr[j] = arr[j-1]; + arr[i] = x; } template <class T> -__device__ void add_sorted(unsigned long n, T *arr, const T &x) +__device__ void +add_sorted(unsigned long n, T *arr, const T &x) { - unsigned long i = searchsorted(n, arr, x); + unsigned long i = searchsorted(n, arr, x); - if (i < n) - insert(n, arr, i, x); + if (i < n) + insert(n, arr, i, x); } |