|
Packit |
67cb25 |
/* sort/subsetind_source.c
|
|
Packit |
67cb25 |
*
|
|
Packit |
67cb25 |
* Copyright (C) 1999,2000,2001 Thomas Walter, Brian Gough
|
|
Packit |
67cb25 |
*
|
|
Packit |
67cb25 |
* This is free software; you can redistribute it and/or modify it
|
|
Packit |
67cb25 |
* under the terms of the GNU General Public License as published by the
|
|
Packit |
67cb25 |
* Free Software Foundation; either version 3, or (at your option) any
|
|
Packit |
67cb25 |
* later version.
|
|
Packit |
67cb25 |
*
|
|
Packit |
67cb25 |
* This source is distributed in the hope that it will be useful, but WITHOUT
|
|
Packit |
67cb25 |
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
|
Packit |
67cb25 |
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
|
Packit |
67cb25 |
* for more details.
|
|
Packit |
67cb25 |
*/
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
/* find the k-th smallest elements of the vector data, in ascending order */
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
int
|
|
Packit |
67cb25 |
FUNCTION (gsl_sort, smallest_index) (size_t * p, const size_t k,
|
|
Packit |
67cb25 |
const BASE * src, const size_t stride,
|
|
Packit |
67cb25 |
const size_t n)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
size_t i, j;
|
|
Packit |
67cb25 |
BASE xbound;
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
if (k > n)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
GSL_ERROR ("subset length k exceeds vector length n", GSL_EINVAL);
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
if (k == 0 || n == 0)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
return GSL_SUCCESS;
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
/* take the first element */
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
j = 1;
|
|
Packit |
67cb25 |
xbound = src[0 * stride];
|
|
Packit |
67cb25 |
p[0] = 0;
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
/* examine the remaining elements */
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
for (i = 1; i < n; i++)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
size_t i1;
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
BASE xi = src[i * stride];
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
if (j < k)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
j++;
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
else if (xi >= xbound)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
continue;
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
for (i1 = j - 1; i1 > 0 ; i1--)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
if (xi > src[p[i1 - 1] * stride])
|
|
Packit |
67cb25 |
break;
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
p[i1] = p[i1 - 1];
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
p[i1] = i;
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
xbound = src[p[j-1] * stride];
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
return GSL_SUCCESS;
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
int
|
|
Packit |
67cb25 |
FUNCTION (gsl_sort_vector,smallest_index) (size_t * p, const size_t k,
|
|
Packit |
67cb25 |
const TYPE (gsl_vector) * v)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
return FUNCTION (gsl_sort, smallest_index) (p, k, v->data, v->stride, v->size);
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
int
|
|
Packit |
67cb25 |
FUNCTION (gsl_sort, largest_index) (size_t * p, const size_t k,
|
|
Packit |
67cb25 |
const BASE * src, const size_t stride,
|
|
Packit |
67cb25 |
const size_t n)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
size_t i, j;
|
|
Packit |
67cb25 |
BASE xbound;
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
if (k > n)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
GSL_ERROR ("subset length k exceeds vector length n", GSL_EINVAL);
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
if (k == 0 || n == 0)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
return GSL_SUCCESS;
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
/* take the first element */
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
j = 1;
|
|
Packit |
67cb25 |
xbound = src[0 * stride];
|
|
Packit |
67cb25 |
p[0] = 0;
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
/* examine the remaining elements */
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
for (i = 1; i < n; i++)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
size_t i1;
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
BASE xi = src[i * stride];
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
if (j < k)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
j++;
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
else if (xi <= xbound)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
continue;
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
for (i1 = j - 1; i1 > 0 ; i1--)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
if (xi < src[stride * p[i1 - 1]])
|
|
Packit |
67cb25 |
break;
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
p[i1] = p[i1 - 1];
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
p[i1] = i;
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
xbound = src[stride * p[j-1]];
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
return GSL_SUCCESS;
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
int
|
|
Packit |
67cb25 |
FUNCTION (gsl_sort_vector,largest_index) (size_t * p, const size_t k,
|
|
Packit |
67cb25 |
const TYPE (gsl_vector) * v)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
return FUNCTION (gsl_sort, largest_index) (p, k, v->data, v->stride, v->size);
|
|
Packit |
67cb25 |
}
|